Java program to check if a number is a Carmichael number

Hello all, In this article, you will learn about Carmichael numbers and write a Java program to check if a given number is a Carmichael number or not.

Carmichael Number Checker in Java

What is a Carmichael number?

Definition:

A composite integer n that satisfies the congruence b ^{n – 1}  ≡ 1 (mod n) for all positive integers b with gcd(b, n) = 1 is called a Carmichael number. 

Simply put, a number n is Carmichael if it satisfies b ^{n – 1} mod n = 1 for all values of b ranging from 1 to n such that b and n are relatively prime / gcd(b, n) = 1.

It is very rare to find small Carmichael numbers. In fact, the smallest Carmicheal number is 561.

Let’s take an example,

We will check if 6 is a Carmicheal number or not. From b = 1 to b = 6 we will see if gcd(b, 6) = 1 and b ^{6 – 1} mod 6 = 1. If all values of b satisfy both the conditions then we can say that 6 is a Carmichael number.

1. b = 1
   gcd(1, 6) = 1
   1 ^{6 – 1} mod 6 = 1 mod 6 = 1
   ∴ b = 1 satisfies the conditions
2. b = 2
   gcd(2, 6) = 2
   2 ^{6 – 1} mod 6 = 32 mod 6 = 2
   ∴ b = 2 does not satisfy both the conditions for a Carmichael number.

Therefore, n = 6 is not a Carmicheal number.

Let’s implement this in Java.

Algorithm

1. Start.
2. Read n.
3. Iterate from 2 to n and for every iteration check if gcd(b, n) = 1 and  b ^{n – 1} mod n = 1. If all the iterations satisfy the given conditions print “n is a Carmicheal number” else print “n is not a Carmicheal number”.
4. Stop.

Note: We can eliminate 1 from the iterations as gcd(1, n) = 1 as well as 1 mod n = 1.

Code:

import java.util.*;
class Carmichael{
  
  // Method to find GCD of b and n
  static int gcd(int b, int n){
    if (n == 0) 
      return b;     
    return gcd(n, b % n);  
  }
  
  // Method to find b^(n-1) mod n
  static int power(int b, int exp, int n){
    if(exp == 0)
      return 1;
    int result = power(b, exp/2, n) % n;
        result = (result * result) % n;
    if (exp % 2 == 1)
      result = (result * b) % n;
    return result;
  }
  
  // Method to check if gcd(b, n)=1 and b^(n-1) mod n = 1
  static boolean checkCarmicheal(int n){
    for(int b = 2; b<=n; b++){
      if(gcd(b, n)==1 && power(b, n-1, n)!=1)
        return false;
    }
    return true;
  }
  
  public static void main(String args[]){
    Scanner sc = new Scanner(System.in);
    System.out.println("Enter the Number: ");
    int n = sc.nextInt();
    if(checkCarmicheal(n)) System.out.println(n+" is a Carmichael number");
    else System.out.println(n+" is not a Carmichael number");
  }
}

Output:

Enter the Number:
6
6 is not a Carmichael number

Enter the Number:
561
561 is a Carmichael number

For your reference, these are the initial Carmichael numbers.
561, 1105, 1729, 2465, 2821, 6601,………

Also read: Java Program To Check A Number Is Prime or Not