Playing with Fermat's little theorem

Question

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.

Answer 1

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

Answer 2

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