# Fermat's Little Theorem/Corollary 3

Jump to navigation
Jump to search

## Contents

## Corollary to Fermat's Little Theorem

Let $p^k$ be a prime power for some prime number $p$ and $k \in \Z_{\gt 0}$.

Then:

- $\forall n \in \Z_{\gt 0}: n^{p^k} \equiv n \pmod p$

## Proof

The proof proceeds by induction.

For all $k \in \Z_{\ge 1}$, let $P \paren {k}$ be the proposition:

- $\forall n \in \Z_{\gt 0}: n^{p^k} \equiv n \pmod p$

### Basis for the Induction

$P \paren {1}$ is the case:

- $\forall n \in \Z_{\gt 0}: n^p \equiv n \pmod p$

which follows from the corollary 1 to Fermat's Little Theorem.

This is the basis for the induction.

### Induction Hypothesis

Now it needs to be shown that, if $P \paren{k-1}$ is true, where $k \ge 2$, then it logically follows that $P \paren {k}$ is true.

So this is the induction hypothesis:

- $\forall n \in \Z_{\gt 0}: n^{p^{k - 1} } \equiv n \pmod p$

from which it is to be shown that:

- $\forall n \in \Z_{\gt 0}: n^{p^k} \equiv n \pmod p$

### Induction Step

This is the induction step:

For any $n \in \Z_{\gt 0}$ then:

\(\displaystyle n^{p^k}\) | \(=\) | \(\displaystyle \paren {n^{p^{k - 1} } }^p\) | |||||||||||

\(\displaystyle \) | \(\equiv\) | \(\displaystyle n^{p^{k - 1} } \pmod p\) | Corollary 1 to Fermat's Little Theorem | ||||||||||

\(\displaystyle \) | \(\equiv\) | \(\displaystyle n \pmod p\) | Induction Hypothesis |

$\blacksquare$