Proof using Mod

Question

How can you prove that:

$$a^7\equiv a\:(\text{mod } 42)$$

I haven't been given any other information other than to use Fermat's theorem.

Answer 1

Hint $\rm\,\ x\!-\!1\mid x^n\!-\!1\:\Rightarrow\:a^{p-1}\!-\!1\mid a^{n(p-1)}\!-\!1\:\Rightarrow\:p\mid a^p\!-\!a\mid a^{1+\color{#C00}{n(p-1)}}\!-\!a\,\ $ by little Fermat.

So if $\rm\:p_i\:$ are distinct primes then $\rm\ p_i\!-\!1\mid \color{#C00}{m\!-\!1}\:\Rightarrow\: p_1\cdots p_k\mid a^m - a$

Answer 2

There are two versions of Fermat's Theorem.

Version $1$: If $a$ is not divisible by $p$, then $a^{p-1}\equiv 1\pmod{p}$.

Version $2$: For any $a$, $a^p\equiv a\pmod p$.

The more common version is Version $1$. From it, you can easily deduce Version $2$. For if $a$ is not divisible by $p$, then $a^{p-1}\equiv 1\pmod{p}$. Multiplying by $a$, we get that $a^p\equiv a \pmod{p}$. On the other hand, if $a$ is divisible by $p$, we have that both $a^p$ and $a$ are congruent to $0$ modulo $p$, and therefore are congruent to each other.

We omit the proof that Version $2$ implies Version $1$. It is straightforward.

Using Version $2$, we find that for all $a$, $$a^7 \equiv a\pmod{7}.\tag{$1$}$$

Now work modulo $2$. It is hardly necessary to use machinery. If $a$ is odd, then so is $a^7$, and if $a$ is even, then so is $a^7$. We conclude that for all $a$, $$a^7 \equiv a\pmod{2}.\tag{$2$}$$

Now work modulo $3$. We can do a three-cases verification that $a^7\equiv a\pmod{3}$ for all $a$. Or else we can use Fermat's Theorem. If $a$ is divisible by $3$, then $a^7$ and $a$ are congruent to $0$ modulo $3$, so they are conruent to each other. If $a$ is not divisible by $3$, then $a^2\equiv 1\pmod{3}$, and therefore $a^6\equiv 1\pmod{3}$, and therefore $a^7\equiv a \pmod{3}$. we conclude that for all $a$ $$a^7 \equiv a\pmod{3}.\tag{$3$}$$

So $7$, $2$, and $3$ each divide $a^7-a$. Since they are pairwise relatively prime, it follows that their product $42$ divides $a^7-a$ for all $a$. This is what we wanted to prove.

Answer 3

Directly:

$$a^7=a\pmod{42}\Longleftrightarrow \,\,\exists \,k\in\Bbb Z\,\,\,s.t.\,\,\,a^7-a=42k\,\,,\,$$

But

$$(1)\;\;\;\;\text{If}\,a=0\pmod{42}\,\,,\,\text{ then the claim is obvious. Otherwise:}$$

$$a^7=a\pmod{42}\Longrightarrow a^6=1\pmod{42}\Longleftrightarrow \exists\,k\in\Bbb Z\,\,s.t.\,\,a^6-1=42k$$

But:

$$a^6-1=(a^3-1)(a^3+1)=(a-1)(a^2+a+1)(a+1)(a^2-a+1)$$

Now check all the cases and verify the above is always divisible by $\,2\,,\,3\,,\,and\,\,7\,$

Answer 4

Note first $42 = 2\cdot 3\cdot 7$.

By Fermat's theorem, $a^2 \equiv a$ (mod 2). Hence $a^3 \equiv a^2 \equiv a$ (mod $2$), etc. Hence $a^7 \equiv a$ (mod $2$).

By Fermat's theorem, $a^3 \equiv a$ (mod 3). Hence $a^7 = (a^3)^2a \equiv a^3 \equiv a$ (mod $3$).

By Fermat's theorem, $a^7 \equiv a$ (mod $7$).

Therefore $a^7 \equiv a$ (mod $42$).

Answer 5

Hint:

Use Fermat's Theorem and the Chinese Remainder Theorem.