# 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(bn) = 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.
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,………