# Suugaku Girl supplementary handout for chapter 2: Prime numbers

She doesn't seem that excited

So last time, Tetra was being enlightened by MC-kun about definitions. This actually arises from MC-kun using prime numbers as a motivating example.

Primes are megas important in mathematics and even more important today. The entire branch of mathematics called number theory is all about studying the properties of prime numbers. They’re so useful that we’ve done stuff like extend the notion of prime elements to algebraic structures called rings or apply analytic techniques to learn more about them, but we’ll stick with elementary number theory for now.

Now, for hundreds of years, we’d been studying number theory only because it’s cool and mathematicians love prime numbers. Last time, I mentioned some examples of math preceding useful applications. Well, number theory is a really good example of that, because in the 70s, we found a use for it, which is its main use today, in cryptography. There have been some new techniques using some algebra as well, but for the most part, modern cryptography relies on the hardness of factoring primes. Neat!

Okay, so we’re back to the original question that MC-kun tries to get Tetra to answer, which is, what is a prime number?

Definition. An integer \$p\$ is prime if and only if \$p\geq 2\$ and the only positive divisors of \$p\$ are 1 and itself.

MC-kun explains that the motivation for excluding 1 from the definition of a prime number is because we want to be able to say that we can write every number as a unique product of prime numbers. This is very useful, because now we know we can break down every number like this and we can tell them apart because they’re guaranteed to have a unique representation. This is called unique prime factorization.

Theorem. Let \$a > 0\$ be an integer. Then we can write \$a = p_1p_2\cdots p_k\$ for some primes \$p_1,\dots,p_k\$. This representation is unique up to changing the order of terms.

We can show this by induction on \$a\$. We’ve got \$a=2\$ so that’s pretty obvious. So let’s say that every integer \$k\lt a\$ can be decomposed like this and suppose we can’t decompose \$a\$ into prime numbers, assuming \$a\$ itself isn’t already a prime since it would just be its own prime decomposition. Then we can factor \$a=cd\$ for some integers \$c\$ and \$d\$. But both \$c\$ and \$d\$ are less than \$a\$, which means they can be written as a product of primes, so we just split them up into their primes and multiply them all together to get \$a\$. Tada.

As a sort of side note, I mentioned before that primes are so useful that we wanted to be able to extend the idea of prime elements into rings. Well, it turns out for certain rings, it isn’t necessarily true that numbers will always have a unique representation when decomposed into primes. This is something that comes up in algebraic number theory, which is named so because it involves algebraic structures and techniques. This was invented while we were trying to figure out if Fermat’s Last Theorem was actually true (which needed this and other fun mathematical inventions from the last century that implies that Fermat was full of shit when he said he had a proof).

So at the end of the chapter, after Tetra gets her chair kicked over by the megane math girl, we’re treated to a note that acts as a sort of coda to the chapter that mentions that there are infinitely many primes. How do we know this?

Suppose that there are only finitely many primes. Then we can just list all of the prime numbers, like on Wikipedia or something. So we’ve got our list of primes \$p_1,p_2,\dots,p_k\$. So let’s make a number like \$N=1+p_1\cdots p_k\$. Well, that number is just a regular old number, so we can break it down into its prime factors. We already know all the primes, so it has to be divisible by one of them, let’s say \$p_i\$.

Now we want to consider the greatest common divisor of the two numbers, which is just the largest number that divides both of them. We’ll denote this by \$\gcd(a,b)\$. So since \$p_i\$ is a factor of \$N\$, we’ve got \$\gcd(N,p_i)=p_i\$. But then that gives us \$p_i=\gcd(N,p_i)=\gcd(p_i,1)=1\$ by a lemma that says that for \$a=qb+r\$, we have \$\gcd(a,b)=\gcd(b,r)\$. This means that we have \$p_i=1\$, which is a contradiction, since 1 isn’t a prime number, and so I guess there are actually infinitely many primes.

So the nice thing is that we won’t run out of prime numbers anytime soon, which is very useful because as we get more and more computing power, we’ll have to increase the size of the keys we use in our cryptosystems. Luckily, because factoring is so hard, we don’t need to increase that size very much before we’re safe for a while. Or at least until we develop practical quantum computers.