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.
- 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