Episode 6: Combinatorial Number Theory

So last week I asked:

Does every number have a multiple that starts with the number 2004?

Well, indeed, the answer is....

YES!

That's totally cool, right? Every single number has a multiple that starts with 2004. Every single number. Even numbers that are 2004^20042004 digits long, still have a multiple that starts with 2004.

Don't worry, if you don't believe me, I'm going to prove it to you.


First, I need to tell you about a couple of things so you can understand the proof.

The first is this way cool concept called the Pigeonhole Principle. It states,

If n+1 pigeons are trying to find a home in n holes,
then at least one hole contains two or more of the pigeons.

It seems kind of silly, but it is a extremely useful in a lot of mathematics.



The second thing is a little bit more tricky, so I'm sorry if I lose you.

Consider a number, like 6. Then every other number is said to be congruent to either 0, 1, 2, 3, 4, or 5 "mod 6". This means that give me any number (integer), and I will tell you what it is mod 6 (you divide it by 6, and the remainder is the number mod 6).

17 is congruent to 5 mod 6 (17/6= 2 remainder 5)
36 is congruent to 0 mod 6 (36/6=6 remainder 0)
1679617 is congruent to 1 mod 6 (1679617/6=279936 remainder 1)--ok, excessive, sorry....
24 is congruent to 0 mod 6 (24/6=4 remainder 0)
74 is congruent to 2 mod 6 (74/6=12 remainder 2)
and so on and so on and so on...

We will note that if something is 0 mod 6, then it is a multiple of 6. Since every number can be written as one of these 6 numbers, these 6 numbers are called the residue classes of 6. Therefore, every number falls into one of these 6 reside classes for mod 6. This is true for every number, n (meaning, every number, n, has n residue classes).

Now that you know these two things, let's proof this super cool fact!



Proof:

For any number, n, let’s look at the numbers in the form

200420042004………….2004 such that it has 4n digits
20042004………….2004 such that it has 4n-4 digits
2004………….2004 such that it has 4n-8 digits
all the way to
2004 such that it has 4 digits

We can see that there are n numbers on this list.

If one of these is divisible by n, then we are done because we have found the multiple of n that starts with 2004. Therefore, let’s assume that none of these numbers is divisible by n. Now, if we use the pigeonhole principle, and allow the residue classes of n to be the holes we can see that we have n-1 classes, and n numbers to put into the holes (because we don't have the 0 hole, since we are assuming it's not divisible by n).

By the pigeonhole principle, at least 2 numbers from the list must be in the same hole (or the same class). When this occurs, the difference of those 2 numbers will be 0 mod n, or divisible by n (by the properties of residue classes). This number will also start with 2004 (because of the way we constructed the list). Thus, we have a number that is divisible by n and starts with 2004.

THUS, we have shown that every number has a multiple starting with 2004! (Usually a little box goes right here to signify the end of a proof, but I don't know how to make that so I'll just do a heart.) ♥


That's pretty cool, right?