Category Archives: primes

A few words about PWW #27

Posted on October 24, 2019 by

The images in my last post were particular realizations of the famous Sieve of Eratosthenes. The basic idea of the sieve is to repeatedly do the following: Circle the next number bigger than that is not yet crossed out, call … Continue reading →

Posted in pattern, pictures, posts without words, primes | Tagged , , | 4 Comments

Post without words #27

Posted on October 21, 2019 by
Image | Posted on October 21, 2019 by | Tagged , , | 7 Comments

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

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

Quickly recognizing primes less than 100

Posted on September 16, 2018 by

Recently, Mark Dominus wrote about trying to memorize all the prime numbers under . This is a cool idea, but it made me start thinking about alternative: instead of memorizing primes, could we memorize a procedure for determining whether a … Continue reading →

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