- #1

Math100

- 757

- 206

- 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 ##.

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 ##.