## USAMO 2008: Problem 1

For discussing Olympiad Level Number Theory problems
sourav das
Posts: 461
Joined: Wed Dec 15, 2010 10:05 am
Location: Dhaka
Contact:

### USAMO 2008: Problem 1

(Titu Andreescu) Prove that for each positive integer $n$, there are pairwise relatively prime integers $k_0, k_1 ... k_n$, all strictly greater than 1, such that $k_0 k_1 .... k_n -1$ is the product of two consecutive integers.
You spin my head right round right round,
When you go down, when you go down down......
(-$from$ "$THE$ $UGLY$ $TRUTH$" )

*Mahi*
Posts: 1175
Joined: Wed Dec 29, 2010 12:46 pm
Location: 23.786228,90.354974
Contact:

### Re: USAMO 2008: Problem 1

We will use induction on $k_n$. Let there be $k_0,k_1,k_2..k_{n-1}$ satisfying the given condition. So we can write $\prod k_i = a^2+a+1$. Now , some $k_n$ satisfying the condition $k_n \prod k_i = (a+m)^2+(a+m)+1$ for some $m \in \mathbb N$ and $(\prod k_i , k_n)=1$ will prove the fact.
Now we can write $(a+m)^2+(a+m)+1=a^2+a+1 + m(2a+ m +1)$ . So it is enough to set $m= a^2+a+1$, which will make $k_n$ an integer. Setting $m=a^2+a+1$ , we will get $k_n= a^2+a+1 +2a+2=a^2+3a+3$.Now as $(a^2+a+1,a^2+3a+3)=1$, $k_n=a^2+3a+3$ is a solution.
Indeed, $(a^2+a+1)(a^2+3a+3)= (a+1)^4+(a+1)^2+1$,so the proof is complete.
Use $L^AT_EX$, It makes our work a lot easier!
$\prod k_i = a^2+a+1$ now we can take $k_n=a^2-a+1$ satisfying $(\prod k_i,k_n)=1$ and $(a^2+a+1)(a^2-a+1) =a^4+a^2+1$