22.1.1 Introduction to division
If you thought division was hard enough, then unfortunately it gets worse. Much worse.
Here’s a really weird question: consider some integers and . Let’s suppose that , in which case we can ask does divide ? I mean, yes?
Most people do know what this means intuitively, but if you like proofs it is also possible to formalise this
Let with . We say that divides with remainder if and only if there exists a such that
This is simple enough, e.g. if and , it is a truth universally acknowledged11 1 Well, certainly more so than \saya single man in possession of a good fortune, must be in want of a wife - people say that maths books are dull and dry; clearly people who haven’t opened a copy of Pride and Prejudice. that in , , so we can say that divides with remainder .
As usual, once we have found or defined a mathematical property, it is natural to ask for which kinds of objects it exists, how one finds the values in question, and whether the values in question are unique.
I have (and hopefully you do too!) an intuitive notion that we can divide every number ending up with a \sayquotient (e.g. if we divide by the quotient is because ) and some remainder. This remainder is unique (I certainly can’t think of any divisions with multiple remainders for the same divisor) and that the quotient is unique.
There’s actually more we \sayknow about the remainder, specifically that - this should make sense if you consider that if the remainder was greater than , we can just increase the quotient by one, and decrement the remainder.
Taken together this gives us this theorem
Let and , then there exist unique and where
Proof: this proof is actually painful because there are so many random things flying around.
Here’s a sketch of what we will show
Prove that there are some which satisfy the properties the remainder should have.
Prove that therefore there exists at least one which satisfies the properties the remainder should have.
Prove that the remainder is therefore unique.
We start by defining a set of all the possible remainders. This kind of thing is really useful because it allows us to \sayforget specific things we’ve assumed about the structure of our problem in order to prove specific things.
Then, we would like to show that contains some positive members. This is not too bad. We do a proof by exhaustion here; either or . In the first case, we have some where because we can set which gives us
And in this case , so we have a desired .
In the other case, where , we can set , and then we have
This is also greater than or equal to zero, as and as , we must have that so .
Now for the second part of the proof, which is that there exists some where . Here, the use of the set becomes apparent, we can forget about all the random nonsense we had to pull in order to show that we have some , we just know that it is true. We use some more theorems, specifically the well-ordering principle (this literally just states that if we have a set of integers, and some of these integers are positive, then we also have a least positive integer), and let be the least positive element in .
Now we consider our goal: . We pull a familiar technique slightly adapted from proving that to show that , and we will try to show that
Let’s start with , which we know is
Let . We know that ! Now, we also know that (this is because as we know that ), and is the least positive element, so must be negative; that is , which means that
This was our goal!
All that remains to show is that and are unique. We will employ the standard method (as outlined in Section 6.7), and assume that we have (the natural numbers, of course, include , so we are covering the case where the remainder is ), such that and . We will also let such that . That sentence is certainly a mouthful; all I really mean is \sayassume that they are not unique, then we will show that this is absurd, so they must be unique.
Let us consider the value ,
Now we will use some ingenuity, and WLOG22 2 Without loss of generality assume that (this is really without loss of generality, because we can always swap and and and if - don’t forget that we assumed ), which means (as ) that
The last step follows because . This is absurd, as we assumed that , so it certainly cannot be less than zero. Therefore, the remainders and quotients are unique.
22.1.2 A divides b
We say divides if and only if (i.e. there is no remainder when we perform the division).
22.1.3 How large are divisors?
Suppose that for which are all integers. In this case, a question worth asking is how large can be. A little bit of thought reveals that (as otherwise neither could divide ).
So then the next question is that if both and are less than , how large can they be. To solve this we need to consider the fact that . Here I would suggest writing down some numbers and their factors. If you’ve written down a few, it will hopefully become apparent that either or has to be less than .
Let be integers such that . If and , then one of is less than .
Proof: we can prove this statement by contradiction; suppose without loss of generality that . If then
and is absurd. If then
22.1.4 Bezout’s lemma
Let , then there exists some integers and such that .
Prove that for all it is true that
We know using Bezout’s lemma that there exist some such that and , and therefore
and therefore as divides both and it divides the expression we are after.