Category Archives: primes

More on Fermat witnesses and liars

Posted on January 23, 2019 by

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 , , , , , | Leave a comment

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

Posted on January 18, 2019 by

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
Image | Posted on January 15, 2019 by | Tagged , , , | 5 Comments

The Fermat primality test and the GCD test

Posted on November 18, 2018 by

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

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

Quickly recognizing primes less than 1000: memorizing exceptional composites

Posted on October 15, 2018 by

In my previous post I wrote about a procedure for testing the primality of any number less than : Test for divisibility by all primes up to , and also . (In practice I test for 2 and 5 first, … Continue reading →

Posted in arithmetic, computation, primes | Tagged , , , , , , ,

Quickly recognizing primes less than 1000: divisibility tests

Posted on October 11, 2018 by

I took a little hiatus from writing here since I attended the International Conference on Functional Programming, and since then have been catching up on teaching stuff and writing a bit on my other blog. I gave a talk at … Continue reading →

Posted in arithmetic, computation, primes | Tagged , , , , | 3 Comments