Fermat's little theorem (FLT) states that for any prime number and coprime base , . If this congruence fails, then cannot be prime. Using FLT as a primality test seems promising because it distinguishes primes from nonprimes in many cases. For example, , , , , so 9 isn't prime, and so on. This primality test works up to , but . A pseudoprime like 341 is a composite number that passes a primality test. Different bases lead to different pseudoprimes.


  • [Snapshot]
  • [Snapshot]
  • [Snapshot]


    • Share:

Embed Interactive Demonstration New!

Just copy and paste this snippet of JavaScript code into your website or blog to put the live Demonstration on your site. More details »

Files require Wolfram CDF Player or Mathematica.