Derive the following congruence....

[Math100]

Homework Statement

Derive the following congruence:
$a^{21}\equiv a\pmod {15}$ for all $a$.
[Hint: By Fermat's theorem, $a^{5}\equiv a\pmod {5}$.]

Relevant Equations

None.

Proof:

Observe that $15=3\cdot 5$.
Applying the Fermat's theorem produces:
$a^{3}\equiv a\pmod {3}$ and $a^{5}\equiv a\pmod {5}$.
Thus
\begin{align*}
&(a^{3})^{7}\equiv a^{7}\pmod {3}\implies a^{21}\equiv [(a^{3})^{2}\cdot a]\pmod {3}\implies a^{21}\equiv a\pmod {3}\\
&(a^{5})^{4}\equiv a^{4}\pmod {5}\implies a^{20}\equiv a^{4}\pmod {5}\implies a^{21}\equiv a\pmod {5}.\\
\end{align*}
Therefore, $a^{21}\equiv a\pmod {15}$ for all $a$.

 

[fresh_42]

Maybe you should write $a^{21}\equiv a^7\equiv a^3\cdot a^3 \cdot a\equiv a\cdot a\cdot a\equiv a^3\equiv a\pmod{3}.$ Or at least $(a^3)^2\cdot a\equiv a^2\cdot a\equiv a^3\equiv a\pmod{3}.$

I stumbled upon $a^6\cdot a\equiv a\pmod{3}$ which was not immediately clear (to me).

But again: might be due to local time.

 

[Math100]

Maybe you should write $a^{21}\equiv a^7\equiv a^3\cdot a^3 \cdot a\equiv a\cdot a\cdot a\equiv a^3\equiv a\pmod{3}.$ Or at least $(a^3)^2\cdot a\equiv a^2\cdot a\equiv a^3\equiv a\pmod{3}.$

I stumbled upon $a^6\cdot a\equiv a\pmod{3}$ which was not immediately clear (to me).

But again: might be due to local time.

Sorry, it's my fault.

 

[fresh_42]

Sorry, it's my fault.

Not at all. I'm just a little bit slow at night time. That's not your fault. It only proves that the Earth is not flat.