# Playing with Fermat's little theorem

Fermat's little theorem states that if $~p~$ is a prime number then for any integer $~a~$ the number $~a^p - a~$ is divisible by $~p~$.

What if one fixes the exponent $~n~$ and tries to find all $~m~$ such that for any integer $~a~$ the number $~a^n - a~$ is divisible by $~m~$? Is it true that there is at least one such $~m~$? Is the set of all such $~m~$ finite? Do you have any ideas how we can find them all?

I'm not sure that this questions have any reasonable mathematical importance - rather it's just my own curiosity. Thanks in advance for any ideas.

-
Fixing both $a$ and $n$ would make the question somewhat boring :) – darij grinberg Mar 27 at 22:36
@Jean-ClaudeArbaut I certainly meant "for all $a$". Thanks for remark - i've clarified the question. – Igor Mar 27 at 22:38
Clearly the set is finite for $n>1$. Since the values of $m$ must divide $2^n-2$. – Carry on Smiling Mar 27 at 22:40
$a^n-a$ is always divisible by $2$. But for general $n$ I don't think we can say more. – André Nicolas Mar 27 at 22:41
I'm interested in the set $\{ m \in \mathbb{N} : \forall a \in \mathbb{N} a^n - a \equiv 0 \mod m\}$ – Igor Mar 27 at 22:48

Given $n>1$ we must find all the possible values of $m$ for which $a^{n}\equiv a \bmod m$ for all $a$, call this set $M$.

It is clear that if $m\in M$ then $m$ is square-free.

The Chinese remainder theorem ensures that the distinct primes $p_1,p_2\dots p_n$ are all in $M$ if and only if $p_1p_2\dots p_n$ is in $M$.

Therefore, to characterize $M$ it suffices to find all primes $p$ so that $a^n\equiv a \bmod p$ for all $a$, this is equivalent to finding all the primes $p$ so that $a^{n-1}\equiv 1 \bmod p$ for all $a$ which are not a multiples of $p$.

Since the multiplicative group of $\mathbb Z_p$ is cyclic these are exactly the prime numbers for which $p-1$ divides $n-1$.

So $m$ is in $M$ if and only if $m$ is square-free and every prime divisor $p$ of $m$ satisfies $p-1|n-1$.

-
It's 2 after midnight in my timezone so i might ask a very stupid question. But could you explain, please, why $~m~$ has to be square-free? – Igor Mar 27 at 22:53
Suppose $p^2|m$. Let $a=m/p$. Then $a^n$ is a multiple of $m$, so $a^n-a$ is not a multiple of $m$ (because $a^n$ is and $a$ is not). – Carry on Smiling Mar 27 at 22:55
@Igor : hence you get that if for every $d | n-1$, $d+1$ is not a prime, then the set $M$ is empty (excluding $m = 1$) – user1952009 Mar 27 at 23:00
yeah, that seems to be the case. – Carry on Smiling Mar 27 at 23:01
and "The Chinese remainder theorem ensures that $p_1p_2\dots p_n$ is in $M$ if and only if the distinct primes $p_1,p_2,\dots, p_n$ are all in $M$" ($1$ being in $M$ since it has no prime divisors) – user1952009 Mar 27 at 23:03

You can ask, more generally, given any integer polynomial $p(x)$, what is the great common divisor of $p(\mathbb Z)$?

Every integer polynomial of degree $n$ can be written uniquely as:

$$f(x)=\sum_{k=0}^n a_k(x)_k$$

where the $a_k$ are integers and the $(x)_k$ are the falling factorials: $(x)_k=x(x-1)\cdots(x-(k-1))$.

Now, $(x)_k$ is always divisible by $k!$ and is equal to $k!$ when $x=k$.

More generally, $f(0),f(1),\dots,f(n)$ are divisible by $\gcd(a_00!,a_11!,a_22!,\dots,a_nn!)$. This is actually exactly the value.

For example, $x^3-x=(x)_3 +3(x)_2$, so $a^3-a$ has $m=\gcd(3!,3\cdot 2!)=6$.

Not sure how to write $x^n-x$ generally in this form, though.

$$x^4-x = (x)_4 + +6(x)_3+7(x)_2$$

So $m=2$ when $n=4$.

-