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.

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

  • $\begingroup$ 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? $\endgroup$ – Igor Mar 27 '16 at 22:53
  • 1
    $\begingroup$ 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). $\endgroup$ – Jorge Fernández Hidalgo Mar 27 '16 at 22:55
  • $\begingroup$ @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$) $\endgroup$ – reuns Mar 27 '16 at 23:00
  • $\begingroup$ yeah, that seems to be the case. $\endgroup$ – Jorge Fernández Hidalgo Mar 27 '16 at 23:01
  • $\begingroup$ 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) $\endgroup$ – reuns Mar 27 '16 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$.


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.