Fermat's Little Theorem

    Given a prime number and a positive integer a, Fermat's Little Theorem says that a to the p minus one power is congruent to 1 modulo p. This theorem is a special case of Euler's Theorem involving the important Euler totient function. Fermat's Little Theorem takes care of solving linear congruences with prime modulus and provides a formula for finding the solution. These ideas are illustrated below with proofs and examples. Fermat's Little Theorem has many application in cryptology including factorization of integers.  

Proposition (Fermat's Little Theorem) If is prime and is a positive integer, then  

    (i) if then and
    
    (ii)
    
    Proof. (i): Consider the integers: ..., These integers have the following property: if with then because Therefore, these integers must be congruent modulo to taken in some order. Multiplying all of these congruence together we find that
    


and since we have as desired.
    (ii): If then by (i) we have and so . If then and so in either case we have as desired.

Example (Fermat's Little Theorem - Illustrating the Proof of) Illustrate why

    Solution. Fermat's Little Theorem states that To illustrate why this is true,  let and Notice that and


    
Consequently, we have,



Whence,

Example (Fermat's Little Theorem - Illustrating How to Use) Use Fermat Little Theorem to show that



when and are distinct primes.

    Solution. By Fermat's Little Theorem we have and ;  thus we consider the system
    


Using the Chinese Remainder Theorem we have,
    


Finally since ,  we have as desired.

Example (Fermat's Little Theorem - Converse Is Not True) Compute modulo to show that the converse of Fermat's Little Theorem is not true.

    Solution. Since , if the converse of Fermat's Little Theorem were true then would be prime. However, and so the converse of Fermat Little Theorem is not true.

Proposition (Inverse Modulo a Prime) If is a prime and is an integer such that then is an inverse of modulo     

    Proof. By Fermat's Little Theorem we know that and so Therefore,   is an inverse of modulo

Example (Inverse Modulo a Prime) Find the inverse of modulo

    Solution. Since and We see that and so is the inverse of modulo

Proposition (Linear Congruence Modulo a Prime) If and are positive integers and is a prime with then the solutions of the linear congruence are the integers such that

    Proof. Since is the inverse of modulo we have



by Fermat's Little Theorem.  

Example (Linear Congruence Modulo a Prime) Solve the two linear congruences and

    Solution. By Fermat's Little Theorem we have and ; so is the solution to and is the solution to

• print this page
• pages linking here
• related pages

Cite this as:
Fermat Little Theorem
Published by Library of Math -- Online math organized by subject into topics.
Written by Smith, David A.
http://www.libraryofmath.com/fermat-little-theorem.html