The Impostor Numbers That Fool Even the Most Sophisticated Mathematical Primality Tests
In short: In the world of number theory, some composite numbers are master mimics. They pass tests designed to identify primes, masquerading as the building blocks of mathematics. These pseudoprimes are not just theoretical curiosities; they are central to the security of modern digital communication and the limits of computational power.
At the heart of this deception lies Fermat’s Little Theorem, first asserted by Pierre de Fermat in 1640. The theorem states that for any prime number p and an integer a, p must divide exactly into a raised to the power of p minus a. While this property is a hallmark of primes, it is not exclusive to them. A composite number that satisfies this specific condition is known as a Fermat pseudoprime.
The smallest of these impostors is 341, which is the product of 11 and 31. When tested with the base 2, 341 successfully divides 2 to the power of 341 minus 2, appearing prime to the test despite its composite nature. Leonhard Euler provided the first formal proof of Fermat’s theorem in 1749, long after Fermat’s initial claim. The existence of these numbers proves that Fermat’s primality test is a necessary, but not sufficient, condition for identifying a prime.
The complexity deepens with Carmichael numbers, such as 561 and 1,729, identified by Robert D. Carmichael in 1909. Unlike standard pseudoprimes that only fool tests for specific bases, Carmichael numbers pass the test for every base with which they are relatively prime. This makes them particularly elusive. Because finding large primes is computationally expensive, these probabilistic tests are essential in cryptography, where the difficulty of factoring large numbers secures sensitive data. While deterministic tests like the AKS primality test exist to avoid these false positives, the ongoing tension between speed and certainty remains a cornerstone of computational number theory.
Opens the Intellect+ feed with this card first. Swipe up for the next one.
Sources
- Summary by Intellect · source: Pseudoprime | Definition & Facts | Britannica
- Also: Pseudoprime
To cite this card, link to https://intellectplus.co.uk/app/science-pseudoprime.
How we source, check and correct cards: Editorial standards.
General information, not professional advice. Spotted an error? Flag the card or see corrections and complaints.
Intellect Plus is a visual educational discovery platform for exploring fascinating facts and ideas. Brain Food, Not Brain Rot. What is Intellect Plus?
Related
More in Number theory · More in Science · Latest · A–Z · All topics