THE 68th NMO SELECTION TESTS FOR THE JUNIOR BALKAN MATHEMATICAL OLYMPIAD

We have $504=2^3\cdot 3^2\cdot 7$.

a) $\Rightarrow$ b). First we prove that $(n,5)=1$. If $(n,5)\ne 1$ then $n=5k$. The sequence $(5m+2{)}_{m\ge 1}$ is an arithmetic sequence with ratio 5. Its first term being coprime with the ratio, from Dirichlet's Theorem it follows that the sequence contains infinitely many primes. Then, there exists a prime $p$ such that $p=5m+2$ and $p>n$. As $(p,n)=1$ it follows that $p^6\equiv 1(\mathrm{mod}n)$, i.e., $n\mid (5m+2{)}^6-1$. As $5\mid n$ and $(5m+2{)}^6=M_5+2^6$, we get that 5 divides 63, absurd! As $(n,5)=1$, according to the hypothesis $5^6\equiv 1(\mathrm{mod}n)$, i.e. $n\mid (5^6-1)$. But $5^6-1=(5^3-1)(5^3+1)=(5-1)(5^2+5+1)(5+1)(5^2-5+1)=4\cdot 31\cdot 6\cdot 21=2^3\cdot 3^2\cdot 7\cdot 31$, hence $n\mid 2^3\cdot 3^2\cdot 7\cdot 31$ (1) From (1) one can notice that $(n,11)=1$, hence $11^6\equiv 1(\mathrm{mod}n)$, i.e., $n\mid (11^6-1)$. But $11^6-1=(11^3-1)(11^3+1)=(11-1)(11^2+11+1)(11+1)\cdot (11^2-11+1)=10\cdot 133\cdot 12\cdot 111$, therefore $$n\mid 2^3\cdot 3^2\cdot 5\cdot 7\cdot 19\cdot 37(2)$$ From (1) and (2) it follows that $n\mid 2^3\cdot 3^2\cdot 7$, i.e., $n\mid 504$.

b) $\Rightarrow$ a). Let $x\in \mathbb{Z}$. Then $x^6-1=(x^2-1)(x^4+x^2+1)$. We have: 1. if $(x,2)=1$ then $x-1$ and $x+1$ are consecutive even numbers, hence $2^3\mid x^6-1$; 2. if $(x,7)=1$, from Fermat's Theorem we obtain $7\mid x^6-1$; 3. if $(x,3)=1$ then $x=3k\pm 1$. Obviously $3\mid x-1$ or $3\mid x+1$, hence $3\mid x^2-1$. We also have $$\begin{gathered} x^4+x^2+1=(3k\pm 1{)}^4+(3k\pm 1{)}^2+1=(M_3+1)+(M_3+1)+1=M_3,\text{ i.e.,} \\ 3\mid x^4+x^2+1. \end{gathered}$$ It follows that for $(x,3)=1$ we have $3^2\mid x^6-1$. If $n\in \mathbb{N}$, $n\ge 2$ and $n\mid 504$, then $n=2^a\cdot 3^b\cdot 7^c$ with $a\in \{0,1,2,3\}$, $b\in \{0,1,2\}$, $c\in \{0,1\}$ and $a,b,c$ not all of them 0. From the three statements above it follows that for all integer $x$ coprime with $n$ we have $n\mid x^6-1$, i.e. $x^6\equiv 1(\mathrm{mod}n)$.