1
$\begingroup$

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!

$\endgroup$
  • 1
    $\begingroup$ Eulers theorem suggests that $\phi(n)$ should divide 24 $\endgroup$ – TheOscillator Oct 12 '15 at 16:29
  • 1
    $\begingroup$ That's sufficient, but not necessary. @TheOscillator $\endgroup$ – Thomas Andrews Oct 12 '15 at 16:30
  • $\begingroup$ For example, it is true for $n=65$, but $\phi(65)=48$ is not a divisor of $24$. @TheOscillator $\endgroup$ – Thomas Andrews Oct 12 '15 at 16:35
  • $\begingroup$ 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 $\endgroup$ – Thomas Andrews Oct 12 '15 at 16:36
1
$\begingroup$

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.

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

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 $.

$\endgroup$
  • $\begingroup$ yeah.. sorry for being so sloppy. $\endgroup$ – pchakrab Oct 12 '15 at 16:46
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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$? $\endgroup$ – Trung Ta Oct 12 '15 at 16:45
  • 1
    $\begingroup$ 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 $\endgroup$ – Thomas Andrews Oct 12 '15 at 16:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.