Number Theory – A Primer

This primer exists for the background necessary to read our post on RSA encryption, but it also serves as a general primer to number theory.

Oh, Numbers, Numbers, Numbers

We start with some easy definitions.

Definition: The set of integers, denoted \mathbb{Z}, is the set \left \{ \dots -2, -1, 0, 1, 2, \dots \right \}.

Definition: Let a,b be integers, then a divides b, denoted a \mid b, if there exists an integer n such that na = b. We also less commonly say b is divisible by a. A composite number has a divisor greater than 1, and hence two strictly smaller divisors.

This definition of “dividing” allows us to bypass the more complicated world of fractions and rational numbers, and keep most of what we do in the integers. The novice reader is encouraged to prove the following propositions about divisibility:

  • If a \mid b then a \mid kb for any k \in \mathbb{N}.
  • If a \mid b and a \mid c then a \mid b + c, a \mid bc.
  • If a \mid b and b \mid a then a = \pm b.
  • Find a counterexample where a \mid bc but neither a \mid b nor a \mid c holds.

Definition: A positive integer p is prime if it has exactly two distinct divisors: 1 and p. For the remainder of this post, we will always use p,q to denote primes.

It follows immediately from the definition that if p,n are positive integers and p is prime, then n \mid p if and only if n = 1 or n=p.

We could work toward the fundamental theorem of arithmetic, that every positive integer factors uniquely as a product of primes, but this would lead us down the road of proving Bezout’s theorem, and we want to work quickly toward other things. Instead, we simply prove the existence of such a factoring, and take its uniqueness for granted:

Theorem: Every positive integer factors as a product of primes.

Proof. Let S be the set of positive integers which do not have a factoring as a product of primes. In particular, 1 \notin S since 1 is the product of zero primes, and no prime is in S. So S is entirely composed of composite numbers. Take the smallest element x \in S, and since it is composite it may be written as x = ab, where a,b are both strictly smaller than x. But since each of a,b are not in S, they factor into products of primes. By combining these factorings, we achieve a factoring of x, a contradiction. \square

Definition: The greatest common divisor of two numbers a, b, abbreviated gcd and denoted (a,b) or less commonly \gcd(a,b), is the largest divisor of both a and b. We say two numbers are relatively prime if (a,b) = 1.

Note that two relatively prime numbers might not be prime. In fact, (8,9) = 1, but neither 8 nor 9 are prime. We also sometimes say (though it is probably grammatically incorrect) a is relatively prime to b.

We may prove some interesting facts about greatest common divisors, which we leave as exercises to the ambitious reader:

  • (a + cb, b) = (a,b) for any c \in \mathbb{Z}.
  • (a,b) is the smallest positive linear combination of a,b with integer coefficients.
  • (Bezout’s theorem, a corollary to the above two statements) There is a linear combination of a,b with integer coefficients that equals (a,b).

The last theorem shows up in group theory as a statement about generators of additive integer groups n\mathbb{Z}.

Congruences and Modular Arithmetic

Definition: a is congruent to b modulo n, denoted a \equiv b \mod n, if n \mid b-a.

This definition has a more familiar form for computer scientists, namely the line of code:

a % n == b % n

In plain language, two numbers are congruent modulo n if they have the same remainder when divided by n. Usually, however, we make 0 \leq b < n, so that b is the remainder of a when divided by n.

It is a cheap fact that the relation \cdot \equiv \cdot \mod n is an equivalence relation on integers for any fixed n. In other words:

  • a \equiv a \mod n
  • If a \equiv b \mod n then b \equiv a \mod n
  • If a \equiv b \mod n and b \equiv c \mod n then a \equiv c \mod n.

This allows us to partition the integers into their congruence classes. In other words, the fact that this is an equivalence relation allows us to identify a number with its remainder modulo n. For the sake of consistency, when stating the set of all congruence classes mod n, we stick to the classes represented by the positive integers 0, \dots, n-1.

There is a vast amount of work on solving systems of congruences. The interested reader should investigate the Chinese Remainder Theorem and Hensel’s Lemma.

Definition: A number b is an inverse to a number a modulo n if ab \equiv 1 \mod n.

Inverses help to reduce computations by pairing a number with its inverse modulo n. Therefore, it is interesting to know when numbers have inverses, and whether one is unique up to congruence.

Proposition: An inverse for a \mod n exists if and only if (a,n) = 1 (a and n are relatively prime).

Proof. Suppose such an inverse b exists. Then by the definition of congruence, n \mid ab - 1, and hence cn = ab-1, so ab - cn = 1. In particular, 1 is a linear combination of a and n, and hence it must be the smallest positive linear combination. This is equivalent to (a,n), which is proved by the exercise above.

On the other hand, suppose (a,n)=1. We may reverse the computation above to find b. Specifically, b is the coefficient of a in the linear combination of a,n that makes 1. This proves the theorem \square.

It would be great if we could determine how many numbers have inverses mod n. In fact, we will, but first we’d like to investigate a few interesting theorems.

Theorem: (Wilson) (p-1)! \equiv -1 \mod p for any prime p.

Proof. We immediately see that two of these factors are easy: 1 \equiv 1 \mod p and p-1 \equiv -1 \mod p. We claim that the product of the remaining numbers is always 1.

Since each number 1 < n < p-1 is relatively prime to p (indeed, all numbers are relatively prime to a prime), each number n has an inverse modulo p. As long as this inverse is not n itself, we may pair off each number with its inverse, and see that the entire product is just 1.

To prove that n^{-1} \neq n, suppose n^2 \equiv 1 \mod p. Then (n+1)(n-1) \equiv 0 \mod p. But since 1 < n < p-1, we must have two numbers n+1, n-1 whose product is divisible by p. But neither of n+1, n-1 has p as a factor. So we conclude that either n+1 = 0 or n-1 = 0, giving n \equiv \pm 1 \mod p, a contradiction.

So we may indeed pair the numbers off as we described above, and see that (p-1)! \equiv -1 \mod p. \square

Here is another fundamental result that uses Wilson’s theorem as a stepping stone:

Theorem: (Fermat’s Little Theorem) If p is prime and 0 < a < p, then a^{p-1} \equiv 1 \mod p.

Proof. The set \left \{ 1, 2, \dots, p-1 \right \} are the nonzero remainders mod p. If we multiply each by a, we get another complete set of nonzero residues mod p, namely \left \{ a, 2a, \dots, (p-1)a \right \}.

Since both of these sets are all the nonzero residues mod p, their products are congruent. In particular,

\displaystyle \prod \limits_{k=1}^{p-1} k \equiv \prod \limits_{k=1}^{p-1}ak \mod n

Since we may factor out the a from each term, and there are p-1 terms, we arrive at (p-1)! \equiv a^{p-1}(p-1)! \mod p. But Wilson’s theorem proved that (p-1)! is nonzero mod p, and hence has a multiplicative inverse. Multiplying both sides of the equation by its inverse (which is obviously -1), we get a^{p-1} \equiv 1 \mod p, as desired. \square

Fermat’s Little Theorem allows us to quickly compute large powers of integers modulo any prime. Specifically, we may break 3^{143} \mod 11 into 3^{10*14 + 3} = (3^{10})^{14} \cdot 3^3 By Fermat’s Little Theorem, this is just 1^{14} \cdot 27 \mod 11, and from here we may compute 3^{143} \equiv 5 \mod 11. Certainly this is much faster than incrementally multiplying 3 to itself 143 times and every so often dividing by 11. We subtly allude to the usefulness of number theory for computing large exponents, which is an important theme in our post on RSA encryption.

Euler’s Phi Function

Our final topic for this primer is Euler’s phi function (also called the totient function), which counts the number of positive integers which are relatively prime to n.

Definition: \varphi(n) is the number of positive integers between 1 and n which are relatively prime to n.

Here we have another, more general version of Fermat’s Little Theorem, which uses an almost identical proof:

Theorem: For any positive integer n, if (a,n) = 1 then a^{\varphi(n)} \equiv 1 \mod n.

Proof. Again we use the argument from Fermat’s Little Theorem, except here the sets are not all integers from 1 to n, but only those which are relatively prime. Then we notice that if a, b are relatively prime to n, then so is their product.

Using the product trick once more, we label the relatively prime integers r_i, and see that

\displaystyle \prod \limits_{k=1}^{\varphi(n)} r_k \equiv a^{\varphi(n)} \prod \limits_{k=1}^{\varphi(n)} r_k \mod n

Since the product of all relatively prime integers is again relatively prime, it has a multiplicative inverse mod n. While we might not know what it is, it certainly exists, so we may cancel both sides of the congruence to get a^{\varphi(n)} \equiv 1 \mod n. Therefore, we win. \square

Now we would like to have a good way to compute \varphi(n) for a general n. First, we see that for powers of primes this is easy:

Proposition: \varphi(p^k) = p^{k-1}(p-1) = p^k - p^{k-1} for any prime p and positive integer k. In particular, \varphi(p) = p-1.

Proof. The only numbers which are not relatively prime to p^k are all the multiples of p. Since every pth number is a multiple of p, there are hence p^k / p numbers which are not relatively prime to p. Subtracting this from p^k gives our desired formula. \square

Finally, we have a theorem that lets us compute \varphi(n) for an arbitrary n, from \varphi of its prime power factors.

Proposition: \varphi(nm) = \varphi(n)\varphi(m) if n and m are relatively prime.

Proof. To each number a relatively prime to n, and each number b relatively prime to m, we see that am+bn is relatively prime to mn. Supposing to the contrary that some prime p divides (an+bm, mn), we see that it must divide one of m, n but not both, since (m,n) = 1. Suppose without loss of generality that p \mid n. Then since p \mid an+bm, we may see that p \mid m, a contradiction.

In other words, we have shown that a,b \mapsto am+bn is a function from the set of pairs of relatively prime numbers of n, m to the set of relatively prime numbers to nm. It suffices to show this map is injective and surjective.

For injectivity, we require that no two distinct am+bn are congruent. Supposing we have two distinct a,a' and two b, b', with am+bn \equiv a'm+b'n \mod mn. Then rearranging terms we get m(a-a') + n(b-b') \equiv 0 \mod mn. Since latex m$ divides both m(a-a') and 0 under the modulus, we see that m divides n(b-b'). But since (m,n) = 1, we get that m \mid b-b', so by definition b \equiv b' \mod m, contradicting our assumption that the b‘s were distinct. We get a similar result for the a‘s, and this proves injectivity.

For surjectivity, let k be a positive integer relatively prime to nm. Since (m,n) = 1, we may write am+bn = k for some a,b \in \mathbb{Z}. This is achieved by finding a linear combination of m,n equal to 1 (their gcd), and then multiplying through by k. We claim that (a,n) = 1. This is true since if some prime divided both of a,n, then it would also divide am+bn = k, and also nm. But k was assumed to be relatively prime to nm, so this cannot happen. Hence, a is relatively prime to m. An identical argument gives that b is relatively prime to n, so the pair (a,b) \mapsto am+bn, proving surjectivity. \square

This, we may compute \varphi(n) multiplicatively, by first finding its prime factorization, and then computing \varphi(p^k) for each prime factor, which is easy.

Unfortunately, finding prime factorizations quickly is very hard. Unless we know the factorization of a large n ahead of time (large as in hundreds-of-digits long), computing \varphi(n) is effectively impossible. We cover the implications of this in more detail in our post on RSA encryption.

Until next time!

Encryption & RSA

This post assumes working knowledge of elementary number theory. Luckily for the non-mathematicians, we cover all required knowledge and notation in our number theory primer.

So Three Thousand Years of Number Theory Wasn’t Pointless

It’s often tough to come up with concrete applications of pure mathematics. In fact, before computers came along mathematics was used mostly for navigation, astronomy, and war. In the real world it almost always coincided with the physical sciences. Certainly the esoteric field of number theory didn’t help to track planets or guide ships. It was just for the amusement and artistic expression of mathematicians.

Despite number theory’s apparent uselessness, mathematicians invested a huge amount of work in it, searching for distributions of primes and inventing ring theory in the pursuit of algebraic identities. Indeed some of the greatest open problems in mathematics today are still number theoretical: the infamous Goldbach Conjecture, the Twin Prime Conjecture, and the Collatz Conjecture all have simple statements, but their proofs or counterexamples have eluded mathematicians for hundreds of years. Solutions to these problems, which are generally deemed beyond the grasp of an average mathematician, would certainly bring with them large prizes and international fame.

Putting aside its inherent beauty, until recently there was no use for number theory at all. But nowadays we have complex computer simulated models, statistical analysis, graphics, computing theory, signal processing, and optimization problems. So even very complex mathematics finds its way into most of what we do on a daily basis.

And, of course, number theory also has its place: in cryptography.

The history of cryptography is long and fascinating. The interested reader will find a wealth of information through the article and subsequent links on Wikipedia. We focus on one current method whose security is mathematically sound.

The Advent of Public Keys

Until 1976 (two years before the RSA method was born), all encryption methods followed the same pattern:

  1. At an earlier date, the sender and recipient agree on a secret parameter called a key, which is used both to encrypt and decrypt the message.
  2. The message is encrypted by the sender, sent to the recipient, and then decrypted in privacy.

This way, any interceptor could not read the message without knowing the key and the encryption method. Of course, there were various methods of attacking the ciphers, but for the most part this was a safe method.

The problem is protecting the key. Since the two communicating parties had to agree on a key that nobody else could know, they either had to meet in person or trust an aide to communicate the key separately. Risky business for leaders of distant allied nations.

Then, in 1976, two researchers announced a breakthrough: the sender and recipient need not share the same key! Instead, everybody who wanted private communication has two keys: one private, and one public. The public key is published in a directory, while the private key is kept secret, so that only the recipient need know it.

Anyone wishing to send a secure message would then encrypt the message with the recipient’s public key. The message could only be decrypted with the recipient’s private key. Even the sender couldn’t decrypt his own message!

The astute reader might question whether such an encryption method is possible: certainly every deterministic computation is reversible. Indeed, in theory it is possible to reverse the encryption method. However, as we will see it is computationally unfeasible. With the method we are about to investigate (disregarding any future mathematical or quantum breakthroughs), it would take a mind-bogglingly long time to do so. And, of course, the method works through the magic of number theory.

RSA

Rivest, Shamir, and Adleman. They look like pretty nice guys.

RSA, an acronym which stands for the algorithm’s inventors, Rivest, Shamir, and Adleman, is such a public-key encryption system. It is one of the most widely-used ciphers, and it depends heavily on the computational intractability of two problems in number theory: namely factoring integers and taking modular roots.

But before we get there, let us develop the method. Recall Euler’s totient function, \varphi(n).

Definition: Let n be a positive integer. \varphi(n) is the number of integers between 1 and n relatively prime to n.

There is a famous theorem due to Euler that states if a, n are relatively prime integers, then

\displaystyle a^{\varphi(n)} \equiv 1 \mod{n}

In other words, if we raise a to that power, its remainder after dividing by n is 1. Group theorists will recognize this immediately from Lagrange’s Theorem. While it is possible to prove it with elementary tools, we will not do so here. We cover the full proof of this theorem in our number theory primer.

In particular, we notice the natural next result that a^{k \varphi(n) + 1} \equiv a \mod{n} for any k, since this is just

\displaystyle (a^{\varphi(n)})^k \cdot a \equiv 1^ka \equiv a \mod{n}.

If we could break up k \varphi(n) + 1 into two smaller numbers, say e,d, then we could use exponentiation as our encryption and decryption method. While that is the entire idea of RSA in short, it requires a bit more detail:

Let M be our message, encoded as a single number less than n. We call n the modulus, and for the sake of argument let us say M and n are relatively prime. Then by Euler’s theorem, M^{\varphi(n)} \equiv 1 \mod{n}. In particular, let us choose a public key e (for encryption), and raise M^e \mod{n}. This is the encrypted message. Note that both e and n are known to the encryptor, and hence the general public. Upon receiving such a message, the recipient may use his private key d = e^{-1} \mod{\varphi(n)} to decrypt the message. We may pick e to be relatively prime to \varphi(n), to ensure that such a d exists. Then ed \equiv 1 \mod{\varphi(n)}, and so by Euler’s theorem

\displaystyle (M^e)^d = M^{ed} = M^{k \varphi(n) + 1} \equiv M \mod{n}

By exponentiating the encrypted text with the right private key, we recover the original message, and our secrets are safe from prying eyes.

Now for the messy detail: Where did n come from? And how we can actually compute all this junk?

First, in order to ensure M < n for a reasonably encoded message M, we require that n is large. Furthermore, since we make both n and e public, we have to ensure that \varphi(n) is hard to compute, for if an attacker could determine \varphi(n) from n, then e^{-1} \mod{\varphi(n)} would be trivial to compute. In addition, one could theoretically compute all the eth roots of M^e modulo n.

We solve these problems by exploiting their computational intractability. We find two enormous primes p,q, and set n = pq. First, recall that the best known way to compute \varphi(n) is by the following theorem:

Theorem: For p,q primes, \varphi(p^k) = p^k - p^{k-1}, and \varphi(p^j q^k) = \varphi(p^j)\varphi(q^k).

In this way, we can compute \varphi(n) easily if we know it’s prime factorization. Therein lies the problem and the solution: factorizing large numbers is hard. Indeed, it is an unsolved problem in computer science as to whether integers can be factored by a polynomial-time algorithm. Quickly finding arbitrary roots mod n is a similarly hard problem.

To impress the difficulty of integer factorization, we visit its world record. In 2009, a team of researchers successfully factored a 678-bit (232-digit) integer, and it required a network of hundreds of computers and two years to do. The algorithms were quite sophisticated and at some times fickle, failing when one node in the network went down. On the other hand, our p,q will each be 2048-bit numbers, and so their product is astronomical in comparison. In fact, even 1024-bit numbers are thousands of times harder to factor than 678-bit numbers, meaning that with the hugest of networks, it would take far longer than our lifespans just to factor a “weak” RSA modulus with the methods known today. In this respect, and for the foreseeable future, RSA is watertight.

Since we constructed n as the product of two primes, we know

\varphi(n) = \varphi(p)\varphi(q) = (p-1)(q-1),

so we can compute \varphi(n) trivially. Then, if we pick any e < \varphi(n) which is relatively prime to \varphi(n) (for instance, e itself could be prime), then we may compute the public key d via the extended Euclidean algorithm.

For a clean-cut worked example of RSA key generation and encryption, see the subsection on Wikipedia. We admit that an example couldn’t be done much better than theirs, and we use the same notation here as the writers do there.

Big Random Primes

There is one remaining problem that requires our attention if we wish to implement an RSA encryption scheme. We have to generate huge primes.

To do so, we note that we don’t actually care what the primes are, only how big they are. Generating large random odd numbers is easy: we can simply randomly generate each of its 2,048 bits, ensuring the smallest bit is a 1. Since we recall that primes are distributed roughly according to x / \log(x), we see that the chance of getting a prime at random is roughly 2 / \log(2^{2048}), which is about 1 / 710. Thus, on average we can expect to generate 710 random numbers before we get a prime.

Now that we know we’ll probably find a prime number fast, we just have to determine which is prime. There is essentially only one sure-fire primality test: the Sieve of Eratosthenes, in which we simply test all the primes from 2 to the square root of n. If none divide n, then n is prime.

Unfortunately, this is far too slow, and would require us to generate a list of primes that is unreasonably large (indeed, if we already had that list of primes we wouldn’t need to generate any more!). So we turn to probabilistic tests. In other words, there are many algorithms which determine the likelihood of a candidate being composite (not prime), and then repeat the test until that likelihood is sufficiently close to 0, and hence a certainty. Generally this bound is 2^{-100}, and the existing algorithms achieve it in polynomial time.

Unfortunately an in-depth treatment of one such primality test is beyond the scope of this post. In addition, most contemporary programming languages come equipped with one such primality test, so we put their implementations aside for a later date. To read more about probabilistic primality tests, see the list of them on Wikipedia. They are all based on special cases of Euler’s theorem, and the distribution of multiplicative inverses modulo n.

Implementation

In a wild and unprecedented turn of events, we did not use Mathematica to implement RSA! The reason for this is so that anyone (especially the author’s paranoid father) can run it. So we implemented it in Java. As always, the entire source code (and this time, an executable jar file) is available on this blog’s Github page.

Despite its relative verbosity, Java has a few advantages. The first of these is the author’s familiarity with its GUI (graphical user interface) libraries. The second benefit is that all of the important functions we need are part of the BigInteger class. BigInteger is a built-in Java class that allows us to work with numbers of unbounded size. Recall that in Mathematica unbounded arithmetic is built into the language, but older and more general-purpose languages like Java and C adhere to fixed-length arithmetic. Disregarding the debates over which is better, we notice that BigInteger has the functions:

static BigInteger probablePrime(int bitLength, Random rnd)
BigInteger modPow(BigInteger exponent, BigInteger m)
BigInteger modInverse(BigInteger m)

For clarity, the first function generates numbers which are not prime with probability at most 2^{-100}, the second computes exponents modulo “m”, and the third computes the multiplicative inverse modulo “m”. The “modPow” and “modInverse” functions operate on the context object, or the implicit “this” argument (recall Java is object-oriented [see upcoming primer on object-oriented programming]).

Indeed, this is all we need to write our program! But there are a few more specifics:

First, we need a good random number generator to feed BigInteger’s “probablePrime” function. It turns out that Java’s built-in random number generator is just not secure enough. To remedy this, we could use the “java.security.secureRandom” class, part of Java’s cryptography package; but for the sake of brevity, we instead import an implementation of the Mersenne Twister, a fast prime number generator which is not secure.

Second, there are known factoring methods for n=pq if p \pm 1 or q \pm 1 has only small prime factors. These are due to Pollard and Williams. So we include a special method called “isDivisibleByLargePrime”, and screen our candidate prime numbers against its negation. The largest prime we test for is 65537, the 6543rd prime. The details of this function are in the source code, which again is available on this blog’s Github page. It is not very interesting.

Third, we notice that the choice of public key is arbitrary. Since everyone is allowed to know it, it shouldn’t matter what we pick. Of course, this is a bit too naive, and it has been proven that if the public key e is small (say, 3), then the RSA encryption is less secure. After twenty years of attacks trying to break RSA, it has been generally accepted that public keys with moderate bit-length and small Hamming weight (few 1’s in their binary expansion) are secure. The most commonly used public key is 65537, which is the prime 2^{16} +1 = \textup{0x10001}. So in our implementation, we fix the public key at 65537.

Finally, in order to make our String representations of moduli, public keys, and private keys slightly shorter, we use alphadecimal notation (base 36) for inputting and outputting our numbers. This has the advantage that it uses all numerals and characters, thus maximizing expression without getting funky symbols involved.

Results

Here is a snapshot of the resulting Java application:


As you can see, the encrypted messages are quite long, but very copy-pasteable. Also, generating the keys can take up to a minute, so have patience when pressing the “Generate Keys” button under the tab of the same name.

There you have it! Enjoy the applet; it’s for everyone to use, but despite all my due diligence in writing the software, I wouldn’t recommend anyone to rely on it for national security.

Feel free to leave me a comment with a super-secret RSA-encoded message! Here is my encryption modulus and my public key:

public key: 1ekh

encryption modulus:
5a1msbciqctepss5dfpp76rdb5selhybzhzerklbomyvwlohasuy81r9rbd3scvujpqn9e7m5hp52qv4fli9f4bupg23060wmaf94zq94s4j22hwyi764kk0k6w8is05tyg7029ub6ux4vb4bq9xxzw9nkfs0pfteq7wnm6hya7b2l2i1w8jh25913qye67gz8z4xrep1dcj8qpyxyi56ltukqyv366hei4nme6h9x00z16cbf8g76me1keccicsgd268u3iocvb6c5lw00j234270608f24qelu8xfjcddc7n9u0w2tf46bl1yzsjb8kb5ys9gh51l0ryetge1lwh1ontenraq35wv5f4ea57zae1ojcsxp3cxpx84mbg0duoln2vny7uixl3ti4n2flvfats4wz0h1c34cgxdyixb7ylci6t4dk8raqcbdi3yxclktvb7yv1sb61nxk1kylfp0h7wqtrogf8c039mc6bqe8b7eixb72pfz4sajw1rf170ck2vysy1z6bgyngrhyn8kpepd0btcyuyj0scdshlexlg4uolls8p6frxj8dt4ykcnddeuvf7dfz1qyqpjk7ljwr1hdgaecyqa6gsxryodrup1qpwgieot6v8c5bbizxm45qj4nez5cpe9q12m0pyeszic5dtb1yc0rm7lzzddg254uf390rk4irecfxibpv2lnk9zper3kg729w32n7u0qn8mamtmh80fo6hd0n5a50d9kzft1g3bky2t2d2f1a574ukigx1dfgqrtehnmx5nd

Until next time!

False Proof – There are Finitely Many Primes

Problem: Show there are finitely many primes.

“Solution”: Suppose to the contrary there are infinitely many primes. Let P be the set of primes, and S the set of square-free natural numbers (numbers whose prime factorization has no repeated factors). To each square-free number n \in S there corresponds a subset of primes, specifically the primes which make up n‘s prime factorization. Similarly, any subset Q \subset P of primes corresponds to a number in S, since we can simply multiply all numbers in Q together to get a square-free number.

Thus we have shown a bijection between S and the power set of P, but the power set of an infinite set is uncountable. Hence, there are uncountably many square-free natural numbers, a contradiction. Hence there are only finitely many primes.

Explanation: The problem here lies in the bijection. Take any subset of primes which is infinitely large. Assuming there are infinitely primes to begin with, this is a valid step, since we may consider the subset of all primes, P \subset P. However, the product of all primes in an infinite subset of positive numbers is infinitely large, and hence cannot correspond to a square-free (finite) number. In other words, the set of finite subsets of an infinite set is countable.

This illuminates why the power set of an infinite set is interesting. Specifically, the only things which make it “big” are the infinite subsets. So these should be our primary concern.

Prime Design

The goal of this post is to use prime numbers to make interesting and asymmetric graphics, and to do so in the context of the web design language CSS.

Number Patterns

For the longest time numbers have fascinated mathematicians and laymen alike. Patterns in numbers are decidedly simple to recognize, and the proofs of these patterns range from trivially elegant to Fields Medal worthy. Here’s an example of a simple one that computer science geeks will love:

Theorem: \sum \limits_{i=0}^{n} 2^i = 2^{n+1}-1 for all natural numbers n.

If you’re a mathematician, you might be tempted to use induction, but if you’re a computer scientist, you might think of using neat representations for powers of 2…

Proof: Consider the base 2 representation of 2^i, which is a 1 in the ith place and zeros everywhere else. Then we may write the summation as

\begin{matrix} & 100 & \dots & 0 \\ & 010 & \dots & 0 \\ & 001 & \dots & 0 \\ & & \vdots & \\ + & 000 & \dots & 1 \\ = & 111 & \dots & 1 \end{matrix}

And clearly adding one to this sum gives the next largest power of 2. \square

This proof extends quite naturally to all k powers, giving the following identity. Try to prove it yourself using base k number representations!

\sum \limits_{i=0}^{n} k^i = \dfrac{k^{n+1}-1}{k-1}

The only other straightforward proof of this fact would require induction on n, and as a reader points out in the comments (and I repeat in the proof gallery), it’s not so bad. But it was refreshing to discover this little piece of art on my own (and it dispelled my boredom during a number theory class). Number theory is full of such treasures.

Primes

Though there are many exciting ways in which number patterns overlap, there seems to be one grand, overarching undiscovered territory that drives research and popular culture’s fascination with numbers: the primes.

The first few prime numbers are 2,3,5,7,11,13,17,19,23, \dots . Many elementary attempts to characterize the prime numbers admit results implying intractability. Here are a few:

  • There are infinitely many primes.
  • For any natural number n, there exist two primes p_1, p_2 with no primes between them and |p_1 - p_2| \geq n. (there are arbitrarily large gaps between primes)
  • It is conjectured that for any natural number n, there exist two primes p_1, p_2 larger than n with |p_1 - p_2| = 2. (no matter how far out you go, there are still primes that are as close together as they can possibly be)

Certainly then, these mysterious primes must be impossible to precisely characterize with some sort of formula. Indeed, it is simple to prove that there exists no polynomial formula with rational coefficients that always yields primes*, so the problem of generating primes via some formula is very hard. Even then, much interest has gone into finding polynomials which generate many primes (the first significant such example was n^2 +n +41, due to Euler, which yields primes for n < 40), and this was one of the driving forces behind algebraic number theory, the study of special number rings called integral domains.

*Aside: considering the amazing way that the closed formula for the Fibonacci numbers uses irrational numbers to arrive at integers, I cannot immediately conclude whether the same holds for polynomials with arbitrary coefficients, or elementary/smooth functions in general. This question could be closely related to the Riemann hypothesis, and I’d expect a proof either way to be difficult. If any readers are more knowledgeable about this, please feel free to drop a comment.

However, the work of many great mathematicians over thousands of years is certainly not in vain. Despite their seeming randomness, the pattern in primes lies in their distribution, not in their values.

Theorem: Let \pi(n) be the number of primes less than or equal to n (called the prime counting function). Then

\lim \limits_{n \rightarrow \infty} \dfrac{\pi(n)}{n / \log(n)} = 1

Intuitively, this means that \pi(n) is about n / \log(n) for large n, or more specifically that if one picks a random number near n, the chance of it being prime is about 1/ \log(n). Much of the work on prime numbers (including equivalent statements to the Riemann hypothesis) deals with these prime counting functions and their growth rates. But stepping back, this is a fascinatingly counterintuitive result: we can say with confidence how many primes there are in any given range, but determining what they are is exponentially harder!

And what’s more, many interesting features of the prime numbers have been just stumbled upon by accident. Unsurprisingly, these results are among the most confounding. Take, for instance, the following construction. Draw a square spiral starting with 1 in the center, and going counter-clockwise as below:

Number Spiral

If you circle all the prime numbers you’ll notice many of them spectacularly lie on common diagonals! If you continue this process for a long time, you’ll see that the primes continue to lie on diagonals, producing a puzzling pattern of dashed cross-hatches. This Ulam Spiral was named after its discoverer, Stanislaw Ulam, and the reasons for its appearance are still unknown (though conjectured).

All of this wonderful mathematics aside, our interest in the primes is in its apparent lack of patterns.

Primes in Design

One very simple but useful property of primes is in least common denominators. The product of two numbers is well known to equal the product of their least common multiple and greatest common divisor. In symbols:

\textup{gcd}(p,q) \textup{lcm}(p,q) = pq

We are particularly interested in the case when p and q are prime, because then their greatest (and only) common divisor is 1, making this equation

\textup{lcm}(p,q) = pq

The least common multiple manifests itself concretely in patterns. Using the numbers six and eight, draw two rows of 0’s and 1’s with a 1 every sixth character in the first row and every 8th character in the second. You’ll quickly notice that the ones line up every twenty-fourth character, the lcm of six and eight:

000001000001000001000001000001000001000001000001
000000010000000100000001000000010000000100000001

Using two numbers p,q which are coprime (their greatest common divisor is 1, but they are not necessarily prime; say, 9 and 16), then the 1’s in their two rows would line up every pq characters. Now for pretty numbers like six and eight, there still appears to be a mirror symmetry in the distribution of 1’s and 0’s above. However, if the two numbers are prime, this symmetry is much harder to see. Try 5 and 7:

0000100001000010000100001000010000100001000010000100001000010000100001
0000001000000100000010000001000000100000010000001000000100000010000001

There is much less obvious symmetry, and with larger primes it  becomes even harder to tell that the choice of match up isn’t random.

This trivial observation allows us to create marvelous, seemingly non-repeating patterns, provided we use large enough primes. However, patterns in strings of 1’s and 0’s are not quite visually appealing enough, so we will resort to overlaying multiple backgrounds in CSS. Consider the following three images, which have widths 23, 41, and 61 pixels, respectively.

23

41

61

Each has a prime width, semi-transparent color, and a portion of the image is deleted to achieve stripes when the image is x-repeated. Applying our reasoning from the 1’s and 0’s, this pattern will only repeat once every \textup{lcm}(23,41,61) = 23*41*61 = 57523 pixels! As designers, this gives us a naturally non-repeating pattern of stripes, and we can control the frequency of repetition in our choice of numbers.

Here is the CSS code to achieve the result:

html {
   background-image: url(23.png), url(41.png), url(61.png);
}

I’m using Google Chrome, so this is all the CSS that’s needed. With other browsers you may need a few additional lines like “height: 100%” or “margin: 0”, but I’m not going to worry too much about that because any browser which supports multiple background images should get the rest right. Here’s the result of applying the CSS to a blank HTML webpage:

Now I’m no graphic designer by any stretch of my imagination. So as a warning to the reader, using these three particular colors may result in an eyesore more devastating than an 80’s preteen bedroom, but it illustrates the point of the primes, that on my mere 1440×900 display, the pattern never repeats itself. So brace yourself, and click the thumbnail to see the full image.

Now, to try something at least a little more visually appealing, we do the same process with circles of various sizes on square canvases with prime length sides ranging from 157×157 pixels to 419×419. Further, I included a little bash script to generate a css file with randomized background image coordinates. Here is the CSS file I settled on:

html {
   background-image: url(443.png), url(419.png), url(359.png),
      url(347.png), url(157.png), url(193.png), url(257.png),
      url(283.png);
   background-position: 29224 10426, 25224 24938, 8631 32461,
      22271 15929, 13201 7320, 30772 13876, 11482 15854,
      31716, 21968;
}

With the associated bash script generating it:

#! /bin/bash

echo "html {"
echo -n "   background-image: url(443.png), url(419.png), "
echo -n "url(359.png), url(347.png), url(157.png), url(193.png), "
echo -n "url(257.png), url(283.png);"
echo -n "   background-position: "

for i in {1..7}
do
	echo -n "$RANDOM $RANDOM, "
done

echo "$RANDOM, $RANDOM;"
echo "}" 

Prime Circles

And here is the result. Again, this is not a serious attempt at a work of art. But while you might not call it visually beautiful, nobody can deny that its simplicity and its elegant mathematical undercurrent carry their own aesthetic beauty. This method, sometimes called the cicada principle, has recently attracted a following, and the Design Festival blog has a gallery of images, and a few that stood out. These submissions are the true works of art, though upon closer inspection many of them seem to use such large image sizes that there is only one tile on a small display, which means the interesting part (the patterns) can’t be seen without a ridiculously large screen or contrived html page widths.

So there you have it. Prime numbers contribute to interesting, unique designs that in their simplest form require very little planning. Designs become organic; they grow from just a few prime seedlings to a lush, screen-filling ecosystem. Of course, for those graphical savants out there, the possibilities are endless. But for the rest of us, we can use these principles to quickly build large-scale, visually appealing designs, leaving math-phobic designers in the dust.

It would make me extremely happy if any readers who play around and come up with a cool design submit them. Just send a link to a place where your design is posted, and if I get enough submissions I can create a gallery of my own 🙂

Until next time!