Carmichael Number

Carmichael Number is an odd composite number which follows the following condition applicable in Fermat's Little Theorem.

Fermat's little theorem states that if p is prime and a is not a multiple of p, then a ^{p - 1} ≡ 1 mod p. Stated theorem gives an achievable way to detect non-primee. For a > 1, we write F(a) for the set of positive integers n satisfying a ^{n - 1} ≡ 1 mod n. By Fermat’s theorem, F(a) includes all primes that are not divisors of a. If n ∈ F(a), then gcd(a, n) = 1, since, clearly, gcd (a ^{n - 1} , n) = 1. Also, a ⁿ ≡ a mod n; the reverse implication is true provided that a and n are coprime. A composite number n belonging to F(a) is called a Fermat Pseudoprimes or Absolute Fermat Pseudoprimes. A number n that is a-pseudoprime for all a coprime to n is called a Carmichael number. A Carmichael number will pass a Fermat primality test to every base a relatively prime to the number, even though it is not actually prime. These numbers are named after there inventor Robert Daniel Carmichael. This above theory was proposed in 1912.

Carmichael Number follows the following condition:
m^n-1 % n = 1,

m^(n-1) % n == 1

for all m ranging from 1 to n such that m and n are relatively prime.

Interesting Facts about Carmichael Numbers

Few Interesting Facts about Carmichael Numbers are:

1. Every Carmichael number is squarefree means number which is not divisible by a square greater than 1.
2. Every Carmichael number has at least three different prime factors.
3. Small Carmichael numbers are rare: there are only 2,163 are less than 25,000,000,000.
4. Recently, Richard Pinch has found that there are still only 246,683 Carmichael numbers below 10,000,000,000,000,000.

Algorithm

• Step 1 : Input the number which is to be checked whether it is Carmichael Number or not.
• Step 2 : Iterate through all numbers from 2 to n and for every relatively prime number, check if its (n-1)th power MOD n is 1 or not, if not then respective number is not carmichael number.
• Step 3 : Stop.

Example Illustrated

Here, user have given input number 4 whether it is Carmichael Number or not.
As per according to steps mentioned in algorithm, step 2 proposes that iterate through all numbers starting from 2 to n (here till 4 because given unsigned integer is 4) and for every relatively prime number check mentioned conditions (steps of algorithm) and if it get violets, the given number is not Carmichael Number.
Iteration for b = 1
when n = 4, b = 1
Condition: 1^{4 - 1} = 1 (condition satisfied)
Iteration for b = 2
when n = 4, b = 2
Condition: 2^{4 - 1} = 0 which is not equal to 1 hence (condition not satisfied i.e calculatePower(i, number_ - 1, number_) != 1 is true) which in turn returns boolean value false from the calculateCarmichaelNumber() funtion.
Analyzing time Complixity of implemented algorithm, recursive frames are stacked on the memory by giving recursive call to calculate the power of a respective input base, incremented by one till we get base and input-number(number_) relatively prime, hence the time complexity is given as log₂n.

Result : Output: 4 number is not a Carmichael Number because condition for iteration b = 2 is violeted.

Implementation

#include<iostream>
class CarmichaelNumber
{
public:
    CarmichaelNumber(unsigned int number_) : number_(number_){}
    unsigned int calculateGCD(unsigned int num1, unsigned int num2);
    unsigned int calculatePower(unsigned int base, unsigned int exponent, unsigned int MOD);
    bool calculateCarmichaelNumber();
private:
    unsigned int number_;
};
unsigned int CarmichaelNumber::calculateGCD(unsigned int num1, unsigned int num2)
{
    //Euclidean algorithm
    if (num1 == 0)
        return num2;
    return calculateGCD(num2 % num1, num1);
}
unsigned int CarmichaelNumber::calculatePower(unsigned int base, unsigned int exponent, unsigned int MOD)
{
    if (exponent == 0)
        return 1;
    unsigned int ans = calculatePower(base, exponent / 2, MOD) % MOD;
    ans = (ans * ans) % MOD;
    if (exponent % 2 == 1)
        ans = (ans * base) % MOD;
    return ans;
}
bool CarmichaelNumber::calculateCarmichaelNumber()
{
    for (int i = 2; i < number_; i++)
    {
        // If i found to be relatively prime to n then
        if (calculateGCD(i, number_) == 1 and calculatePower(i, number_ - 1, number_) != 1)
           return false;
    }
    return true;
}
int main()
{
    unsigned int valueOfN;
    std::cout << "\nEnter the Number to check whether it is Carmichael Number : ";
    std::cin >> valueOfN;
    CarmichaelNumber aCarmichaelNumber(valueOfN);
    bool result = aCarmichaelNumber.calculateCarmichaelNumber();
    if (result)
    {
        std::cout << "\nNumber " << valueOfN << " is a Carmichael Number.\n";
    } else
    {
        std::cout << "\nNumber " << valueOfN << " is not a Carmichael Number.\n";
    }
    return 0;
}

Sample Input

Enter the Number to check whether it is Carmichael Number : 4

Sample Output

Number 4 is not a Carmichael Number.

Complexity

The time and space complexities of specifying whether number is Carmechael Number or not are:

• Worst case time complexity: Θ(log2N)
• Average case time complexity: Θ(log2N)
• Best case time complexity: Θ(log2N)
• Space complexity: Θ(n)

where N is the input.

Applications

• Carmichael Numbers have significant role in Fermat's Method of Primality Checking following condition
  where,
  n is a prime number, then for every m, 1 < m < n - 1,
  aⁿ - 1 % n = 1

Further reading

For learning different type of numbers present in number theory, read:

• Bell Numbers