gtMath

There is a hallway with 100 lockers, numbered 1 through 100. They are all closed to begin with. 

 

There are also 100 kids, numbered 1 through 100. Each kid $n$ runs down the hall once, visiting each locker with a multiple of $n$ on it, opening it if it's closed or closing it if it's open.

 

Which lockers remain open at the end?

 

I've heard that this one is actually an interview question, though no one has ever asked it to me...

So kid 1 runs down the hallway and opens all multiples of 1 (i.e. all the lockers), leaving them all open. Kid number 2 then goes and closes 2, 4, 6, etc., i.e. all the evens.

Now, kid 3 visits 3, 6, 9, etc. and changes the state of each. So he'll close 3 (which kid #1 opened), open 6 (opened by 1 then closed by 2), close 9 (opened by 1), etc.

It's not going to be fast to go through each kid and write it out, though that would get you the answer. But what if there are 1,000 lockers/kids, or 1,000,000? The answer's the same in each case, and it's pretty cool.

To get there, start by considering a given locker- let's look at #48 as an example. Kids #1, 2, 3, 4, 6, 8, 12, 16, 24, and 48, or all the factors of 48, are going to visit this locker. Since there are 10 factors, the door will end up closed (and it will be opened then closed again 5 times in the process).

Now, this is where it gets good.

You can see from the example, or any other example you work through, that a locker will end up closed if it has an even number of visitors, or an even number of factors. Almost all the lockers have an even number of factors, because almost every factor has a "buddy." For 48, the "buddies" are 1 and 48, 2 and 24, 3 and 16, 4 and 12, and 6 and 8.

Which factors don't have a buddy?

It's the ones where the buddy is itself. Take locker 64 as an example. The factors are 1, 2, 4, 8, 16, 32, and 64. Notice that 8 has no buddy, because $64 = 8^2$. So this locker will end up open. It will get opened and closed again 3 times, but will be opened one additional time and remain open at the end.

The only numbers with an odd number of factors like this are the perfect squares, i.e. the set of integers that equal the square of another integer, 1, 4, 9, 16, 25, 36, etc.

So we got the answer; it's the perfect squares. Good job.

If you want to read the real nerdy stuff, go on; otherwise, thanks for reading.

Unique Prime Factorization

The solution to the problem above relied on the fact that any positive integer can be written as the product of two factors, sometimes in multiple ways.

A prime number is a positive integer that has no factors other than 1 and itself. Any other positive integer is a composite number and can be written as a product of factors other than 1 and itself. The first few primes are 1, 2, 3, 5, 7, 11, 13, 17, etc.

There are infinitely many primes. If you want to prove this, assume that there are only $n$ primes, and label them so that $p_1 < p_2 < ... < p_n$. Consider the number $x = p_1 p_2 p_3 ... p_n + 1$. If you try to figure out which primes are factors of this number (by the assumption, there must be at least one, since $x$ is greater than all the primes and thus must be composite), you will run into a contradiction quickly, which proves that there actually must be infinitely many primes.

This isn't news- the proof outlined above is allegedly a modification of a proof by Euclid.

Ok, back to business. We were talking about the locker problem and factoring. Now, as I mentioned above, there are many ways to factor an integer (unless it's prime, in which case there's only one way)- for example, $12 = 1 \times 12 = 2 \times 6 = 3 \times 4 = 1 \times 2 \times 2 \times 3$, etc. However, once we break it down to powers of primes, there is only one way to do it, called a prime factorization. $12 = 2^2 \times 3$. If you look at the factorizations above, they are actually all just re-arrangements of $2^2 \times 3$, the prime factorization of 12.

Ahh...it's all coming back now, isn't it? Remember these?


This discussion is bringing us to the Fundamental Theorem of Arithmetic. I'm going to show the proof below and then leave you a little food for thought about how this relates to the number of visitors at our lockers above.

Before going to that, there is a notation that will be useful, and that's the product sign $\Pi$, which looks like the entrance to a temple but is actually an upper-case Greek letter Pi. This works in the same way as the sum symbol $\Sigma$, where we write below and/or above the index over which we'll be multiplying, and then we write the factors to the right. For example, $\prod_{i=1}^{7}{2i^2}$ has an index $i$ running from 1 to7, and for each one, we throw $2i^2$ into the product. So $\prod_{i=1}^{7}{2i^2} = (2 \times 1^2) \times (2 \times 2^2) \times ... \times (2 \times 7^2)$, whatever that ends up being.

Like sums, we can also write infinite products such as: $$\prod_{i=1}^{\infty}{{p_i} ^ {x_i}}$$ If we say each of the $p_i$'s above is a prime (remember, there are infinitely many), and each of the exponents $x_i$ is a positive integer or zero, with only finitely many being non-zero, then the product above is a representation of some number in the form of a prime factorization. For the ones with an exponent of zero, that prime simply doesn't show up in the prime factorization since ${p_i} ^ 0 = 1$.

Theorem (Fundamental Theorem of Arithmetic): Every positive integer greater than 1 can be factored into a product of powers of primes. Furthermore, this prime factorization is unique (i.e. there is only one way to do it).

Proof: We have to prove that such a prime factorization exists, and then that it is unique. Luckily, it's already been done on Wikipedia, so I'll regurgitate their proof below.

Existence: This part can be proved by induction. The base case is $n=2$, which is obvious because $2 = 2^1$. This is a product (consisting of one factor, $2^1$) of powers of primes. Assume that for some $n$, each integer $j$ with $1<j<n$ has a prime factorization. Either $n$ is prime, or it is composite. If $n$ is prime, we know it can only be written as $n \times 1$, so that is the prime factorization. Otherwise, $n$ is composite, which means that there exist two integers $a$ and $b$ such that $1<a,b<n$ and $ab = n$.

Then $a$ and $b$ are examples of $j$'s from the induction hypothesis, so they can each be written as products of powers of primes, $a = \prod_{i=1}^{m}{{p_i}}$, and $b = \prod_{i=1}^{k}{{q_i}}$, where the $p_i$'s and $q_i$'s are primes. But then $n = ab = (\prod_{i=1}^{m}{{p_i}})(\prod_{i=1}^{k}{{q_i}}) = p_1 ... p_m q_1 ... q_k$, which shows that $n$ can be written as a product of powers of primes.

Uniqueness: There is a more intuitive way to do this that uses Euclid's Lemma, but I'll show the way that doesn't assume this lemma.

We know now that every positive integer greater than 1 has at least one prime factorization. Let $s$ be the smallest positive integer greater than 1 which does not have a unique prime factorization. We're going to show that $s$'s very existence leads to a contradiction and thus that prime factorizations are unique.

$s$ cannot be prime, because primes only have the unique factorization into the product of 1 with themselves, so $s$ is composite and the prime factorizations $s = \prod_{i=1}^{m}{{p_i}}$ and $s = \prod_{i=1}^{k}{{q_i}}$ must each have at least 2 prime factors. Note that here, the $p_i$'s and $q_i$'s are any primes, and some of the $p_i$'s could equal each other, as could the $q_i$'s.

However, none of the $p_i$'s can equal any of the $q_j$'s. If they did, then we'd have a number $\dfrac{s}{p_i} = \dfrac{s}{q_j}$ which is smaller than $s$ but has two different prime factorizations, $p_1...p_{i-1}p_{i+1}...p_m$ and $q_1 ... q_{j-1}q_{j+1}...q_k$. This contradicts the assumption that $s$ was the smallest such integer. So none of the $p_i$'s equal any of the $q_j$'s.

Assume without loss of generality that $p_1 < q_1$. It is indeed without loss of generality, because if it's not the case, then we can switch the $p$ and $q$ labels. Consider the number $t = (q_1 - p_1)q_2...q_k$. This number must be greater than $q_2$ since it's the product of $q_2$ and bunch of other numbers greater than 1, and it must also be less than $s$ since it has the same factors (from the product with the $q$'s) except with the first one reduced from $q_1$ to $q_1 - p_1$.

We can do some algebra to get $$
\begin{align}
t &= (q_1 - p_1) (q_2 ... q_k) \\[2mm]
&= q_1(q_2...q_k) - p_1(q_2...q_k) \\[2mm]
&= s -  p_1(q_2...q_k) \\[2mm]
&= p_1(p_2...p_m) - p_1(q_2...q_k) \\[2mm]
&= p_1((p_2...p_m) - (q_2...q_k)) \\[2mm]
&= p_1u
\end{align}$$ where $u=(p_2...p_m) - (q_2...q_k)$. Since $p_1>0$ and $t>0$, it must also be the case that $u>0$. Since $t<s$, $t$ has a unique prime factorization, and we just showed that $p_1$ must appear in said factorization.

$q_1-p_1>0$, but $q_1-p_1 \neq 1$, because if it did, then we'd have $t = (q_1-p_1)q_2...q_k = q_2...q_k$. But $p_1$ appears in $t$'s unique prime factorization, and none of the $q$'s equal any of the $p$'s, so $q_1-p_1 \geq 2$, which means $q_1-p_1$ has a prime factorization, $q_1 - p_1 = r_1...r_d$, and thus $t = r_1...r_d q_2...q_k$.

Since $p_1$ appears in $t$'s prime factorization and isn't any of the $q$'s, it must be one of the $r$'s, and so $p_1$ is a factor of $q_1-p_1$. In other words, $\exists \ \alpha \in \{1, 2, 3, 4, ... \}$ such that $\alpha p_1 = q_1 - p_1$, which can be rearranged to $p_1 (\alpha + 1) = q_1$. This shows that $q_1$ has a factorization other than just $1 \times q_1$ and thus is not prime.

That's a contradiction, so this whole thing is nonsense: $s$ could not have had 2 different prime factorizations in the first place. This completes the proof.

$\square$

To tie this back to visitors at our numbered lockers, see if you can use the theorem above to prove the following fact about the perfect squares:

In the unique prime factorization of a perfect square, the exponent of each prime is even.

Can you see how that relates to whether the number has an even or odd number of factors (and thus number of visitors at locker $n$)?

Thanks for reading. Post any questions in the comments section.