Tag Archives: little

Fermat’s Little Theorem: proof by necklaces

Posted on December 12, 2017 by Brent

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

Posted on November 30, 2017 by Brent

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 , , , | Comments Off on Euler’s Theorem: proof by modular arithmetic

Fermat’s Little Theorem: proof by modular arithmetic

Posted on November 13, 2017 by Brent

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!

Posted on November 1, 2017 by Brent

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

Posted on October 14, 2017 by Brent

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

Posted on September 30, 2017 by Brent

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