Implementation of Fermat’s Little Theorem in Java

Hey Guys, in this article we will learn about Fermat’s Little Theorem and implement it in Java.

Fermat’s Little Theorem was proposed by the French mathematician Pierre de Fermat. It states that p divides a ^{p − 1} − 1 whenever p is prime and a is an integer not divisible by p.

Fermat’s Little Theorem

If p is prime and a is an integer not divisible by p, then

a ^{p − 1} ≡ 1 (mod p) — 1

Furthermore, for every integer a we have

a ^p ≡ a (mod p) — 2

We will write a Java code to find if Fermat’s Little Theorem holds true for given values of a and p.

Let’s take an example,

a = 3, p = 7
Substituting in Eq 1

⇒ 3^{7 − 1} ≡ 1 (mod 7)

⇒ 3⁶ ≡ 1 (mod 7)

⇒ 729 ≡ 1 (mod 7)
The above congruence is true since 729 mod 7 = 1

Therefore, Fermat’s Little Theorem holds true for given values of a = 3 and p = 7.

Code:

// Java Program to Check Fermat’s Little Theorem
import java.util.*;
class fermat{
  public static void main(String args[]){
    Scanner sc = new Scanner(System.in);
    System.out.println("Enter the value of a: ");
    int a = sc.nextInt();
    System.out.println("Enter the value of p: ");
    int p = sc.nextInt();
    
    checkFermat(a, p);
  }
  static void checkFermat(int a, int p){
    int n = (int) Math.pow(a, p-1) % p;
    if(n==1) System.out.println("Fermat's Little Theorem holds true");
    else System.out.println("Fermat's Little Theorem holds false");
  }
}

Output:

Enter the value of a:
3
Enter the value of p:
7
Fermat's Little Theorem holds true

Modular Multiplicative Inverse using Fermat’s Little Theorem

Fermat’s Little Theorem can also be used to find the modular multiplicative inverse of a number a only if p is a prime number.

Taking Eq 1, a ^{p − 1} ≡ 1 (mod p)

Multiplying a⁻¹ on both sides we get,

a⁻¹ ≡ a ^{p − 2} (mod p)

The value of a ^{p− 2} (mod p) from the above congruence will be the modular multiplicative inverse of a.

Let’s write Java code to find modular multiplicative inverse.

Code:

// Java Program to Find Modular Multiplicative Inverse using Fermat’s Little Theorem
import java.util.*;
class fermatMod{
  public static void main(String args[]){
    Scanner sc = new Scanner(System.in);
    System.out.println("Enter the value of a: ");
    int a = sc.nextInt();
    System.out.println("Enter the value of p: ");
    int p = sc.nextInt();
    
    modularInverse(a, p);
  }
  
  static int checkFermat(int a, int p){
    int n = (int) Math.pow(a, p-1) % p;
    return n;
  }
  
  static void modularInverse(int a, int p){
    if(checkFermat(a, p)!=1) System.out.println("Inverse does not exist");
    else{
      int inverse = (int) Math.pow(a, p-2) % p;
      System.out.println("Modular Multiplicative Inverse is: "+inverse);
    }
  }
}

Output:

Enter the value of a:
3
Enter the value of p:
7
Modular Multiplicative Inverse is: 5