# 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

that satisfies the congruencenbfor all positive integers^{ n – 1 }≡ 1 (mod n)bwithgcd(b, n) = 1is 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.

- b = 1

gcd(1, 6) = 1

1^{ 6 – 1 }mod 6 = 1 mod 6 = 1

**∴**b = 1 satisfies the conditions - 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**

- Start.
- Read n.
- 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”. - 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,………

## Leave a Reply