The Number That Lies About Being Prime

[00:00:00]There is a fast way to check whether a number is prime, and it leans on one fact proved by Fermat almost 400 years ago.

[00:00:08]Take a prime, call it P. Pick any base that shares no factor with it. Raise that base to the power P minus 1 and divide by P. The remainder is always 1.

[00:00:20]Always, for every base.

[00:00:22]That gives you a test you can run on a number you are unsure about. Call it N.

[00:00:27]Pick a base, raise it to N minus 1. Take the remainder on dividing by N. If that remainder is anything other than 1, you are done. N cannot be prime. A single base has caught it. And on ordinary composite numbers, it catches them at once.

[00:00:43]>> [music] >> Take 15. Raise 2 to the 14th, divide by 15, and the remainder is 4, not 1. 2 has just testified that 15 is composite, >> [music] >> and it is right. 15 is 3 * 5.

[00:00:57]Try 91. The base 2 leaves a remainder of 64.

[00:01:02]Caught again in one line with the smallest base there is. So, the test has a comforting shape. The genuine prime answers 1 to every base you try.

[00:01:12]A composite almost always gets exposed by some base. A witness that the number is hiding factors. The whole method rests [music] on a quiet assumption that everyone made, that if a number answers 1 to enough bases, it has run out of places to hide.

[00:01:29]That assumption has a hole in it.

[00:01:31]>> [music] >> And the smallest number that falls through the hole is 561.

[00:01:35][music] So, put 561 on trial.

[00:01:38]We are looking for one base, just [music] one, that leaves a remainder other than 1 and proves it composite.

[00:01:45]On 15, the base 2 did the job on the first try. On 91, the base 2 did it again. We expect the same here. One quick witness, and we are finished.

[00:01:57]Start with two.

[00:01:59]Raise two to the 560th power, divide by 561, and read the remainder. It is one.

[00:02:06]Try four.

[00:02:08]One.

[00:02:09]Try five. One.

[00:02:11]Seven. One.

[00:02:13]Eight. One. 10. One.

[00:02:17]13. One. Every small base we hand it comes back the same way a true prime would answer. Push it harder. Jump to 100. One. 200. One.

[00:02:30]All the way out to 560, the largest base below the number itself, still one. We are not sampling a handful and getting lucky. Count the bases between one and 561 that share no common factor with it.

[00:02:45]There are 320 [music] of them, and every single one returns a remainder of one.

[00:02:50]320 bases interrogated. 320 answers of one. Zero witnesses. The only bases that do anything different are the ones already sharing a factor with 561, bases like three or 11, and those give themselves away by not being coprime in the first place, which is a different kind of catch. Among the honest interrogators, the ones the test actually relies on, not one dissents.

[00:03:16]By every reading the test can give, 561 behaves exactly like a prime.

[00:03:23]There is no base coprime to it that will ever say otherwise. Here is the catch.

[00:03:28]561 is not [music] prime.

[00:03:31]It factors cleanly and without effort into 3 * 11 * 17. You can multiply those in your head.

[00:03:39]3 * 11 is 33 * 17 is 561.

[00:03:44]The factors were never deeply hidden. A trial division by three finds one in a single step. And yet the powerful general test, the one that exposed 15 and 91 on site, checked 320 different bases and was fooled by every one of them.

[00:04:01]This is the thing worth sitting with.

[00:04:03]The test did not slip up on a hard case.

[00:04:05]It failed completely >> [music] >> on a number whose factors a child could find because it was asking the wrong kind of question.

[00:04:13]It kept asking whether a base leaves a remainder of one and for this number the answer is yes for every base they could possibly test a fire. The witnesses that should have caught it do not exist.

[00:04:23]With an ordinary composite, witnesses are everywhere. For 91, most bases expose it and you only have to try a few before one does. For 561, the set of witnesses among the co-prime bases is empty.

[00:04:37]Not small, empty. A composite number that passes the Fermat test for every base co-prime to it is called a Carmichael number after Robert Carmichael who wrote about them in 1910.

[00:04:50]The blunt name for what they do is also the accurate one. They are absolute pseudoprimes, false primes that hold up under every base.

[00:04:59]And 561 is the smallest one there is. The obvious question is how a number pulls this off and there is a precise answer.

[00:05:08]It was written down by a man named Korselt [music] in 1899.

[00:05:12]Years before anyone had found a single example to test it against, Korselt's rule says a number is one of these absolute [music] pseudoprimes exactly when two conditions hold.

[00:05:24]First, it must be square-free. No prime factor is allowed to appear twice.

[00:05:28]>> [music] >> So a number like 12, which is 2 squared * 3, is ruled out from the start.

[00:05:34]Second, and this is the engine of the whole thing.

[00:05:38]For every prime [music] that divides the number, that prime minus one must divide the number minus one.

[00:05:44]Notice what is striking about this rule.

[00:05:47]It never raises anything to a huge power. It never runs the test at all. It just looks at the prime factors and does a little arithmetic. And that alone decides whether every base in the world will be fooled.

[00:06:00]Walk it through on 561.

[00:06:02]It's primes are 3, 11, and 17. Each appearing once.

[00:06:07]>> [music] >> So, it is square-free. The first condition holds. Now, the second.

[00:06:12]The number minus one is 560.

[00:06:15]Subtract one from each prime factor.

[00:06:18]Three becomes two, 11 becomes 10, [music] 17 becomes 16. So, you check three small divisions. Does two divide 560?

[00:06:28]Yes, 280 times.

[00:06:30]>> [music] >> Does 10 divide 560?

[00:06:33]Yes, 56 times. Does 16 divide 560?

[00:06:38]Yes, >> [music] >> exactly 35 times. Three conditions all met. No remainder anywhere.

[00:06:46]That is the entire reason 561 fools the test. And you can verify it by hand [music] in under a minute. The deep looking deception comes down to three small numbers each [music] dividing 560 evenly. It is worth seeing why that rule is the right [music] one because it turns a mystery into something almost mechanical.

[00:07:06]Fermat's fact in its sharper form says that for a prime P, raising any coprime base to the power P minus one returns [music] one. The reason 561 cannot be cracked is that it inherits this property from each of its three prime [music] factors at once.

[00:07:24]Take the factor 17. By Fermat, any base raised to the 16th power is one in the world of remainders modulo 17. Now, the exponent we actually use [music] is 560 and Korselt guaranteed that 16 divides 560.

[00:07:40]So, the big exponent is just the small [music] one repeated a whole number of times.

[00:07:45]One to any power is still one. The base comes back as one modulo 17. The very same argument runs through three, >> [music] >> because two divides 560, and through 11, because 10 divides [music] 560.

[00:07:59]So, the base leaves a remainder of one modulo three, modulo 11, and modulo 17, all together. And when something is one across all [music] three prime factors of a square-free number, it is one modulo their product, one modulo 561 itself. [music] That is the machine. Korselt's divisibility conditions are exactly what force the same answer of one out of every prime factor in lockstep. The number does not get lucky. It is built so that no base can ever disagree. 561 is the first, but it is not alone.

[00:08:34]Run Korselt's test on every number and collect the ones that pass.

[00:08:38]>> [music] >> And below 10,000, you find exactly seven of these false primes. After >> [music] >> which is 5 * 13 * 17. Then 1729.

[00:08:51]>> [music] >> Then 2465, 2821, 6601, and 8911.

[00:08:58]Seven numbers scattered across the first 10,000 integers. And look at what every one of them has in common.

[00:09:04]Each is a product of three distinct [music] odd primes. None is a product of just two.

[00:09:10]That is not an accident, and it is the next thread [music] to pull.

[00:09:15]There is a reason no Carmichael number is a product of just two primes. [music] Korselt demands that for each prime factor, that prime minus one divides the number minus one. Try it with only two factors, [music] say P * Q, and the two divisibility conditions collide. They force a contradiction every [music] time.

[00:09:35]The rule simply cannot be satisfied with two primes. Three is the minimum, which is why the smallest example had to wait until a product of three small primes [music] lined up just right at 561.

[00:09:49]One of those seven is worth a glance on its own. 1729 is [music] the taxi cab number, the smallest number that is a sum of two cubes in two different ways.

[00:09:59]The one Ramanujan named from a hospital bed [music] when Hardy called its cab dull. It turns out the same 1729 [music] is also one of these absolute pseudoprimes, 7 * 13 * 19, quietly fooling the Fermat test. A single small number wearing two different pieces of mathematical fan.

[00:10:18]But the headline about the seven is not their charm. It is [music] how few of them there are. Hold the seven Carmichael numbers below 10,000 against the company they keep.

[00:10:29]In that [music] same range, there are 1,229 primes. So, for every Carmichael number, there are well over a hundred ordinary primes and an overwhelming run of plain composites that the Fermat test catches [music] without trouble.

[00:10:44]And they thin out as you climb. Below 100,000, there are 16 [music] of them.

[00:10:49]Below a million, 43. Below 10 million, 105.

[00:10:54]The count keeps rising, but desperately slowly [music] next to the primes, which by 10 million already number more than 660,000.

[00:11:02]>> [music] >> This is why the Fermat test was trusted for so long and why a strengthened version of it is still used in practice today.

[00:11:10]Pick a random number with hundreds of digits and a [music] few random bases, and the chance of stumbling onto one of these perfect liars is staggeringly small. For almost everything you will ever feed it, the test is right.

[00:11:23]The Carmichael numbers are a measure zero crack, vanishingly rare, easy to never meet by accident. The fix that real systems [music] use, a refinement called the strong test plugs the hole by asking a sharper question that even the Carmichael numbers cannot answer with a clean one. That the plain Fermat test on its own has this blind spot built in and the seven small numbers below 10,000 are the first proof of it.

[00:11:50]Which makes the last fact about them the surprising one.

[00:11:53]They never run out. For most of the 20th century, [music] nobody could prove whether the list of Carmichael numbers stops. You could keep finding more, but maybe past some enormous [music] point they simply ceased. Maybe the conditions Korselt demanded became impossible to satisfy all at once. The answer arrived in 1994.

[00:12:14]Three mathematicians, Alford, Granville, and [music] Pomerance, proved that there are infinitely many Carmichael numbers.

[00:12:21]The list never ends. However far out you go, there is always another composite waiting [music] that will pass the Fermat test for every base. Their proof did more than say the supply is endless.

[00:12:33]>> [music] >> It showed the count grows at a definite rate. That beyond some point the number of Carmichael numbers up to a given size grows faster than any fixed power of a slowly shrinking margin. In plain terms, [music] not only are there always more, there are eventually a great many more than anyone had dared to guess.

[00:12:53]So both halves of the picture are true at once and they pull [music] against each other. These numbers are extraordinarily rare, a tiny scatter among the integers thinning as you climb.

[00:13:04]And they are infinite in number. No last one. No point past which they stop.

[00:13:10]Rare forever, but never exhausted. That combination is exactly why a primality test built only on Fermat's [music] idea can never be made fully safe.

[00:13:20]There is no height you can climb to and declare yourself past the liars. [music] The The of numbers that fool the test is endless, even as the odds of meeting one shrink toward [music] nothing. So, here is the whole shape of it.

[00:13:33]Fermat handed us a fast, almost always right way to expose composite numbers.

[00:13:39]Find one base that leaves a remainder other than one, and the number cannot be prime. On 15, [music] on 91, on nearly everything, it works on sight. And then there is the handful of numbers it cannot touch. Composite, square-free, [music] built so that every prime factor returns one in perfect unison, and so passing the test for every single base that could testify against them. Korselt wrote the recipe for [music] them before anyone had found one. Carmichael gave them his name.

[00:14:08]The smallest of them is 561, >> [music] >> 3 * 11 * 17, a number whose factors you can find in a heartbeat, and [music] which still answers one to all 320 of its honest interrogators. Seven of them hide below 10,000. [music] Infinitely many wait beyond.

[00:14:25]The reason traces all the way back to three small divisions, 2, 10, and 16 each going evenly [music] into 560.

[00:14:33]Change any one prime factor, and the spell breaks. [music] Line them up just so, and the number becomes untouchable by the test. And that is the quiet lesson sitting inside a routine primality check.

[00:14:46]>> [music] >> A test can be right almost every time and still be fooled completely. Not by a number that hid its factors well, but by one that learned to give every honest witness the answer it wanted to hear.

[00:14:58]561 does not conceal that it is composite.

[00:15:03]It simply refuses to every base to admit it.