# Proving $310 \mid n^{121}-n$ for all integers $n$

I wrote it as $n^{120}=1\pmod{310}$ and thought I'd divide it in simpler congruences with primes (is this right?)

$$n^{120}=n^{4\cdot30}=1\pmod{31}$$

$$n^{120}=n^{30\cdot4}=1\pmod{5}$$

But then I'm stuck on this one: it seems to be a false congruence and I guess I can't apply Fermat's theorem on this one, or can I? How do I solve it?

$$n^{120}=1\pmod{2}$$

If this approach is valid I'd prefer answers continuing from here if possible.

• This is not true for $n = \pm 1$. – Alex Silva Jan 2 '15 at 11:55
• In fact, it does not hold for any odd $n$. – Some Math Student Jan 2 '15 at 11:57
• I think it holds only for numbers in the form $310k$, with $k \in \mathbb{Z}$. – Alex Silva Jan 2 '15 at 11:58
• It does actually, I'm checking by plugging number on Wolframalpha, I'm kind of confused right now lol – Snowflake Jan 2 '15 at 12:03
• What? This is bizarre. Do you really think $310|n^{121}$ for every integer $n$? The only prime factors of $n^{121}$ are just the prime factors of $n$ with repetition. You are saying that every integer contains the prime factors of $310$. Isn't that a bit unbelievable? – MPW Jan 2 '15 at 12:05

Hint: $\varphi(310)=120$, where $\varphi$ is the Euler totient function.
Hint: Remember that Fermat's theorem is actually a special case of Euler's theorem: given $\gcd(n, a) = 1$, then $n^{\phi(a)} \equiv 1 \pmod a$. Since $\phi(p) = p - 1$ for $p$ prime, you get Fermat's theorem.
Since $\phi(310) = 120$, that means that if $\gcd(n, 310) = 1$, then $n^{120} \equiv 1 \pmod{310}$. That also means that $n^{121} \equiv n \pmod{310}$ and therefore $n^{121} - n \equiv 0 \pmod{310}$ .
Of course if $n$ is a multiple of 310, then $n^\alpha \equiv 0 \pmod{310}$ for any exponent $\alpha \in \mathbb{Z}^+$. Then $n^{120}$ and $n^{121}$ are also multiples of 310, but guess what, so is $n^{121} - n$.