# 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 $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

###### Definition 22.1.1

Let $a,b\in\mathbb{Z}$ with $b>0$. We say that $a$ divides $b$ with remainder $r$ if and only if there exists a $q\in\mathbb{Z}$ such that

$a=bq+r.$ (22.1)

This is simple enough, e.g. if $a=12$ and $b=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\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 - 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.

###### Example 22.1.1

Taken together this gives us this theorem

###### Theorem 22.1.1

Let $a,b\in\mathbb{Z}$ and $b>0$, then there exist unique $q$ and $r$ where $0\leqq 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 $r\geqq 0$ which satisfy the properties the remainder should have.

• Prove that therefore there exists at least one $r 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.

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

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

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

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

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

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 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. 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

$r-b<0.$ (22.8)

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

 $\displaystyle r-b$ $\displaystyle=a-bq-b$ (22.9) $\displaystyle=a-b(q+1)$ (22.10)

Let $r^{\prime}=a-b(q+1)$. We know that $r^{\prime}\in S$! Now, we also know that $r^{\prime} (this is because $a-bq 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

$r-b<0.$ (22.11)

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}. 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$,

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

Now we will use some ingenuity, and WLOG22 2 Without loss of generality assume that $q^{\prime} (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$

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

The last step follows because $r^{\prime}. 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.

## 22.1.2 A divides b

###### Definition 22.1.2

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

## 22.1.3 How large are divisors?

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}$.

###### Theorem 22.1.2

Let $n,p,q$ be integers such that $n=pq$. If $p,q\neq 1$ and $p,q\neq n$, then one of $p,q$ is 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

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

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

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

## 22.1.4 Bezout’s lemma

###### Theorem 22.1.3

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

TODO: proof

###### Example 22.1.2

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

$\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,z\in\mathbb{Z}$ such that $\gcd(a,b)=wa+xb$ and $\gcd(a,c)=ya+zc$, and therefore

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

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

$\Box$