Math Fact #3: The Fundamental Theorem of Arithmetic

Okay, so you’re probably expecting a proof here of why Saturday is equal to Tuesday. Unfortunately, that’s not true, of course, because if we set Saturday = Tuesday in an attempt to form a subgroup of the cyclic group of order 7, it collapses to order 1 due to the primality of 7. Hey, let’s talk about primality!

Most of us know what a prime number is: it’s a whole number that can’t be divided by anything besides itself and 1 without a remainder. 1 is usually not treated as prime, for many good reasons. In any case, one property of prime numbers is so useful that it’s known as the fundamental theorem of arithmetic — in other words, the most important theorem in the entire branch of arithmetic. This is a bold claim to make, but it has many applications. The theorem is as follows:

Given any positive whole number, assuming we ignore the order of them, there is only one list of primes that multiply together to give the number.

For instance, the only way to make 36 by multiplying primes is 2 x 2 x 3 x 3. The only way to make 231 is 3 x 7 x 11. The only way to make 1877 is, um, 1877. Because 1 multiplied by anything is that thing, we conventionally define the product of an empty list to be 1, so to get 1 we just don’t multiply any primes.

To prove this is going to take a while, but all of the steps are fairly easy to understand if you have a good enough grasp of arithmetic, so let’s go!

To start, what happens if you try to divide a number by some prime that isn’t a factor of it? Clearly, you get a remainder. For instance, 100 divided by 7 is 14, remainder 2. (We won’t worry about fractions.) Now note that the remainder also cannot be a factor of the prime; if it were, it would have to be greater than the prime or less than 1, and remainders don’t fall in those ranges. But we might as well continue the process and try to divide 7 by 2. 7 divided by 2 is 3, remainder 1. The key here is that if you start with one of the two numbers being a prime, you always end up with a remainder of 1 eventually. Another example, using 1877 as our prime:

1877 ÷ 231 = 8, remainder 29231 ÷ 29 = 7, remainder 28
29 ÷ 28 = 1, remainder 1

Now the key is that we can work backwards and use this to write 1 as a multiple of 1877 plus a multiple of 231:

1 = 29 - 1 x 281 = 29 - (231 - 7 x 29) = -231 + 8 x 29
1 = -231 + 8 x (1877 - 8 x 231) = -65 x 231 + 8 x 1877

The fact that you can always do this is known as Bézout’s identity, and it’s a crucial step in the proof of the fundamental theorem.

The next part of the proof is called Euclid’s lemma: we want to prove that if a prime number is a factor of the product of two numbers, it must be a factor of one or the other — i.e. it can’t be “split” between them. Given Bézout’s identity, this is fortunately pretty easy. Let p be some prime that is a factor of the product a x b, and assume that a is not divisible by p. We know from the identity that we can put together a multiple of a and a multiple of p to get 1; in other words, we can find r and s so that r x p + s x a = 1. Now let’s introduce b into this equation by multiplying everything by b: r x p x b + s x a x b = b. We know that p is a factor of r x p x b by observation, and since p is a factor of a x b, then p is also a factor of s x a x b. Because p is a factor of the entire left side, it is also a factor of the right side; i.e. b is divisible by p. So if a prime isn’t a factor of one part of a product, it must be a factor of the other.

We’re getting close! Now we have the tools to prove the original theorem — I’ll say it again as a reminder:

Given any positive whole number, assuming we ignore the order of them, there is only one list of primes that multiply together to give the number.

Now let’s think about something: how do we even know that there is a way to write the number as a product of primes? Well, if the number (let’s call it x from now on) isn’t a prime, there must be a way to write it as a product of two smaller (possibly composite) numbers, neither of which is 1. But if we keep doing this, the numbers can’t keep getting smaller forever, so at some point all of them have to end up being prime! For instance, 48 is 4 x 12, 4 is 2 x 2, 12 is 3 x 4, 4 is 2 x 2, and so 48 is 2 x 2 x 2 x 2 x 3, a product of primes.

The hard part is showing that this product is unique, and this is where we need Euclid’s lemma. Let’s say that x is a product of primes in two different ways. We’ll label them as follows: xp_1 x p_2 x p_3 x … x p_m q_1 x q_2 x q_3 x … x q_n. Now let’s divide x by p_1, giving just the rest of the product p_2 x p_3 x … x p_m. Clearly p_1 is a factor of q_1 x q_2 x q_3 x … x q_n, so from Euclid’s lemma (applied repeatedly) we know that it has to be a factor of one of the elements in the product. Let’s assume that this element is q_1 (if not, we can just relabel all of the q values, as order doesn’t matter). However, q_1 is prime, so if some other prime p_1 is a factor of it, they have to be the same prime. So p_1 = q_1, and of course p_2 x p_3 x … x p_m = q_2 x q_3 xx q_n. Now we have shown one of the primes to be equivalent in the expansion; the key is that we have also produced two expansions for a smaller number (÷ p_1), which follow the same rules. So we can continue to do this until no primes are left; all of the p's are the same as all of the q's, and there is only one unique expansion. Thus the fundamental theorem of arithmetic is proven.

Why does all of this matter? Well, if you’re looking at this post over any sort of encryption, you should be thankful! Modern encryption relies on using very large primes and the fact that while testing if a number is prime is relatively easy, actually factoring it into primes is very hard. This relies on the fact that there’s only one right way to factor the number, and we have just spent the post proving this very fact. But really, more than that, there are applications to the fundamental theorem throughout other branches of mathematics — it is so ubiquitous that a lot of mathematicians can’t think of too many specific examples, prime factorizations being ingrained into the mathematical mind and thought of as too well-known for their use to merit mention. But overall, this “simple” theorem is crucial (or rather, fundamental) to a large amount of mathematics.

If you have any mathematical topic you’d like me to discuss, let me know!

Math Fact #2: Cleveland to Cincinnati

If you travel from Cleveland to Cincinnati on one day, and from Cincinnati to Cleveland on another day, taking the same road, there must be a time at which you were in the same spot both days.

In other words, if you drive from Cleveland to Cincinnati on e.g. Monday and back on Tuesday, there will always be a time, say 4:14, where you’re in the same spot — at 4:14 Monday and at 4:14 Tuesday, your car is in the same exact place on the highway.

It’s not terribly hard to imagine why this is intuitively. Let’s superimpose the two days. Say you have a twin who drives from Cincinnati to Cleveland taking the same route while you drive from Cleveland to Cincinnati. Clearly, you’re going to pass each other at some point.

But let’s look at this mathematically — how can we logically prove that the two of you pass? Well, for that we need to make two assumptions. The first is our former assumption that you have to drive along the same route — in other words, your position along the journey can be expressed completely in terms of a function giving how far (fractionally) you are along the route at a given time, in one dimension. The second assumption is that you move continuously, i.e. you can’t teleport or drive infinitely past either end. We can now express your travel there and back as two functions f1(t) and f2(t), which map the time as a fraction of the day to your position as a fraction of the path. For instance, if you’re 1/3 of the way to Cincinnati at 12:00 noon on Monday, this corresponds to f1(1/2) = 1/3. (Note that we measure the path from Cleveland to Cincinnati on both days; in other words, f1(t) goes from 0 to 1, while f2(t) goes from 1 to 0.)

What we can now do is take a look at the difference between these two functions, as a new function g(t) = f1(t) - f2(t). We can now say the following about g(t):

  • g(0) = -1. At the start of the day, f1(0) = 0 for Cleveland, and f2(0) = 1 for Cincinnati.
  • g(1) = 1. At the end of the day, f1(1) = 1 for Cincinnati, and f2(1) = 0 for Cleveland.
  • g is a continuous function from real numbers to real numbers; this is very important! This is intuitively the “no teleportation” assumption; more formally, it means that at any time t on the journey, if we pick any distance d, there’s an interval of time around t in which you’re within distance d of where you are at time t.

What we can now do is apply the intermediate value theorem. This states that for such a function g, we can pick any value x from g(0) to g(1), and there’s a t between 0 and 1 where g(t) = x. In our case, we pick x = 0, which is between g(0) = -1 and g(1) = 1. Then at some time t we have g(t) = 0; in other words, at some time of day, the distance between your position on day 1 and on day 2 is 0, i.e. you’re in the same place.

The intermediate value theorem only works because the real numbers are a complete set. This means that if we have an infinite sequence of real numbers that get closer and closer to each other, they also get closer to some real number (which may not be in the sequence). This isn’t true of many structures, such as the rational numbers; for instance, the sequence 3, 3.1, 3.14, 3.141, 3.1415, 3.14159, … contains only rational numbers (because all of the decimal expansions terminate) that clearly get closer to each other as you go, but they don’t approach any rational number (they approach π, which is irrational). Similarly, we could start our sequence with 1 and define the pattern that every term of the sequence is the previous term over 2 plus 1 over the previous term; then the sequence contains rational numbers approaching the square root of 2, which is again irrational. The fact that the real numbers are a complete set is very important to their structure (more on that another time).

This proof is what’s known as an existence proof or non-constructive proof; it tells us that something exists, but it gives little to no help in finding it. A lot of these proofs involve the Intermediate Value Theorem, and some of them have pretty interesting applications, particularly in areas such as topology. For instance, one of the most interestingly named results in mathematics is the hairy ball theorem: if a sphere is covered with hair, we can’t comb the hair flat without creating a cowlick. This may seem like a frivolous concept, but it means for instance that there is always a spot on the planet where any wind that exists is pointing directly up or down (or there is no wind at all). This wouldn’t necessarily be true on a donut-shaped planet, by the way, meaning that if Earth were shaped like a donut, there could be a cycle of constant wind.

Math Fact #1: Facebook Friends

This is the first of a series of posts I’m going to make, hopefully every Saturday. In each one, I’m going to give a mathematical fact and proof, attempting to be accessible and interesting to the general population and give an idea of what math is really about (hint: there’s not a whole lot of trigonometry once you’re through high school). So, let’s get started!

Pick any six people on Facebook. However you pick, there will be three people of the six who either are all friends with each other or aren’t friends with each other.

To see why this is the case, let’s assume we’ve picked six people. Take a look at the friends list of one of them — we’ll call him Jim. Of the other five people, Jim could be friends with all of them, or none of them. However, note that the number of friends and non-friends has to add to 5 (clearly), and if two whole numbers add to 5, one of them has to be 3 or higher. (Try a few pairs of numbers if you’re not sure why this is.) So we can always find three of the other five that Jim is either friends with or not friends with.

To simplify things, we’re only going to look in depth at one of these cases. However, we need to clarify why we can do this. Picture a mirror universe where all friendships are inverted — two people who are friends in our universe aren’t in the other universe, and vice versa. So if Jim isn’t friends with three of the others, Mirror-Jim — Mij, if you will — is friends with those three. Then we can show that Mij and his friends form a triangle of friends or non-friends, and this will correspond to a triangle of non-friends or friends in Jim’s world.

So, either Jim or Mij has three friends of the six. We’ll call these three people Anne, Bob, and Carly. If any two of those three are also friends with each other, we have a triangle of friends. But if none of the three are friends, this makes a triangle of non-friends. So we form a triangle in either case.

As a demonstration that 6 is indeed the minimum, consider a ring of five people, where each is friends with the two adjacent people. The non-friends then form another cycle, this one shaped like a five-pointed star. There is no group of three friends or non-friends.

The result does indeed generalize to higher numbers: for any number of mutual friends or non-friends we want, we’ll eventually find this pattern by considering more and more people. The bounds get very large: nobody knows exactly how many people we need to consider for e.g. ten of them to all be friends or non-friends, but it could be over 20,000.

This result is known as Ramsey’s theorem, and it’s an important theorem in the field known as Ramsey theory. The main idea of Ramsey theory is that a complex enough structure is bound to have patterns somewhere in it, no matter how hard we try to prevent this from happening. Ramsey theory has a variety of applications in geometry and computer science.

Website move

As you may be able to tell from the fact that it no longer loads, my website is in the process of being moved to www.whirligig231.tk. Once the domain registration gets through the pipes, I’ll see you there!

Web ads

I apologize to anyone who went to my website recently and found a bunch of annoying ads. I figured it was the product of either a) the hosting service pulling crap on me and saying “HAHAHA, THIS IS WHY IT’S FREE!” or b) h4x0rs. Turns out it’s the hosting service, but they only do it if you haven’t managed your website in a while. Shows you how much time I dedicate to it. In any case, it should be fine now, so take a look!

Dyadic Intervals Theorem

Proof I came up with some weeks ago. If a ruler covers the entire line and has marks at the dyadic rationals (multiples of a power of 2) that are larger if the power of 2 involved is higher, then any open interval has exactly one mark bigger than all of the others.

My twitch.tv channel

So for those of you who didn’t see the big link above this text, I got a channel on twitch.tv! I’ll mostly be using it to stream The Binding of Isaac for now, but I’ll most likely be playing some other games on there as well, so check it out!

Sequential Discontinuity

I just proved a couple of interesting theorems relating to a concept I’ve defined and call the sequential discontinuity. Anyone who has studied calculus knows of three or four types of discontinuity. The first is the removable discontinuity, where a function is undefined or “wrongly” defined at a single point. The second is the jump discontinuity, where a function approaches a different value from either side of the discontinuity. The third type is the essential discontinuity, which is basically anything else, so teachers tend to further subdivide it into vertical asymptotes (which make up the vast majority of essential discontinuities) and oscillating discontinuities such as the discontinuity of sin(1/x) at x = 0 (even if the function is altered such that f(0) = 0). However, not all essential discontinuities fall into this category.

Consider the following function: f(x) = 0 for all x such that log(x) is not an integer and is undefined otherwise. (This is the base 10 logarithm). This function has obvious removable discontinuities at x = 10^k for integer k, but it also has a discontinuity at x = 0. This is because the formal definition of the limit requires an open interval of x-values around 0 where all f(x) except possibly f(0) are undefined, and no such interval exists. In layman’s terms, you can’t put a mark anywhere past 0 on the number line without a power of ten between 0 and the mark, no matter how close it is to 0. This discontinuity is not an asymptote and does not involve oscillation (the value of f(x) never changes where it exists).

A sequential discontinuity exists in two cases: at the limit of a convergent sequence of x-values where the function is undefined, and at the limit of a convergent sequence of x-values where the sequence of the corresponding function values is unbounded. Note that the second case especially can be a different kind of discontinuity as well; for instance, the discontinuity at x = 0 for f(x) = 1/x is sequential, as we can define the sequence x = 1, 1/2, 1/3, …, which converges to 0 and has function values that increase without bound. It is also a vertical asymptote, a simpler case.

The interesting thing about sequential discontinuities is that sometimes they are “removable” in the sense that the function containing them could be made continuous by changing countably many values (strangely not including the value at the discontinuity). However, they have undefined limits and as such are not removable.

I have here a link to a PDF proof and more formal definition. One small lemma is required for the second case but is not proven, so I will prove it here. An unbounded sequence has for every real number k and natural number M a value m > M such that a_m > k. To prove this, choose i such that a_i > k. If a_i > M, then m = i. If a_i <= M, then let K be the maximum of a_1, a_2, …, a_M. We are guaranteed K >= a_i > k. Then there must be a j such that a_j > K, and j must be greater than M (otherwise K would not be the maximum), so let m = j and a_m > k.


Whirligig Studios website is now LIVE!

So I decided yesterday to get my own website! I’ll post the finished versions of all of my games there, as well as more info about myself, etc. Check it out!

Stoichios 1.0 Out!

Yes, another game release within the span of a few weeks. As it turns out, this is a game I started in 2011. It was up to release candidate 3, but then I lost access to Windows computers in general. No worries; I’ve been able to work out the last few bugs and get the game out.

The game is a card game based on the classical/Greek elements (earth, air, fire, and water) and otherwise plays similarly to Mau Mau or Uno. Single-player and multiplayer modes are included (both local and online). There is also AI. Overall, it’s a pretty fun game, and it has what I consider some of my best music in it as well.

The game is a standalone .exe in a .zip archive; make sure to unzip it first in order to get the DLL files out. The soundtrack .mp3s are included if you want it in iTunes. Let me know if anything goes wrong.

Download: https://www.dropbox.com/s/5m3u90n7e38lu8k/Stoichios_100.zip