22.1 Division

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 aa and bb. Let’s suppose that b>0b>0, in which case we can ask does aa divide bb? I mean, yes?

Most people do know what this means intuitively, but if you like proofs it is also possible to formalise this

Definition 22.1.1

Let a,ba,b\in\mathbb{Z} with b>0b>0. We say that aa divides bb with remainder rr if and only if there exists a qq\in\mathbb{Z} such that

a=bq+r.a=bq+r. (22.1)

This is simple enough, e.g. if a=12a=12 and b=3b=3, 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 \mathbb{Z}, 12=4×3+012=4\times 3+0, so we can say that 33 divides 1212 with remainder 0.

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 1212 by 33 the quotient is 44 because 4×3=124\times 3=12) 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 0r<b0\leqq r<b - this should make sense if you consider that if the remainder was greater than bb, we can just increase the quotient by one, and decrement the remainder.

Example 22.1.1

Taken together this gives us this theorem

Theorem 22.1.1

Let a,ba,b\in\mathbb{Z} and b>0b>0, then there exist unique qq and rr where 0r<b0\leqq r<b

a=bq+r.a=bq+r. (22.2)

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 r0r\geqq 0 which satisfy the properties the remainder should have.

  • Prove that therefore there exists at least one r<br<b which satisfies the properties the remainder should have.

  • Prove that the remainder is therefore unique.

We start by defining a set SS 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.

S={r:r=abq}S=\{r:r=a-bq\} (22.3)

Then, we would like to show that SS contains some positive members. This is not too bad. We do a proof by exhaustion here; either a0a\geqq 0 or a<0a<0. In the first case, we have some rSr\in S where r0r\geqq 0 because we can set q=0q=0 which gives us

r\displaystyle r =ab0\displaystyle=a-b0 (22.4)
=a\displaystyle=a (22.5)

And in this case a0a\geqq 0, so we have a desired rSr\in S.

In the other case, where a<0a<0, we can set q=aq=a, and then we have

r\displaystyle r =aba\displaystyle=a-ba (22.6)
=a(1b)\displaystyle=a(1-b) (22.7)

This is also greater than or equal to zero, as a<0a<0 and as b>0b>0, we must have that 1b01-b\geqq 0 so r0r\geqq 0.

Now for the second part of the proof, which is that there exists some r<br<b where rSr\in S. 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 r0r\geqq 0, 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 rr be the least positive element in SS.

Now we consider our goal: r<br<b. We pull a familiar technique slightly adapted from proving that ab=0a-b=0 to show that a=ba=b, and we will try to show that

rb<0.r-b<0. (22.8)

Let’s start with rbr-b, which we know is

rb\displaystyle r-b =abqb\displaystyle=a-bq-b (22.9)
=ab(q+1)\displaystyle=a-b(q+1) (22.10)

Let r=ab(q+1)r^{\prime}=a-b(q+1). We know that rSr^{\prime}\in S! Now, we also know that r<rr^{\prime}<r (this is because abq<ab(q+1)a-bq<a-b(q+1) as we know that b>0b>0), and rr is the least positive element, so rr^{\prime} must be negative; that is r<0r^{\prime}<0, which means that

rb<0.r-b<0. (22.11)

This was our goal!

All that remains to show is that rr and qq are unique. We will employ the standard method (as outlined in Section 6.7), and assume that we have r,rr,r^{\prime}\in\mathbb{N} (the natural numbers, of course, include 0, so we are covering the case where the remainder is 0), such that rrr\neq r^{\prime} and 0r,r<b0\leqq r,r^{\prime}<b. We will also let q,qq,q^{\prime}\in\mathbb{Z} such that qqq\neq q^{\prime}. 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 rr,

r\displaystyle r =abq\displaystyle=a-bq (22.12)

Now we will use some ingenuity, and WLOG22 2 Without loss of generality assume that q<qq^{\prime}<q (this is really without loss of generality, because we can always swap rr and rr^{\prime} and qq and qq^{\prime} if q>qq^{\prime}>q - don’t forget that we assumed qqq\neq q^{\prime}), which means (as q,qq,q^{\prime}\in\mathbb{Z}) that qq+1q^{\prime}\geqq q+1

r\displaystyle r ab(q+1)\displaystyle\leqq a-b(q^{\prime}+1) (22.13)
abqb\displaystyle\leqq a-bq^{\prime}-b (22.14)
=rb\displaystyle=r^{\prime}-b (22.15)
<bb\displaystyle<b-b (22.16)
=0\displaystyle=0 (22.17)

The last step follows because r<br^{\prime}<b. This is absurd, as we assumed that r0r\geqq 0, so it certainly cannot be less than zero. Therefore, the remainders and quotients are unique.

22.1.2 A divides b

Definition 22.1.2

We say aa divides bb if and only if b=qa+0b=qa+0 (i.e. there is no remainder when we perform the division).

22.1.3 How large are divisors?

Suppose that n=pqn=pq for n,p,qn,p,q which are all integers. In this case, a question worth asking is how large can p,qp,q be. A little bit of thought reveals that p,qnp,q\leq n (as otherwise neither could divide nn).

So then the next question is that if both pp and qq are less than nn, how large can they be. To solve this we need to consider the fact that n=pqn=pq. 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 pp or qq has to be less than n\sqrt{n}.

Theorem 22.1.2

Let n,p,qn,p,q be integers such that n=pqn=pq. If p,q1p,q\neq 1 and p,qnp,q\neq n, then one of p,qp,q is less than n\sqrt{n}.

Proof: we can prove this statement by contradiction; suppose without loss of generality that pnp\geq\sqrt{n}. If qpq\geq p then

n\displaystyle n =pq\displaystyle=pq (22.18)
>nq\displaystyle>\sqrt{n}q (22.19)
nn\displaystyle\geq\sqrt{n}\sqrt{n} (22.20)
=n\displaystyle=n (22.21)

and n>nn>n is absurd. If q<pq<p then

n\displaystyle n =pq\displaystyle=pq (22.22)
>nq\displaystyle>\sqrt{n}q (22.23)
=\displaystyle= (22.24)

22.1.4 Bezout’s lemma

Theorem 22.1.3

Let a,ba,b\in\mathbb{Z}, then there exists some integers xx and yy such that gcd(a,b)=xa+yb\gcd(a,b)=xa+yb.

TODO: proof

Example 22.1.2

Prove that for all a,b,c{0}a,b,c\in\mathbb{N}-\{0\} it is true that

gcd(a,bc)|gcd(a,b)×gcd(a,c)\gcd(a,bc)|\gcd(a,b)\times\gcd(a,c) (22.25)

We know using Bezout’s lemma that there exist some w,z,y,zw,z,y,z\in\mathbb{Z} such that gcd(a,b)=wa+xb\gcd(a,b)=wa+xb and gcd(a,c)=ya+zc\gcd(a,c)=ya+zc, and therefore

gcd(a,b)×gcd(a,c)\displaystyle\gcd(a,b)\times\gcd(a,c) =(wa+xb)(ya+zc)\displaystyle=(wa+xb)(ya+zc) (22.26)
=waya+wazc+xbya+xbzc\displaystyle=waya+wazc+xbya+xbzc (22.27)
=(way+wzc+xby)a+(xz)bc\displaystyle=(way+wzc+xby)a+(xz)bc (22.28)

and therefore as gcd(a,bc)\gcd(a,bc) divides both aa and bcbc it divides the expression we are after.