Least $x$ such that $x \mid (n^x-n)$

Question

Let $x$ be a natural number of the form $3qp$ where $q,p$ are prime. Find the least value of $x$ such that $x \mid (n^x - n)$ for all $n$ in $\Bbb{Z}^+$.

I noticed that if $n^x - n$ can be written in the form $a(a+1)(a+2)\dotsb(a+x-1)$ for some natural $a$ then it is divisible by $x$, but this didn't get me far.

To give some context, this problem is from the first level of the IMO selection process in my country. So, a short solution using preferably only elementary number theory would be appreciated. Thanks!

Answer 1

$p,q$ cannot be $2$: otherwise $n=2$ leads to a contradiction $\pmod 3$. There cannot be two equal primes among $3,p,q$: if $r$ were such a prime, then $n=r$ would provide a contradiction $\pmod {r^2}$.

Being a multiple of $x$ is thus equivalent to being a multiple of $3$, $p$ and $q$. We have $n^x-n\equiv 0\equiv x \pmod 3$, as $x$ is odd.

So the condition is equivalent to $p\mid n^{3pq}-n$ and $q\mid n^{3pq}-n$ for all $n$. By Fermat's little theorem this is also equivalent to

• $p\mid n^{3q}-n$ and
• $q\mid n^{3p}-n$ for all $n$.

If $p=5$, then the $q\mid n^{3p}-n= n^{15}-n$ for all $n$ will fail. Pick a primitive root modulo $q$ for $n$: then $q\mid n^{15}-n$ means that $q-1\mid 14$. As $q$ is odd, only $2+1$ and $14+1$ are the candidates, but none of these can be $q$.

This leads to the crucial observation: $q-1\mid 3p-1$ and $p-1\mid 3q-1$, and these together are equivalent to the conditions of the problem (think about it).

You can finish the proof from here yourself. (I think 3, 11, 17 give the smallest value $x=561$.)