Like many math students, I had dreams of mathematical greatness. I thought I was close once. A difficult algebra problem in college kept me working late into the night. After hours of struggle, I felt a breakthrough coming. I deftly manipulated expressions. I factored, multiplied and simplified, until my discovery finally revealed itself:
$latex 1 + 1=2$.
I couldn’t help but laugh. The world already knew that $latex 1 + 1=2$, so “Honner’s theorem” was not to be. And although many young mathematicians have experienced the disappointment of the not-quite-breakthrough, the remarkable story of Daniel Larsen keeps the dream alive.
Larsen was a high school student in 2022 when he proved a result about a certain kind of number that had eluded mathematicians for decades. He proved that Carmichael numbers — a curious kind of not-quite-prime number — could be found more frequently than was previously known, establishing a new theorem that will forever be associated with his work. So, what are Carmichael numbers? To answer that, we need to go back in time.
Pierre de Fermat has his name on one of the most famous theorems in mathematics. For over 300 years, Fermat’s Last Theorem stood as the ultimate symbol of unachievable mathematical greatness. In the 1600s, Fermat scribbled a note about his proposed theorem in a book he was reading, claiming to know how to prove it without providing any details. Mathematicians attempted to solve the problem themselves until the 1990s, when Andrew Wiles finally proved it using new techniques discovered hundreds of years after Fermat died.
But it’s Fermat’s less famous “little theorem” that relates to Carmichael numbers. Here’s one way to state it:
Given a prime number $latex p$, then for any integer $latex a$, the quantity $latex a^p – a$ is divisible by $latex p$.
For example, take the prime $latex p=11$ and the integer $latex a=2$. Fermat’s little theorem says that $latex 2^{11} – 2=2046$ is divisible by 11, and it is: $latex 2046 div 11=186$. Or take $latex p=7$ and $latex a=4$: $latex 4^7 – 4=16380=7 times 2340$, so $latex 4^7 – 4$ is indeed divisible by 7.
Unlike with Fermat’s Last Theorem, it didn’t take 300 years to resolve his little theorem. Leonhard Euler published a proof less than a century later. And because it’s about prime numbers, people found ways to use it.
One way to use Fermat’s little theorem is to show that a number is not a prime. Let’s say you’re wondering if 21 is prime or not. If 21 were prime, then according to Fermat’s little theorem, for any integer $latex a$, $latex a^{21}$ – $latex a$ would have to be divisible by 21. But if you try out some values of $latex a$ you see that this doesn’t work. For example, $latex 2^{21} – 2=2097150$, which is not a multiple of 21. Therefore, because it doesn’t satisfy Fermat’s little theorem, 21 can’t be a prime.
This may seem like a silly way to check if a number is prime. After all, we know $latex 21=3 times 7$. But checking whether large numbers are prime is a time-consuming and important task in modern mathematics, so mathematicians are always looking for shortcuts. To that end, mathematicians have wondered if the converse of Fermat’s little theorem might be true.
What’s the converse of a theorem? You may remember from math class that a theorem can be thought of as a conditional statement of the form “if P then Q.” A theorem says that if the P part (the antecedent or hypothesis) is true, then the Q part (the consequent or conclusion) must also be true. The converse of a theorem is the statement you get when you switch the antecedent and consequent. So the converse of “If P then Q” is the statement “If Q then P.”
Let’s consider the Pythagorean theorem. We’re often told that it says $latex a^2 + b^2=c^2$. But this isn’t quite right. The Pythagorean theorem is really a conditional statement: It says that if a right triangle has side lengths $latex a$, $latex b$ and $latex c$, with $latex c$ being the length of the hypotenuse, then $latex a^2 + b^2=c^2$. So what’s its converse? It says that if a triangle’s side lengths $latex a$, $latex b$ and $latex c$ satisfy the equation $latex a^2 + b^2=c^2$, then it’s a right triangle.
It’s tempting to think that the converse of a theorem is always true, and many a student has fallen into that trap. The converse of the Pythagorean theorem happens to be true, which lets us conclude that a triangle with side lengths 9, 40 and 41 must be a right triangle since $latex 9^2 + 40^2=41^2$. But the converse of a true statement need not be true: For example, while it’s true that if $latex x$ is a positive number, then $latex x^2$ is positive, the converse — if $latex x^2$ is a positive number, then $latex x$ is positive — isn’t, since $latex (-1)^2$ is positive but −1 itself isn’t.
It’s good mathematical practice to explore the converse of a statement, and mathematicians looking for primality tests wanted to know if the converse of Fermat’s little theorem was true. The converse says that, given an integer $latex q$, if the number $latex a^q – a$ is divisible by $latex q$ for any integer $latex a$, then $latex q$ must be a prime number. If this were true, it would sidestep some of the computational grunt work of checking whether $latex q$ is divisible by any numbers other than 1 and itself. As is so often the case in mathematics, this one question led to new questions, which ultimately led to some new mathematical ideas.
When you start exploring the converse of Fermat’s little theorem, you’ll discover that it’s true for a lot of numbers. For example, for any integer $latex a$, the number $latex a^2 – a$ is divisible by 2. You can see this by factoring $latex a^2 – a$ as $latex a times (a-1)$. Since a and $latex a − 1$ are consecutive integers, one of them has to be even, and so their product must be divisible by 2.
Similar arguments show that $latex a^3 – a$ is always divisible by 3 and $latex a^5 – a$ is always divisible by 5 (see the exercises below for more details). So the converse of Fermat’s little theorem holds for 3 and 5. The converse tells us what we expect for small non-prime numbers as well. If we use it to check whether 4 is prime or not, we’ll compute $latex 2^4 – 2$ and observe that 14 is not divisible by 4.
In fact, you can check all the way up to the number 561 and everything will point to the converse of Fermat’s little theorem being true. Prime numbers less than 561 divide $latex a^p – a$ for every a, and non-primes less than 561 don’t. But that changes at 561. With some slightly advanced number theory it can be shown that $latex a^{561} – a$ is always divisible by 561, so if the converse of Fermat’s little theorem were true, then 561 should be a prime. But it’s not: $latex 561=3 × 11 × 17$. So the converse of Fermat’s little theorem is false.
Mathematicians call numbers like 561 “pseudoprime” because they satisfy some conditions associated with being prime (like dividing $latex a^p – a$ for all a) but aren’t actually prime numbers. More counterexamples to the converse of Fermat’s little theorem have been found — the next three are 1,105, 1,729 and 2,465. These became known as Carmichael numbers, named after the American mathematician Robert Carmichael. After they were discovered, new questions popped up: Are there other ways to identify Carmichael numbers? Do they have any other special properties? Are there infinitely many of them? If so, how frequently do they occur?
It was this last question that ultimately caught the attention of Daniel Larsen. Mathematicians had proved that there were indeed infinitely many Carmichael numbers, but to show this they had to construct Carmichael numbers that were very far apart. This left open the question of how these infinitely many Carmichael numbers are distributed along the number line. Are they always far apart by their nature, or might they occur with more frequency and regularity than this initial proof showed?
Such questions about pseudoprimes are reminiscent of similar and important questions about the primes themselves. Two thousand years ago, Euclid proved that there are infinitely many prime numbers, but it took much longer to understand how the primes are distributed throughout the number line. In the 1800s, Bertrand’s postulate showed that for any $latex n> 3$, there is always a prime number between $latex n$ and $latex 2n$. This gives us some idea of how often to expect primes as we make our way along the number line.
Mathematicians wondered if some version of Bertrand’s postulate was true for Carmichael numbers. Daniel Larsen wondered, too, and building on the work of some famous modern mathematicians — the Fields medalists James Maynard and Terence Tao, among others — he turned his curiosity into a new result about how Carmichael numbers are distributed. And while young mathematicians probably shouldn’t expect to achieve as much while completing tonight’s homework, Daniel Larsen’s hard work, perseverance and success should inspire them to push forward, even if they’re re-proving something we already know.
>>> Read full article>>>
Copyright for syndicated content belongs to the linked Source : Quanta Magazine – https://www.quantamagazine.org/pierre-de-fermats-link-to-a-high-school-students-prime-math-proof-20231122/
