Bangladesh IMO TST 1: 2011/ NT-1 (P 3)

[Moon]

Problem 3:
The integer $x$ is at least $3$ and $n=x^6-1$. Let $p$ be a prime and $k$ be a positive integer such that $p^k$ is a factor of $n$. Show that $p^{3k}<8n$.

[nayel]

Let $k$ be the largest positive integer such that $p^k\mid n$. Then it suffices to prove that $p^{3k}<8n$. First assume that $p>3$.

Claim. $p^k<2x^2$.
Proof. We have $p^k\mid x^6-1=(x^3-1)(x^3+1)$. Hence $p^k\mid x^3-1$ or $p^k\mid x^3+1$. Note that $p$ cannot divide both $x^3-1$ and $x^3+1$ as that would imply $p\mid -(x^3-1)+(x^3+1)=2$ , impossible by our choice of $p$.
Case 1. $p^k\mid x^3-1$.
This implies $p^k\mid (x-1)(x^2+x+1)$. If $p$ divides both $x-1$ and $x^2+x+1$, then $p\mid (x^2+x+1)-(x+2)(x-1)=3$ , impossible since $p>3$. Thus $p^k\le\max\{x-1,x^2+x+1\}<2x^2$ for $x\ge 3$. Thus our claim holds in this case.
Case 2. $p^k\mid x^3+1$.
Then we have $p^k\mid (x+1)(x^2-x+1)$. If $p$ divides both $x+1$ and $x^2-x+1$, then $p\mid (x^2-x+1)-(x-2)(x+1)=3$ , impossible since $p>3$. Thus $p^k\le\max\{x+1,x^2-x+1\}<2x^2$ for $x\ge 3$. Therefore the claim holds in all cases.

Therefore $p^k\le 2x^2-1$ which implies $p^{3k}<(2x^2)(2x^2)(2x^2-1)=8x^6-4x^4<8x^6-8=8n$, as required.

Now we have to examine the case $p\le 3$. I'll post the rest of the solution a few moments later.

[nayel]

(Remaining part of the previous solution)

i) $p=2$: Then $2^k\mid x^6-1$, so $x$ is odd. But $x^2\pm x+1$ is odd, so $2^k\mid x^6-1=(x-1)(x+1)(x^2-x+1)(x^2+x+1)\Rightarrow 2^k\mid (x-1)(x+1)=x^2-1$. Therefore $p^{3k}=2^{3k}\mid (x^2-1)^3<8x^6-8=8n$, as required.

ii) $p=3$: Then $3^k\mid x^6-1=(x^2-1)(x^4+x^2+1)$.
Lemma. For any prime $p$ and positive integer $a$, $\displaystyle\gcd\left(a-1,\frac{a^p-1}{a-1}\right)\in\{1,p\}$.
Proof. Let $g$ be the gcd in the statement. Then $g\mid a-1$, so $a\equiv 1\pmod g$ and hence $\displaystyle\frac{a^p-1}{a-1}=a^{p-1}+a^{p-2}+\dots+1\equiv p\pmod g$. Therefore $g\mid p\Rightarrow g=1$ or $p$. $\blacksquare$
Hence it follows that $\gcd(x^2-1,x^4+x^2+1)=1$ or $3$. In the first case, $x$ must be divisible by $3$, which is impossible. Hence $\gcd(x^2-1,x^4+x^2+1)=3$. This implies that $3$ divides one of $x^2-1,x^4+x^2+1$ and $3^{k-1}$ divides the other.

i) If $3^{k-1}\mid x^2-1$, then $3^{k-1}\mid x-1$ or $x+1$ which implies $3^{k-1}\le x+1$. Hence $3^{3k-3}\le (x+1)^3\Rightarrow 3^{3k}\le (3x+3)^3<8(x^6-1)=8n$, which holds for all $x\ge 3$ by induction.

ii) If $3^{k-1}\mid x^4+x^2+1$ then $3\mid x^2-1$ and $3^2\nmid x^2-1$. Hence $x^2-1\equiv 3$ or $6\pmod{3^2}$, which implies $x^4+x^2+1\equiv 12\pmod{3^2}$. Thus $k-1=1\Rightarrow k=2$, and therefore $3^{3k}=3^6<8(x^6-1)=8n$. This completes the solution.

[Masum]

Sorry for my late reply.Here is the complete solution.But it is actually not different from the previous,only in using LTE.
Lemma 1: $gcd(x^2-x+1,x^2+x+1)=1$
Proof:
Let $gcd (x^2-x+1,x^2+x+1)=g$
Then $g|x^2-x+1,x^2+x+1$ so their difference $2x$ too.But note that $g$ odd.So $g|x|x^2-x,x^2-x+1$,so their difference $1$ too.That means that $g=1$
Lemma 2: $gcd(x-1,\frac {x^n-1} {x-1})|n$
$x^n-1=(x-1)(x^{n-1}+...+1)$
From the Remainder Theorem,$gcd(x-1,x^{n-1}+...+1)=gcd(x-1,1+....+1)=gcd(x-1,n)$ which of-course divide $n$.
When $n=p$ a prime,we have $gcd$ is $1$ or $p$.
Lemma 3:
$8(x^3-1)>27(x+1)$
Proof:
Straight forward if we use Induction.
We consider three cases:
Case 1:$p=2$ and let $v_{2}(n)=k$
Note that $x^2-x+1$ and $x^2+x+1$ both are odd.So then if $x$ even,it is trivial.Let's see when $x$ odd.
Again note that if $v_2(x+1)=l$ or $v_2(x-1)=l, v_2(x^2-1)=l+1$.So then $l+1=k$ and $x^2-1\ge 2^k$
Almost obviously $2(x^2+x+1)>x^2-1\ge 2^k$ and $4(x^2-x+1)>x^2-1\ge 2^k$
Thus $8(x^2-1)(x^2+x+1)(x^2-x+1)>2^k.2^k.2^k\Longrightarrow 2^{3k}$
When $p$ odd,$p|x^3+1$ or $x^3-1$,otherwise $p$ would divide their difference $2$.
Case 2:$p=3$
We can assume $x>4$ after checking this true for $x=3,4$
Let $3|x+1,$then the case $3|x-1$ would be much similar to that.
Let $v_3(x+1)=l,l>1$ since the theorem is obviously valid for $l=1$.Then according to LTE $v_3(x^3+1)=l+1$ or $l+1=k$
Also $3\not| \frac {x^2-x+1} {3}$ because if $3^2|x^2-x+1$,then $gcd(x^2-x+1,x+1)=9$ at least,contradicting the fact that $gcd(x+1,x^2-x+1)=3$(we get it from the lemma $2$)
Again note that $x^2+x+1>3(x+1)$ since $x\ge 3$ is given.Then $x^2-x+1>3.3^l=3^k$
From lemma $3,$we may conclude that $8(x^3-1)>27(x+1)\ge 27.3^l=27.3^{k-1}$
$x+1\ge 3^l=3^{k-1}$
Multiplying the inequalities,we get $8(x^3-1)(x+1)(x^2-x+1)>27.(3^{k-1})^3=3^{3k}$
Case 3: We shall see the case for $x+1$,the other case is similar.
Now $p\not| x+1,$so $p^k|x^2-x+1$ and then $x^2-x+1\ge p^k$
Then almost obviously $4(x^2-1)>x^2-x+1\ge p^k$ and $2(x^2+x+1)>p^k$
Multiply them and the result follows.