homechevron_rightStudychevron_rightMathchevron_rightAlgebrachevron_rightNumber theory

Fermat primality test

The calculator tests an input number by a primality test based on Fermat's little theorem.

Using this calculator you can find if an input number is Fermat pseudoprime. The calculator uses Fermat primality test, based on Fermat's little theorem. If n is a prime number, and a is not divisible by n, then : a^{n-1} \equiv 1 \pmod n .

PLANETCALC, Fermat primality test

Fermat primality test

Can be prime
 



But, the test does not say an input number is prime or not, even the result is 1. I.e. the converse is not true. if a^{n-1} \equiv 1 \pmod n and a and n are coprime numbers does not mean n is a prime number.
E.g., the test on the number 29341 gives positive results using bases: 3; 5; 7; 11. However this number is not prime, it is the composite Carmichael number: 13 x 37 x 61= 29341.

URL copied to clipboard
Creative Commons Attribution/Share-Alike License 3.0 (Unported) PLANETCALC, Fermat primality test

Comments