Primes

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? [Read More]

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. [Read More]

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\). [Read More]