Category Archives: primes

The Fermat primality test

Posted on August 3, 2018 by

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 , , | 4 Comments

Fast and slow machines

Posted on January 27, 2018 by

In my previous post, I presented three hypothetical machines which take a positive integer as input and give us something else as output: a factorization machine gives us the complete prime factorization of ; a factor machine gives us one … Continue reading →

Posted in computation, number theory, primes | Tagged , , , , , , , , , , | 1 Comment

New Mersenne prime

Posted on January 11, 2018 by

With impeccable timing, just in the middle of my series about primality testing, a new Mersenne prime has been announced, a little under two years after the previous one. In particular, it has been shown that is prime; this is … Continue reading →

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

A tale of three machines

Posted on January 3, 2018 by

The Fundamental Theorem of Arithmetic tells us that any positive integer can be factored into a product of prime factors.1 Given a positive integer , this leads naturally to several questions: What is the prime factorization of ? This is … Continue reading →

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

Fermat’s Little Theorem: proof by group theory

Posted on December 21, 2017 by

It’s time for our third and final proof of Fermat’s Little Theorem, this time using some group theory. This proof is probably the shortest—explaining this proof to a professional mathematician would probably take only a single sentence—but requires you to … Continue reading →

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

Fermat’s Little Theorem: proof by necklaces

Posted on December 12, 2017 by

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

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 , , ,