# Find all positive integers $n$ such that $n$ divides $a^{25} - a$ for all positive integers $a$

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!

• Eulers theorem suggests that $\phi(n)$ should divide 24 – TheOscillator Oct 12 '15 at 16:29
• That's sufficient, but not necessary. @TheOscillator – Thomas Andrews Oct 12 '15 at 16:30
• For example, it is true for $n=65$, but $\phi(65)=48$ is not a divisor of $24$. @TheOscillator – Thomas Andrews Oct 12 '15 at 16:35
• Sorry, it is also not sufficient, I was wrong about that. $\phi(4)$ divides $24$, but $2^{25}-2$ is not divisible by $4$. @TheOscillator – Thomas Andrews Oct 12 '15 at 16:36

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.

• Thanks for your answer! It's a nice approach! – Trung Ta Oct 12 '15 at 16:51

First notice that $n$ is product of different primes, because if $p$ is a prime $p^2$ does not divide $p^{25} - p$. Take $a=2$ to get $2^{25}-2$ which factorizes to $2\cdot 3^2 \cdot 5 \cdot 7 \cdot 13 \cdot 17 \cdot 241$. So the primes in $n$ can only be from these. $17$ and $241$ are ruled out because $17 \nmid 3^{25} - 3$ and $241\nmid3^{25}-3$. For the rest it is easy to check (using Fermat's Theorem) that $a^{25}\equiv a(mod p)$ for $p=2,3,5,7,13$. Any combination of these $5$ primes can serve as $n$. So the answer is all divisor of $2\cdot 3 \cdot 5 \cdot 7 \cdot 13$.

• yeah.. sorry for being so sloppy. – pchakrab Oct 12 '15 at 16:46

First, note that if it is true for $n$, it is true for any divisor of $n$.

Also, if it is true for $n$ and $m$, it is true for the least common multiple f $n,m$.

So you need to concentrate on the prime powers first.

No prime squared has this property, since if $p$ is a prime, $p^{25}-p$ is not divisible by $p^2$. That means any $n$ must not have a prime squared as a divisor.

If $a$ is divisible by $p$, then $a^{25}-a$ is divisible by $p$. So we only care about the cases $a$ relatively prime to $p$, so $p\mid a^{24}-1$ in those cases.

But that means that $24$ is divisible by $p-1$.[*]

So what primes $p$ have $p-1$ dividing $24$? Exactly $2,3,5,7,13$.

Then $n$ can be any product of these primes, or, alternatively, any divisor of $2\cdot 3\cdot 5\cdot 7\cdot 13$.

[*] Unfortunately, to know this, you have to know a little number theory.

• Thanks for your answer! Can you explain which theorem is used in [*]? I know the Little Fermat's theorem that $a^{p-1} -1$ is divisible by $p$, but is $p-1$ is the smallest number $h$ such that p divides $a^h -1$? – Trung Ta Oct 12 '15 at 16:45
• There always exists an $a$ such that $h=p-1$ is the smallest number such that $a^h-1$ is divisible by $p$. It is not true for all $a$ that $p-1$ is the smallest number. @TrungTa – Thomas Andrews Oct 12 '15 at 16:47