Unraveling the complex and diverse nature of numbers has always been a fascinating ordeal for me; that is what makes and keeps me interested in the world of mathematics. Finding out new number patterns and the relationship between numbers is nothing short of a new discovery; that is how my interest into learning more about and exploring Fermat's Little Theorem came about.
INTRODUCTION OF FERMAT'S LITTLE THEOREM
Pierre de Fermat was a French mathematician whose contribution to analytic geometry and calculus are duly noted. But, what made him and still makes him a relevant mathematic figure is one of his well and widely known theorem; Fermat's Little Theorem. This theorem was first stated by him in a letter to a fellow friend on October 18, 1640, but what made it interesting is that he gave no proof of this theorem. This is how the theorem became well-known. It aroused mathematicians who came across this theorem to prove it. Though, this theorem has now been proved many times by many ways what still keeps it interesting is its real world application in the RSA security key system. In this exploration, I am going to focus mainly on the proofs of Fermat's Little Theorem.
Fermat's Little Theorem1 states that if 'p' is a prime number and 'a' is any integer, then,
ap-1 ≡ 1 (mod p) (1)
ap ≡ a (mod p) (2)
By multiplying equation ap-1 ≡ 1 (mod p) with 'a', we can get equation the equation ap ≡ a (mod p)
An example of how this theorem works is as follows:
In order to really understand how this theorem works, it is important to know some definitions and preliminary lemmas that will aid me in the proofs of Fermat's Little theorem.
SOME DEFINITIONS AND THEOREMS
Definition 1: Defining congruence symbol
Let a, b, and m be integers, with m > 0. If m | (a - b), then we say a is congruent to b (mod m) and hence:
a ≡ b (mod m)
Hence, this is just another notation of congruency and of stating the modulus.
Lemma 1: Cancellation Property of Congruence.
Let a, b and c be integers,
If ac ≡ bc (mod m) and greatest common denominator, gcd is (c,m) = 1, then a ≡ b (mod m).
This just shows how as c and m are common to both equations, they can be cancelled out to let a ≡ b (mod m).
Lemma 2: Binomial Theorem
For any prime p,
This can be
Another way of interpreting this lemma is:
INITIAL BINOMIAL THEOREM PROOF FOR FERMAT'S LITTLE THEOREM
The binomial theorem proof for Fermat's Little theorem also uses induction in order to first prove the lemma which is then used to prove the theorem.
The first step, that 0 p ≡ 0 (mod p), is true for modular arithmetic because it is true for integers. Next, we must show that if the theorem is true for a = k, then it is also true for a = k+1. For this induction, lemma 2 is required.
Proof. Assume kp ≡ k...