Tag Archives: prime

A few words about PWW #27

Posted on October 24, 2019 by Brent

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 Brent
Posted in pattern, pictures, posts without words, primes | Tagged , , | 7 Comments

Quickly recognizing primes less than 1000: memorizing exceptional composites

Posted on October 15, 2018 by Brent

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 , , , , , , , | Comments Off on Quickly recognizing primes less than 1000: memorizing exceptional composites

Quickly recognizing primes less than 1000: divisibility tests

Posted on October 11, 2018 by Brent

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 Brent

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

New Mersenne prime

Posted on January 11, 2018 by Brent

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 , , , , | Comments Off on New Mersenne prime

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

The route puzzle

Posted on June 17, 2016 by Brent

While poking around some old files I came across this puzzle: (Click for a larger version.) I didn’t make it, and I have no idea where I got it from (do you know?). But in any case, wherever it comes … Continue reading →

Posted in arithmetic, challenges, number theory, proof, puzzles | Tagged , , , , , , | 7 Comments

M74207281 is prime!

Posted on January 24, 2016 by Brent

I’m a bit late to the party, but the Great Internet Mersenne Prime Search has recently announced a newly verified prime number, , with a whopping 22,338,618 decimal digits! This is now the largest known prime number (though of course … Continue reading →

Posted in computation | Tagged , , , , | Comments Off on M74207281 is prime!

MaBloWriMo 23: contradiction!

Posted on November 24, 2015 by Brent

So, where are we? We assumed that is divisible by , but is not prime. We picked a divisor of and used it to define a group , and yesterday we showed that has order in . Today we’ll use … Continue reading →

Posted in algebra, group theory, modular arithmetic, number theory, proof | Tagged , , , , , , , , , , , | 5 Comments