Get this book -> Problems on Array: For Interviews and Competitive Programming

**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^{ n } â‰¡ 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:

- Every Carmichael number is
**squarefree**means number which is not divisible by a square greater than 1. - Every Carmichael number has
**at least three different prime factors**. - Small Carmichael numbers are rare: there are only
**2,163**are less than 25,000,000,000. - 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 _{2}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:
**Î˜(log**_{2}N) - Average case time complexity:
**Î˜(log**_{2}N) - Best case time complexity:
**Î˜(log**_{2}N) - 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^{n}- 1 % n = 1

### Further reading

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