How to prove that $42|a^7-a$?

Question

Suppose we are given a number $a \in \mathbb{Z}$ prove that $42|a^7-a$.

I'm not too sure how to start any ideas?

Answer 1

Reduce $a^7-a$ mod 2,3, and 7 (the factors of 42) and show in each case that you get 0, so that 2,3, and 7 are all factors of $a^7-a$

Answer 2

Use Fermat's little theorem mod 2, 3 and 7 since these are the prime factors of 42.

Answer 3

First by the Fermat's little theorem we have $$a^7\equiv a \bmod 7$$ so $7|a^7-a$. On the other hand by applying the same theorem it is easy to see that $$2|a^7-a$$ and $$3|a^7-a \quad*$$

Proof of $3|a^7-a$.

If a is a multiple of $3$, * is clear. So suppose that $\gcd (a,3)=1$. Then Fermat's theorem implies that $$a^2\equiv a\bmod 3\implies a^6\equiv a^3\equiv a^2\times a\equiv a\times a\equiv a \bmod 3 \implies a^7\equiv a^2 \equiv a\bmod 3$$ Could you repeat this for the other case?

Answer 4

Hint $\ $ It follows immediately from a slight generalization of $\color{#c00}{\rm Fermat's}$ little Theorem:

• $ $ If $\ p\!-\!1\mid e\!-\!1\,$ then $\, {\rm mod}\ p\!:\ a^e\equiv a.\,$ Indeed, it is true if $\,a\equiv 0,\,$ and if $\,a\not\equiv 0\,$ then $\,e\, =\, 1+k(p\!-\!1)\ $ so $\ a^e\equiv a (\color{#c00}{a^{p-1}})^k\overset{\rm\color{#c00}{ Fermat}}\equiv a \color{#c00}{(1)}^k\equiv a,\ $ so $\ a^e\!-a\equiv a-a\equiv 0.$

In your case we have $\,2\!-\!1,\,3\!-\!1,\,7\!-\!1$ all divide $\,e\!-\!1 = 7\!-\!1,\,$ so $\,a^7-a\,$ is divisible by $\,2,3,7,\,$ therefore it is also divisible by their lcm = product $ = 42.$

Remark $\ $ Above we used basic congruence rules. The key idea generalizes, see Korselt's Carmichael Number Criterion.

Answer 5

In fact, $42$ is the largest integer that divides $a^7-a$ for all $a\in\Bbb Z$.

$a^7-a=a\left(a^6-1\right)=a\left(a^3-1\right)\left(a^3+1\right)$

$=a(a-1)\left(a^2+a+1\right)(a+1)\left(a^2-a+1\right)$

$a-1,a,a+1$ are three consecutive integers, so $2,3\mid a^7-a$.

Also by Fermat's Little theorem $7\mid a^7-a$. Therefore $2\cdot 3\cdot 7=42\mid a^7-a$.

$2^7-2=42\cdot 3$ and $3^7-3=42\cdot 52$. But $\gcd(3,52)=1$,

so it follows that $42$ is the largest integer that divides $a^7-a$ for all $a\in\Bbb Z$.