Tag Archives: theorem

Chinese Remainder Theorem proof

Posted on April 10, 2019 by Brent

In my previous post I stated the Chinese Remainder Theorem, which says that if and are relatively prime, then the function is a bijection between the set and the set of pairs (remember that the notation means the set ). … Continue reading →

Posted in modular arithmetic, number theory | Tagged , , , | 2 Comments

More words about PWW #25: The Chinese Remainder Theorem

Posted on April 5, 2019 by Brent

In a previous post I made images like this: And then in the next post I explained how I made the images: starting in the upper left corner of a grid, put consecutive numbers along a diagonal line, wrapping around … Continue reading →

Posted in modular arithmetic, number theory, posts without words | Tagged , , , , | 3 Comments

A few words about PWW #25

Posted on March 9, 2019 by Brent

In my previous post I made images like this: What’s going on? Well, first, it’s easy to notice that each grid starts with in the upper-left square; is one square down and to the right of , then is one … Continue reading →

Posted in modular arithmetic, number theory, posts without words | Tagged , , , , | 4 Comments

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

Apollonian gaskets and Descartes’ Theorem II

Posted on June 10, 2016 by Brent

In a few previous posts I wrote about “kissing sets” of four mutually tangent circles, and the fact that their signed bends satisfy Descartes’ Theorem, (Remember that the signed bend of a circle is like the curvature , except that … Continue reading →

Posted in geometry, pattern, pictures, recursion | Tagged , , , , , , , | 1 Comment