Tag Archives: Fermat

The Fermat primality test

After several long tangents writing about orthogons and the chromatic number of the plane, I’m finally getting back to writing about primality testing. All along in this series, my ultimate goal has been to present some general primality testing algorithms … Continue reading

Posted in computation, number theory, primes | Tagged , , | 5 Comments

Fermat’s Little Theorem: proof by necklaces

It’s time for our second proof of Fermat’s Little Theorem, this time using a proof by necklaces. As you know, proof by necklaces is a very standard technique for… wait, what do you mean, you’ve never heard of proof by … Continue reading

Posted in combinatorics, number theory, primes, proof | Tagged , , , , , , | 4 Comments

Euler’s Theorem: proof by modular arithmetic

In my last post I explained the first proof of Fermat’s Little Theorem: in short, and hence . Today I want to show how to generalize this to prove Euler’s Totient Theorem, which is itself a generalization of Fermat’s Little … Continue reading

Posted in number theory, primes, proof | Tagged , , ,

Fermat’s Little Theorem: proof by modular arithmetic

In a previous post I explained four (mostly) equivalent statements of Fermat’s Little Theorem (which I will abbreviate “FlT”—not “FLT” since that usually refers to Fermat’s Last Theorem, whose proof I am definitely not qualified to write about!). Today I … Continue reading

Posted in number theory, primes, proof | Tagged , , | 8 Comments

Four formats for Fermat: correction!

In my previous post I explained three variants on Fermat’s Little Theorem, as well as a fourth, slightly more general variant, which it turns out is often called Euler’s Totient Theorem. Here’s what I said: If and is any integer, … Continue reading

Posted in number theory, primes | Tagged , , , , , , | 4 Comments

Four formats for Fermat

In my previous post I mentioned Fermat’s Little Theorem, a beautiful, fundamental result in number theory that underlies lots of things like public-key cryptography and primality testing. (It’s called “little” to distinguish it from his (in)famous Last Theorem.) There are … Continue reading

Posted in number theory, primes, proof | Tagged , , | 3 Comments

New baby, and primality testing

I have neglected writing on this blog for a while, and here is why: Yes, there is a new small human in my house! So I won’t be writing here regularly for the near future, but do hope to still … Continue reading

Posted in meta, number theory, primes | Tagged , , , | 10 Comments