Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
1  
Fixing both $a$ and $n$ would make the question somewhat boring :) – darij grinberg Mar 27 at 22:36
1  
@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
1  
$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
1  
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
up vote 4 down vote accepted

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

share|cite|improve this answer
    
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
1  
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$.

share|cite|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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