We’ve covered a lot of ground this first week! I wanted to provide a written summary, with partial proof, of what we have done so far.
We began by learning about proofs. We talked about direct proofs, inductive proofs, proofs by contradiction, and proofs by using the contrapositive of the statement we want to prove. A proof is a justification and argument based upon certain logical premises (which we call axioms); in contrast to other disciplines, a mathematical proof is completely logical and can be correct or incorrect.
We then established a set of axioms for the integers that would serve as the foundation of our exploration into the (often fantastic yet sometimes frustrating) realm of number theory. In short, the integers are a non-empty set with addition and multiplication [which are both associative, commutative, and have an identity, and which behave as we think they should behave; further, there are additive inverses], a total order [an integer is either bigger than, less than, or equal to any other integer, and it behaves like we think it should under addition and multiplication], and satisfying the deceptively important well ordering principle [every nonempty set of positive integers has a least element].
With this logical framework in place, we really began number theory in earnest. We talked about divisibility [we say that divides , written , if for some integer ]. We showed that every number has a prime factorization. To do this, we used the well-ordering principle.
Suppose that not all integers have a prime factorization. Then there must be a smallest integer that does not have a prime factorization: call it . Then we know that is either a prime or a composite. If it’s prime, then it has a prime factorization. If it’s composite, then it factors as with . But then we know that each of have prime factorizations since they are less than . Multiplying them together, we see that also has a prime factorization after all.
Our first major result is the following:
There are infinitely many primes
There are many proofs, and we saw 2 of them in class. For posterity, I’ll present three here.
First proof that there are infinitely many primes
Take a finite collection of primes, say . We will show that there is at least one more prime not mentioned in the collection. To see this, consider the number . We know that this number will factor into primes, but upon division by every prime in our collection, it leaves a remainder of . Thus it has at least one prime factor different than every factor in our collection.
This was a common proof used in class. A pattern also quickly emerges: , a prime. , a prime. , also a prime. It is always the case that a product of primes plus one is another prime? No, in fact. If you look at , you get a nonprime.
Second proof that there are infinitely many primes
In a similar vein to the first proof, we will show that there is always a prime larger than for any positive integer . To see this, consider . Upon dividing by any prime less than , we get a remainder of . So all of its prime factors are larger than , and so there are infinitely many primes.
I would also like to present one more, which I’ve always liked.
Third proof that there are infinitely many primes
Suppose there are only finitely many primes . Then consider the two numbers and . We know that has a prime factor, so that it must share a factor with since is the product of all the primes. But then divides , which is nonsense; no prime divides . Thus there are infinitely many primes.
We also looked at modular arithmetic, often called the arithmetic of a clock. When we say that , we mean to say that , or equivalently that for some integer (can you show these are equivalent?). And we pronounce that statement as ” is congruent to mod .” We played a lot with modular arithmetic: we added, subtracted, and multiplied many times, hopefully enough to build a bit of familiarity with the feel. In most ways, it feels like regular arithmetic. But in some ways, it’s different. Looking at the integers partitions the integers into a set of equivalence classes, i.e. into sets of integers that are congruent to . When we talk about adding or multiplying numbers mod , we’re really talking about manipulating these equivalence classes. (This isn’t super important to us – just a hint at what’s going on beneath the surface).
We expect that if , then we would also have for any integer , and this is true (can you prove this?). But we would also expect that if we had , then we would necessarily have , i.e. that we can cancel out the same number on each side. And it turns out that’s not the case. For example, (both are ), but ‘cancelling the fours’ says that – that’s simply not true. With this example in mind, we went about proving things about modular arithmetic. It’s important to know what one can and can’t do.
One very big and important observation that we noted is that it doesn’t matter what order we operate, as in it doesn’t matter if we multiply an expression out and then ‘mod it’ down, or ‘mod it down’ and then multiply, or if we intermix these operations. Knowing this allows us to simplify expressions like , since we know , and we know that , and so . If we’d wanted to, we could have multiplied it out and then reduced – the choice is ours!
Amidst our exploration of modular arithmetic, we noticed some patterns. Some numbers are invertible in the modular sense, while others are not. For example, , so in that sense, we might think of . More interestingly but in the same vein, since . Stated more formally, a number has a modular inverse if there is a solution to the modular equation , in which case that solution is the modular inverse. When does this happen? Are these units special?
Returning to division, we think of the greatest common divisor. I showed you the Euclidean algorithm, and you managed to prove it in class. The Euclidean algorithm produces the greatest common divisor of and , and it looks like this (where I assume that :
where in each step, we just did regular old division to guarantee a remainder that was less than the divisor. As the divisors become the remainders, this yields a strictly decreasing remainder at each iteration, so it will terminate (in fact, it’s very fast). Further, using the notation from above, I claimed that the gcd of and was the last nonzero remainder, in this case . How did we prove it?
Proof of Euclidean Algorithm
Suppose that is a common divisor (such as the greatest common divisor) of and . Then divides the left hand side of , and thus must also divide the right hand side. So any divisor of and is also a divisor of . This carries down the list, so that the gcd of and will divide each remainder term. How do we know that the last remainder is exactly the gcd, and no more? The way we proved it in class relied on the observation that . But then divides the right hand side of , and so it also divides the left. This also carries up the chain, so that divides both and . So it is itself a divisor, and thus cannot be larger than the greatest common divisor.
As an aside, I really liked the way it was proved in class. Great job!
The Euclidean algorithm can be turned backwards with back-substitution (some call this the extended Euclidean algorithm,) to give a solution in to the equation . This has played a super important role in our class ever since. By the way, though I never said it in class, we proved Bezout’s Identity along the way (which we just called part of the Extended Euclidean Algorithm). This essentially says that the gcd of and is the smallest number expressible in the form . The Euclidean algorithm has shown us that the gcd is expressible in this form. How do we know it’s the smallest? Observe again that if is a common divisor of and , then divides the left hand side of , and so . So cannot be smaller than the gcd.
This led us to explore and solve linear Diophantine equations of the form for general . There will be solutions whenever the , and in such cases there are infinitely many solutions (Do you remember how to see infinitely many other solutions?).
Linear Diophantine equations are very closely related a linear problems in modular arithmetic of the form . In particular, this last modular equation is equivalent to for some .(Can you show that these are the same?). Using what we’ve learned about linear Diophantine equations, we know that has a solution iff . But now, there are not infinitely many incongruent (i.e. not the same ) solutions. This is called the ‘Linear Congruence Theorem,’ and is interestingly the first major result we’ve learned with no proof on wikipedia.
Theorem: the modular equation has a solution iff , in which case there are exactly incongruent solutions.
We can translate a solution of into a solution of , and vice-versa. So we know from the Extended Euclidean algorithm that there are only solutions if . Now, let’s show that there are solutions. I will do this a bit differently than how we did it in class.
First, let’s do the case when , and suppose we have a solution so that . If there is another solution, then there is some perturbation we can do by shifting by a number and by a number that yields another solution looking like . As we already know that , we can remove that from the equation. Then we get simply . Since , we know (see below the proof) that divides . But then the new solution , so all solutions fall in the same congruence class – the same as .
Now suppose that and that there is a solution. Since there is a solution, each of and are divisible by , and we can write them as . Then the modular equation is the same as , which is the same as . Note that in this last case, we can remove the from both sides, so that , or that . From the first case, we know this has exactly one solution mod , but we are interested in solutions mod . Just as knowing that means that might be since goes into three times, goes into times, and this gives us our incongruent solutions.
I mentioned that we used the fact that we’ve proven 3 times in class now in different forms: if and , then we can conclude that . Can you prove this? Can you prove this without using unique factorization? We actually used this fact to prove unique factorization (really we use the statement about primes: if is a prime and , then we must have that or , or perhaps both). Do you remember how we proved that? We used the well-ordered principle to say that if there were a positive integer that couldn’t be uniquely factored, then there is a smaller one. But choosing two of its factorizations, and finding a prime on one side – we concluded that this prime divided the other side. Dividing both sides by this prime yielded a smaller (and therefore unique by assumption) factorization. This was the gist of the argument.
The last major bit of the week was the Chinese Remainder Theorem, which is awesome enough (and which I have enough to say about) that it will get its own post – which I’m working on now.
I’ll see you all in class tomorrow.