Category Archives: Primes

The Prime Bet

Let's say you sit in a pub, minding your own business, when all of a sudden a stranger walks up to you and offers you a bet:

We'll choose two positive integers at random. If they have any divisor in common (other than 1) I'll pay you a dollar, else you'll pay me a dollar. Are you in?

Apart from the question what kind of establishments you frequent, you should be wondering: is this a good bet for you?

When two integers have no divisors in common except the trivial divisor 1 we say they are coprime or relatively prime. 6 and 9 have the common divisor 3, so they are not coprime, whilst 8 and 9 only have the trivial common divisor 1, so they are coprime.

This makes you start thinking: "As numbers grow bigger, aren't there a lot of divisors out there? After all, half the numbers are even, so if we hit two even numbers, they'll have the factor 2 in common and I'll win. And then there's 3, 5, 7, ... Seems like a good deal!" Continue reading The Prime Bet

Primes from a Different World

Every textbook on number theory will begin with a treatise on prime numbers; every treatise on prime numbers will begin by emphasising their importance as building blocks or atoms of our number system: every integer can be expressed as a product of prime numbers in one way and one way only. Six is two times three and there is no other way to decompose it.1 Euclid proved this over two thousand years ago and it is so fundamental (hence the name fundamental theorem of arithmetic) to our thinking about numbers that we take it for granted. It is not!

There are numbers that behave very much like the integers but have a different structure. One rather simple example are the Gaussian integers (usually denoted \mathbb Z[i]) which look just like complex numbers z=x+iy, except that x and y are restricted to integer values. They live in the complex plane, but exclusively on a discrete grid amongst their continuous cousins.

Gaussian_integer_lattice.svg Continue reading Primes from a Different World


  1. Yes, you can write 12 as 3*4 or 2*6, but you can continue either way and eventually reach the unambiguous 2*2*3. 

Prime Generating Sequences

A couple of months ago (really, a long, long time ago) I found an interesting question on Mathematics Stack Exchange (another site to effectively waste away hours of your life). It reminded me of my Bachelor's thesis (which I wrote a really, really long time ago) about the sequence

g_n=\mathrm{gcd}(n,a_{n-1})=(n,a_{n-1}) \quad\text{for}\quad n>1,

where a_1=7 and

a_n=a_{n-1}+g_n.

Here, \mathrm{gcd}(a,b)=(a,b) stands for the greatest common divisor,1 i.e., the largest integer d that divides both a and b. This may not seem terribly interesting at first sight, but if you look at the first few values for g_n you'll notice something curious:

1, 1, 1, 5, 3, 1, 1, 1, 1, 11, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 23, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 47, 3, 1, 5, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 101...

There are for sure a lot of ones in there, but other than that, all the numbers are primes. This is not a bias in the first few example -- Eric Rowland proved that all values of g_n are either 1 or a prime in a beautiful little paper back in 2008. Continue reading Prime Generating Sequences


  1. It's common to abbreviate gcd(a,b)=(a,b) in number theory, and I shall do so in the remainder of the article. Similarly, it's convention to write lcm(a,b)=[a,b].