Season 7 Episode 0

Some numbers aren't prime but feel almost prime. In this episode, we find a way to make that feeling more precise!

Further Reading

Fermat’s Little Theorem 

Jonah proved this with what I call an "overcounting" method; count some objects more than once each, then correct for the overcount. You might have seen other versions of this method if you’ve seen combinations and permutations. 

For a different proof of FLT using proof by induction, see the Wolfram MathWorld page here, just before equation (4) and onwards. 

Quick note on history; Fermat appears to be the first person to state this theorem, but he didn’t publish a proof. Euler published a proof. Maybe it should be called Euler’s Theorem but there’s a problem; see this list. 


Lagrange’s Theorem

This bit is just for people who have met an introduction to group theory before (perhaps as part of A-level Further Maths). If you haven’t heard of groups before and you’d like to find out what they are, there’s an introduction here on the NRICH website or, as I always say, you might be interested in a university Mathematics degree! 

There's a theorem for groups in general called Lagrange’s Theorem which says that the size of a subgroup (a subset of your group that’s also a group) always divides the size of the group. As a consequence, if you take any group element and raise to the power of "the size of the group" then you’ll always get the identity element. Applying this to the group made of the integers from $1$ to $p-1$ with group operation multiplication modulo $p$ gives $a^{p-1}\equiv 1 \,(\text{mod} \,p)$ for all $a$. Then we can just multiply both sides by $a$. 

This is what I meant on the stream when I said that there are large theorems that produce smaller theorems "as examples"; here we’re taking a big theorem that’s true for all groups and applying it to one type of group as a sort of example. There are still one-off neat ideas in mathematics; things that come out of nowhere, but there’s also a lot that be done incrementally, building bigger and better theorems. 


Carmichael numbers 

For a proper definition and some discussion, the Wikipedia page is pretty good.

Quick note on history; these are named “Carmichael” numbers after Robert Carmichael, but the property that they have, and several examples, had previously been found by Václav Šimerka. Somewhere in between, Alwin Korselt found a neat test (below) but didn’t provide any examples. It is easy to imagine that mathematical ideas can all be neatly attributed to a single mind, but that’s not accurate. 

Korselt's criterion says that $a^n\equiv a\, (\text{mod}\, n)$ for all integers $a$ if both of the following; $n$ has no repeated prime factors, and for each prime factor $p$, $n-1$ is a multiple of $p-1$. 

The fact that there are infinitely many Carmichael numbers is due to Alford, Granville, Pomerace in a paper published 1994. 

Even more recently, in a paper published in 2023 Larsen proved that there’s a Carmichael number between $N$ and $2N$ for all sufficiently large $N$. There's a write-up in Quanta magazine here.



If you want to get in touch with us about any of the mathematics in the video or the further reading, feel free to email us on oomc [at] 

Please contact us with feedback and comments about this page. Last updated on 05 Jan 2024 14:03.