Tag Archives: Fermat

More on Fermat witnesses and liars

Posted on January 23, 2019 by Brent

In my previous post I stated, without proof, the following theorem: Theorem: if is composite and there exists at least one Fermat witness for , then at least half of the numbers relatively prime to are Fermat witnesses. Were you … Continue reading →

Posted in computation, number theory, primes | Tagged , , , , , | Comments Off on More on Fermat witnesses and liars

Fermat witnesses and liars (some words on PWW #24)

Posted on January 18, 2019 by Brent

Let be a positive integer we want to test for primality, and suppose is some other positive integer with . There are then four possibilities: and could share a common factor. In this case we can find the common factor … Continue reading →

Posted in computation, number theory, posts without words, primes | Tagged , , , , | 1 Comment

Post without words #24

Posted on January 15, 2019 by Brent
Posted in computation, number theory, posts without words, primes | Tagged , , , | 5 Comments

The Fermat primality test and the GCD test

Posted on November 18, 2018 by Brent

In my previous post we proved that if shares a nontrivial common factor with , then , and this in turn proves that is not prime (by Fermat’s Little Theorem). But wait a minute, this is silly: if shares a … Continue reading →

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

Making the Fermat primality test deterministic

Posted on November 17, 2018 by Brent

Let’s recall Fermat’s Little Theorem: If is prime and is an integer where , then . Recall that we can turn this directly into a test for primality, called the Fermat primality test, as follows: given some number that we … Continue reading →

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

The Fermat primality test

Posted on August 3, 2018 by Brent

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

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