NMO Selection Tests for the Balkan and International Mathematical Olympiads

We show that every prime number $p$, $2\le p\le n$, divides the product $(a-1)(a^2-1)\cdots (a^{n-1}-1)$ to at least as high a power as it divides $n!$. The exponent of the highest power of $p$ which divides $n!$ is $$\epsilon =\sum _{k\ge 1}\lfloor n/p^k\rfloor <\sum _{k\ge 1}n/p^k=n/(p-1).$$ On the other hand, by hypothesis, $p$ does not divide $a$, so at least $\lfloor (n-1)/(p-1)\rfloor$ factors of the product $(a-1)(a^2-1)\cdots (a^{n-1}-1)$ are divisible by $p$, by Fermat's Little Theorem. Finally, notice that $\epsilon \le \lfloor (n-1)/(p-1)\rfloor$. If $n/(p-1)$ is integral, then $\epsilon \le n/(p-1)-1=(n-p)/(p-1)\le \lfloor (n-1)/(p-1)\rfloor$; otherwise, $p\ge 3$ and $n/(p-1)-(n-1)/(p-1)=1/(p-1)<1$, so $\epsilon \le \lfloor n/(p-1)\rfloor =\lfloor (n-1)/(p-1)\rfloor$.