The fermat's little theorem

The fermat's little theorem

1. By recurrence

   Let \(a \in \mathbb{Z}\) be an integer and \(p \in \mathbb{P}\) a prime number.

   Let show that the following statement \((S_a)\) is true:

   $$ \forall a \in \mathbb{Z}, \enspace p \in \mathbb{P}, $$
   $$ a^p \equiv a \hspace{0.2em} \bigl[p\bigr] \qquad (S_a) $$

   1. First term calculation

      Let verify if is true for the first term, that is to say for \( a = 0 \).

      $$ 0^p \hspace{0.2em} \equiv \hspace{0.2em} 0 \hspace{0.2em} \bigl[p\bigr] $$

      \((S_0)\) is true.

   2. Inductive step

      1. In the natural numbers set\(: \mathbb{N} \)

         Let \( k \in \mathbb{N} \) be a natural number.

         Let us assume that \((S_k)\) is true for all \( k \).

         $$ k^p \equiv k \hspace{0.2em} \bigl[p\bigr] \qquad (S_{k}) $$

         We will verify that is also the case for \((S_{k + 1})\).

         $$ (k+1)^p \equiv k+1 \hspace{0.2em} \bigl[p\bigr] \qquad (S_{k + 1}) $$

         Let us calculate \( (k+1)^p\).

         With the Newton's binomial , we know that:

         $$\forall n \in \mathbb{N}, \enspace \forall (a, b) \in \hspace{0.04em} \mathbb{R}^2,$$

         $$ (a + b)^n = \sum_{p = 0}^n \binom{n}{p} a^{n-p}b^p $$

         So,

         $$ (k+1)^p = k^p + \sum_{i = 1}^{p-1} \binom{p}{i} k^{p-i} + 1 \qquad (1) $$

         Well, for all \( (p, i) \), with \( 1 \leqslant i \leqslant p \) we can apply the binomial's pawn formula :

         $$ \binom{p}{i} = \frac{p}{i} \binom{p-1}{i-1} $$
         $$ i \binom{p}{i} = p \binom{p-1}{i-1} $$

         But, we know by the Gauss' theorem that:

         $$ \forall (a, b, c) \in \hspace{0.04em} \mathbb{Z}^3, \enspace (a \mid bc) \text{ and } (a \wedge b = 1) \hspace{0.2em} \Longrightarrow \hspace{0.2em} a \mid c $$

         In our case,

         $$ \forall i \in \hspace{0.04em} 1 \leqslant i \leqslant (p-1),$$
         $$ p \mid i\binom{p}{i} \text{ and } p \wedge i = 1 \hspace{0.2em} \Longrightarrow \hspace{0.2em} p / \binom{p}{i} $$

         If \( p \) divides the \( \binom{p}{i} \) binom, then \( p \) also divides the central member of \( (1) \).

         $$ (k+1)^p = k^p + \enspace \underbrace{\sum_{i = 1}^{p-1} \binom{p}{i} k^{p-i} } _{ = \hspace{0.2em} pQ, \hspace{0.4em} with \hspace{0.4em} Q \hspace{0.1em} \in \hspace{0.04em} \mathbb{N} } \hspace{0.1em} + 1 \qquad (1) $$

         So,

         $$ \sum_{i = 1}^{p-1} \binom{p}{i} k^{p-i} \equiv 0 \bigl[p\bigr] $$

         And as our recurrence hypothesis is:

         $$ k^p \equiv k \hspace{0.2em} \bigl[p\bigr] \qquad (S_k) $$

         These are all the congruences for the \( (k+1)^p \) calculation:

         $$ (k+1)^p = \underbrace{ k^p } _{ \equiv \hspace{0.2em} k \hspace{0.2em} \bigl[p\bigr] } + \enspace \underbrace{\sum_{i = 1}^{p-1} \binom{p}{i} k^{p-i} } _{ \equiv \hspace{0.2em} 0 \hspace{0.2em} \bigl[p\bigr] } \hspace{0.2em} + 1 $$

         We then have by addition of the congruences :

         $$ (k+1)^p \equiv k + 1 \bigl[p\bigr] \qquad (S_{k + 1}) $$

         Thus, \((S_{k + 1})\) est vraie.

      2. In the relative numbers set\(: \mathbb{Z} \)

         Here, we have to prove it in the contrary direction, to verify if it is still true inside the \( \mathbb{Z}\) set.

         In other words, let verify that \((P_{k - 1})\) is true.

         $$ (k-1)^p \equiv k - 1 \bigl[p\bigr] \qquad (P_{k - 1}) $$

         Let us calculate \( (k-1)^p \).

         $$ (k-1)^p = k^p + \sum_{i = 1}^{p-1} (-1)^i \binom{p}{i} k^{p-i} + (-1)^p \qquad (P_{k - 1}) $$

         \(p\) being a prime number by hypothesis, it will always be odd, and then:

         $$ (k-1)^p = k^p + \sum_{i = 1}^{p-1} (-1)^i \binom{p}{i} k^{p-i} -1 \qquad (1') $$

         Likewise, if \( p \) divise the \( \binom{p}{i} \) binom, then \( p \) also divides the central member of \( (1') \) :

         $$ (k-1)^p = k^p + \enspace \underbrace{\sum_{i = 1}^{p-1} (-1)^i \binom{p}{i} k^{p-i} } _{ = \hspace{0.2em} pQ, \hspace{0.4em} with \hspace{0.4em} Q \hspace{0.1em} \in \hspace{0.04em} \mathbb{Z} }\hspace{0.2em} - 1 \qquad (1') $$

         Even if this central member contains an alternance of positive and negative numbers, its general quotient \( Q \) remains inside the \( \mathbb{Z} \) set.

         We will also, like previously:

         $$ k^p \equiv k \hspace{0.2em} \bigl[p\bigr] \qquad (S_k) $$

         So these are all the congruences for the \( (k-1)^p \) calculation:

         $$ (k-1)^p = \underbrace{ k^p } _{ \equiv \hspace{0.2em} k \hspace{0.2em} \bigl[p\bigr] } + \enspace \underbrace{\sum_{i = 1}^{p-1} (-1)^i \binom{p}{i} k^{p-i} } _{ \equiv \hspace{0.2em} 0 \hspace{0.2em} \bigl[p\bigr] } \hspace{0.2em} - 1 $$

         And finally,

         $$ (k-1)^p \equiv k - 1 \bigl[p\bigr] \qquad (P_{k - 1}) $$

         \((P_{k - 1})\) est vraie.

   3. Conclusion

      The statement \((S_a)\) is true for its fisrt term \(a_0 = 0\) and it's hereditary from terms to terms for all \(k \in \mathbb{Z}\), upwards and downwards.

      By the recurrence principle, that statement is true for all \(a \in \mathbb{Z}\).

      
      

      And finally,

      $$ \forall a \in \mathbb{Z}, \enspace p \in \mathbb{P}, $$
      $$ a^p \equiv a \hspace{0.2em} \bigl[p\bigr] \qquad \bigl(\text{Fermat's little theorem} \bigr) $$

   This therefore means that:

   $$ p \mid (a^p - a) \Longrightarrow p \mid a(a^{p - 1} - 1) $$

   Now, we know from the Gauss' theorem that:

   $$ \forall (a, b, c) \in \hspace{0.04em} \mathbb{Z}^3, \enspace (a \mid bc) \text{ and } (a \wedge b = 1) \hspace{0.2em} \Longrightarrow \hspace{0.2em} a \mid c $$

   So on the other hand, if \((a \land p = 1)\), then:

   $$ p \mid (a^{p - 1} - 1) $$

   And also,

   $$ a^{p - 1} - 1 \equiv 0 \hspace{0.2em} \bigl[p\bigr] $$

   And as a result,

   $$ \forall a \in \mathbb{Z}, \enspace p \in \mathbb{P}, \enspace (a \land p = 1), $$
   $$ a^{p - 1} \equiv 1 \hspace{0.2em} \bigl[p\bigr] $$