Godly Musings » Why Number Theory is Cool

I’ve started doing an intro to number theory, and one of the cool things about it is that it examines some simple questions with complicated answers. Here’s a quick example:

Show that $n^2 - n$ is even, for any given integer n.

And here’s the proof: we can easily see that $n^2 - n = n(n-1)$ . Since either $n$ or $n-1$ must be even, and the product of an even number with any other number is even, their product must also be even.

This sort of problem has a property similar to many geometry problems, which is that the original statement is easily comprehensible to people without a mathematical background. In this case, the solution also is widely accessible. There are some more complex proofs, though, and I’ve put one below the fold if you’re interested.

It is impossible to pick two integers a and b greater than two such that $2^b - 1$ divides evenly into $2^a + 1$ .

This is what I mean: I think this is a statement that is easily understood by anyone who remembers any 8th-grade math. Finding a proof of this, though, is trickier. We use an iterative approach, manipulating the expression until we get results.

First of all, for the sake of brevity, I’m going to use a bit of shorthand. When I say $x|y$ what I mean is “x divides evenly into y”. This is the same as saying $y = px$ for some integer value of p. The opposite of this is $x\not|y$ . Now the proof itself.

Proof. Let a and b be any (not necessarily different) integers greater than 2.

Suppose for the time being that $2^b - 1|2^a + 1$ . We are going to accept this assumption and show that it leads to a contradiction. This will prove that the assumption is false.

Now,

$\begin{align}2^a+1 & = (2^{a-b} \times 2^{b}) + 1 \\ &= (2^{a-b} \times 2^{b} - 2^{a-b} + 2^{a-b}) + 1 \\ &= 2^{a-b}(2^{b} - 1 + 1) + 1 \\ &= 2^{a-b}(2^{b} - 1) + (2^{a-b} + 1)\end{align}$

Since we’ve assumed that $2^b - 1$ divides evenly into $2^a + 1$ , we must be able to subtract any multiple of the first from the second, and the result will still be divisible by the first (if this is not obvious, try it with some integers and you’ll see why it works). So we can subtract $2^{a-b}(2^{b} - 1)$ from the above expression, and it should still be divisible by $2^b - 1$ .

Here, we’ve shown that if $2^b - 1|2^a + 1$ then $2^b - 1|2^{a-b} + 1$ .

Now, we have three possible cases:

$a-b=b$
In this case, we have $2^b - 1|2^{a-b} + 1 = 2^b + 1$ . We can do the same thing as above, where we subtract a multiple of the first number, to get:
$2^b - 1|(2^b + 1) - (2^b - 1)$
$2^b - 1|2$
This means that $2^b - 1$ is a factor of 2, namely either 1 or 2. Thus $2^b = 2$ or $2^b = 3$ . 3 is impossible if $b$ is an integer, and 2 is only possible if $b=1$ , but we know that $b \ge 3$ so this is impossible.
$a-b < b$
Since $2^b - 1|2^{a-b} + 1$ , the second term must be equal to or greater than the first. We can’t have $x|y$ if $y < x$ . So this gives us:
$2^b - 1 \le 2^{a-b} + 1$
$2^b - 2^{a-b} \le 2$
Now since $2^b \ge 8$ , this means $2^{a-b} \ge 6$ and therefore $a-b > 2$ . But we divide the last line by two to get:
$2^{b-1} - 2^{a-b-1} \le 1$
Note that this difference cannot be zero, since the exponents are not equal. If both $b-1$ and $a-b-1$ are greater than 0 (and not equal), then their difference will be a multiple of 2. But it clearly is not. So one of the two must be less than or equal to 0. Which means either $b$ or $a-b$ is less than or equal to 1. It can’t be $b$ , because we know it’s greater than 2. And it can’t be $a-b$ because we already determined that it’s greater than 2. So we have another impossibility.
$a-b > b$
This is the only possibility left, therefore it must be true (if our initial assumption is true).

Now we have $2^b - 1|2^{a-b} + 1$ , and we know that $a-b > 2$ , since it’s greater than $b$ . Thus, we can plug $a-b$ into this whole process, in place of $a$ .

Note that $a-b$ is smaller than $a$ since $b$ is positive. So when we wind up at this same step, with a result of $(a-b) - b = a-2b > b$ , we’re dealing with an even smaller number. We keep going, and eventually we get a number $a-nb$ that is smaller than or equal to $b$ (I’m not going to prove that this is inevitable, but you should be able to convince yourself of this). This leads us to possibility 1 or 2, above, which is a contradiction.

Now the contradiction cascades back through the proof. Since a contradiction is generated in one of those three options, the conclusion that $a-nb \le b$ must be false, therefore it cannot be the case that $2^b - 1 | 2^{a-nb} + 1$ . Thus it cannot be true that $2^b - 1 | 2^{a-(n-1)b} + 1$ and so on, back through the iterations of the proof. Thus it cannot be true that $2^b - 1 | 2^{a-b} + 1$ , therefore it cannot be true that $2^b - 1 | 2^a + 1$ . This was our initial assumption, therefore we have proved the opposite.

Now, the final step is to generalize the whole thing. Sure, this may work for some choice of $a$ and $b$ , but is this always true? Well, the proof does not depend on the values of the variables, except for the restriction that they both be greater than 2. So regardless of what values you put in, the original statement (in blockquote) holds. $\blacksquare$

One final thing: why do we require that $a$ and $b$ be greater than 2? Because you can find counterexamples otherwise. For instance, if $a = 3, b = 2$ , then the statement is false. And if $b = 1$ then the statement is always false.

Anyway, I hope I haven’t bored you too much. I find this sort of work very interesting, and this is just the basic groundwork of the field of Number Theory. Some of the more complicated theorems to do with, for instance, prime numbers, are very deep. Hopefully I’ll succeed in getting to work on this as a research project over the summer, and I can write more about it.

Why Number Theory is Cool

Posted to Glee!, Math by god