22.1 Division

If you thought division was hard enough, then unfortunately it gets worse. Much worse.

Here’s a really weird question: consider some integers $a$ and $b$. Let’s suppose that $b>0$, in which case we can ask does $a$ divide $b$? I mean, yes?

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

This is simple enough, e.g. if $a=12$ and $b=3$, it is a truth universally acknowledged¹¹ 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\times 3+0$, so we can say that $3$ divides $12$ 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 $12$ by $3$ the quotient is $4$ because $4\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 $0\leqq r<b$ - this should make sense if you consider that if the remainder was greater than $b$, we can just increase the quotient by one, and decrement the remainder.

Taken together this gives us this theorem

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

• •
  ​

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

• •
  ​

  Prove that the remainder is therefore unique.

We start by defining a set $S$ 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 $S$ contains some positive members. This is not too bad. We do a proof by exhaustion here; either $a\geqq 0$ or $a<0$. In the first case, we have some $r\in S$ where $r\geqq 0$ because we can set $q=0$ which gives us

And in this case $a\geqq 0$, so we have a desired $r\in S$.

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

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

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

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

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

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

This was our goal!

All that remains to show is that $r$ and $q$ are unique. We will employ the standard method (as outlined in Section 6.7), and assume that we have $r,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 $r\neq r^{\prime}$ and $0\leqq r,r^{\prime}<b$. We will also let $q,q^{\prime}\in\mathbb{Z}$ such that $q\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 $r$,

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

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

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

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

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

and $n>n$ is absurd. If $q<p$ then

TODO: proof

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

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

$\Box$