Primes

Cryptography is a natural application of number theory and so I’d like to write down a few thoughts about it in this blog. (The fact that there are real world applications to number theory deserves some appreciation in itself, but it would throw us too much off track here.) One particularly nice feature of cryptography is the ability to explain its inner workings with real world analogies about security. For instance, one way two parties (who we, by convention, call Alice and Bob) could hide their secrete communication is if Alice writes a letter, puts it in a box, and locks it with a padlock for which both she and Bob have a key, but no one else. [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]

It’s quite some time since we arrived at Riemann’s main result, the explicit formula \[ J(x)=\mathrm{Li}(x)-\sum_{\Im\varrho>0}\left(\mathrm{Li}(x^\varrho)+\mathrm{Li}(x^{1-\varrho})\right)+\int_x^\infty\frac{\mathrm{d}t}{t(t^2-1)\log t}-\log2, \] where \(J(x)\) is the prime power counting function introduced even earlier. It’s high time we applied this! First, let’s take a look at \(J(x)\) when calculating it exactly: You see how this jumps by one unit at prime values (\(2\), \(3\), \(5\), \(7\), \(11\), \(13\), \(17\), \(19\)), by half a unit at squares of primes (\(4\), \(9\)), by a third at cubes (\(8\)), and by a quarter at fourth powers (\(16\)), but is constant otherwise. [Read More]

I will start this blog the way Bernhard Riemann started his paper: with Euler’s product formula that John Derbyshire called the golden key: \[ \zeta(s)=\sum_{n\ge1}n^{-s}=\prod_{p}(1-p^{-s})^{-1} \] This holds for any complex number \(s\) with \(\Re s > 1\). If you look up a proof in any modern textbook, you will find a number technical rearrangements that end up in an examination of the absolute convergence on both sides. But actually, the formula is nothing but a fancy way of writing out the Sieve of Eratosthenes. [Read More]