I am helping my nephew in the secondary school with the problem stated in the title:
Find all positive integers $n$ such that $n$ divides $a^{25} -a$ for all positive integers $a$
I tried several cases and find that possible values of $n$ is $2, 3, 5, 6, 7, 10$ but don't know how to solve completely this problem.
Can anybody shed light on it?
Thank you very much!
Best Answer
Here is a hands on method of getting the primes you need quite quickly.
Note that $a^{25}-a=a(a^{24}-1)=a(a^{12}+1)(a^6+1)(a^3+1)(a^3-1)$ and $a^{12}+1=(a^4+1)(a^8-a^4+1)$ by successive factorisations using the difference of two squares, so you can obtain a full factorisation for small $a$.
For $a=2$ you get $2^{25}-2=2\cdot17\cdot241\cdot65\cdot9\cdot7$ and the factorisation is easy to complete.
Do a similar thing for $a=3$ to get $3\cdot82\cdot6481\cdot330\cdot 28\cdot 26$
You can then reduce the numbers you have to test to common factors these two, which will be factors of $2\cdot 3\cdot 5\cdot 7\cdot 13$ since no other primes are common.
To prove this works for all factors you need to prove that each of the primes $2,3,5,7,13$ will always divide $a^{25}-a$, and what you need is that $p|a^p-a$ for all primes $p$ and all integers $a$ which is a modest extension of the usual statement of Fermat's little theorem. Use that with the five identified primes.