Carmichael numbers {numbers}

Carmichael Numbers

Description

Checks whether a number is a Carmichael number.

Usage

  carmichael(n)

Arguments

n

natural number

Details

A natural number n is a Carmichael number if it is a Fermat pseudoprime for every a, that is a^(n-1) = 1 mod n, but is composite, not prime.

Here the Korselt criterion is used to tell whether a number n is a Carmichael number.

Value

Returns TRUE or FALSE

Note

There are infinitely many Carmichael numbers, specifically there should be at least n^(2/7) Carmichael numbers up to n (for n large enough).

References

R. Crandall and C. Pomerance. Prime Numbers - A Computational Perspective. Second Edition, Springer Science+Business Media, New York 2005.

See Also

primeFactors

Examples

carmichael(561)  # TRUE

## Not run: 
for (n in 1:100000)
    if (carmichael(n)) cat(n, '\n')
##    561     2821    15841    52633 
##   1105     6601    29341    62745 
##   1729     8911    41041    63973 
##   2465    10585    46657    75361 

## End(Not run)