Derive ## a^{7}\equiv a\pmod {42} ## for all ## a ##

[Math100]

Homework Statement

Derive the following congruence:
$a^{7}\equiv a\pmod {42}$ for all $a$.

Relevant Equations

None.

Proof:

Observe that $42=6\cdot 7=2\cdot 3\cdot 7$.
Applying the Fermat's theorem produces:
$a\equiv 1\pmod {2}, a^{2}\equiv 1\pmod {3}$ and $a^{6}\equiv 1\pmod {7}$.
Thus
\begin{align*}
&a\equiv 1\pmod {2}\implies a^{6}\equiv 1\pmod {2}\implies a^{7}\equiv a\pmod {2}\\
&a^{2}\equiv 1\pmod {3}\implies a^{6}\equiv 1\pmod {3}\implies a^{7}\equiv a\pmod {3}\\
&a^{6}\equiv 1\pmod {7}\implies a^{7}\equiv a\pmod {7}.\\
\end{align*}
Therefore, $a^{7}\equiv a\pmod {42}$ for all $a$.

 

[fresh_42]

Fermat's theorem doesn't apply to all $a$.

 

[Math100]

Then what should we apply here without the Fermat's theorem?

 

[fresh_42]

Then what should we apply here without the Fermat's theorem?

You have used Fermat's theorem in the version $\operatorname{gcd}(a,p)=1.$
The general version says $a^p\equiv a\pmod{p}.$ Try that one.

 

[Math100]

Proof:

Observe that $42=6\cdot 7=2\cdot 3\cdot 7$.
Applying the Fermat's theorem produces:
$a^{2}\equiv a\pmod {2}, a^{3}\equiv a\pmod {3}$ and $a^{7}\equiv a\pmod {7}$.
Thus
\begin{align*}
&a^{2}\equiv a\pmod {2}\implies a^{6}\equiv a^{3}\pmod {2}\\
&\implies a^{7}\equiv a^{4}\pmod {2}\implies a^{7}\equiv (a^{2}\cdot a^{2})\pmod {2}\implies a^{7}\equiv a\pmod {2}\\
&a^{3}\equiv a\pmod {3}\implies a^{6}\equiv a^{2}\pmod {3}\\
&\implies a^{7}\equiv a^{3}\pmod {3}\implies a^{7}\equiv a\pmod {3}.\\
\end{align*}
Since $2, 3, 7$ are relatively prime to each other,
it follows that $a^{7}\equiv a\pmod {2\cdot 3\cdot 7}\implies a^{7}\equiv a\pmod {42}$.
Therefore, $a^{7}\equiv a\pmod {42}$ for all $a$.

 

[fresh_42]

Right. I would write the congruences in one line, e.g.
$a^3\equiv a \pmod{3}\Longrightarrow a^7\equiv a^3\cdot a^3 \cdot a\equiv a\cdot a \cdot a \equiv a^3\equiv a\pmod{3}.$

 

[Math100]

Right. I would write the congruences in one line, e.g.
$a^3\equiv a \pmod{3}\Longrightarrow a^7\equiv a^3\cdot a^3 \cdot a\equiv a\cdot a \cdot a \equiv a^3\equiv a\pmod{3}.$

This is way better.