- #1

Math100

- 768

- 207

- Homework Statement
- Use Fermat's theorem to verify that ## 17 ## divides ## 11^{104}+1 ##.

- Relevant Equations
- None.

Proof:

Fermat's theorem states:

Let ## p ## be a prime and suppose that ## p\nmid a ##. Then ## a^{p-1}\equiv 1\pmod {p} ##.

By using Fermat's theorem, we will prove that ## 17 ## divides ## 11^{104}+1 ##.

Suppose ## a=11, p=17 ## and ## p\nmid a ##.

Then ## 11^{17-1}\equiv 1\pmod {17}\implies 11^{16}\equiv 1\pmod {17} ##.

Observe that ## 104=16\cdot 6+8 ##.

This means

\begin{align*}

&11^{104}\equiv 11^{16\cdot 6+8}\equiv [(11^{16})^{6}\cdot 11^{8}]\pmod {17}\\

&\equiv [1^{6}(11^{2})^{4}]\pmod {17}\equiv 16\pmod {17}.\\

\end{align*}

Thus ## 11^{104}+1\equiv 0\pmod {17}\implies 17\mid (11^{104}+1) ##.

Therefore, ## 17 ## divides ## 11^{104}+1 ##.

Fermat's theorem states:

Let ## p ## be a prime and suppose that ## p\nmid a ##. Then ## a^{p-1}\equiv 1\pmod {p} ##.

By using Fermat's theorem, we will prove that ## 17 ## divides ## 11^{104}+1 ##.

Suppose ## a=11, p=17 ## and ## p\nmid a ##.

Then ## 11^{17-1}\equiv 1\pmod {17}\implies 11^{16}\equiv 1\pmod {17} ##.

Observe that ## 104=16\cdot 6+8 ##.

This means

\begin{align*}

&11^{104}\equiv 11^{16\cdot 6+8}\equiv [(11^{16})^{6}\cdot 11^{8}]\pmod {17}\\

&\equiv [1^{6}(11^{2})^{4}]\pmod {17}\equiv 16\pmod {17}.\\

\end{align*}

Thus ## 11^{104}+1\equiv 0\pmod {17}\implies 17\mid (11^{104}+1) ##.

Therefore, ## 17 ## divides ## 11^{104}+1 ##.