Skip to main content

Section 2.1 Division Algorithm

If \(a\) is a multiple of \(b,\) then we are done, since \(a=qb\) and \(r=0.\)

If \(a\) is not a multiple of \(b,\) by the combination of the Archimedean Property and the Well-Ordering Principle, there is a maximum (hence unique) \(q\) such that

\begin{equation} qb\lt\vert a\vert \lt (q+1)b\label{Eqn-2_1}\tag{2.1.1} \end{equation}

Set \(r=\vert a\vert-qb.\) Note that \(r\) is unique since \(q\) is unique. By subtracting \(qb\) from each part of (2.1.1), we get the needed condition \(0\lt r\lt b.\)

Remark 2.1.2.

If \(n\) is a square, then when divided by \(4,\) \(n\) leaves a remainder of \(0\) or \(1.\)

To prove this let \(n=a^2.\) The Division Algorithm gives \(a=4q+r\) where \(r=0,1,2,3,\) so that

\begin{equation*} n=(4q+r)^2=16q^2+8qr+r^2. \end{equation*}

Now if \(r=0,\) then \(n=4(4q^2+2qr)+0;\) if \(r=1,\) then \(n=4(4q^2+2qr)+1;\) if \(r=2,\) then \(n=4(4q^2+2qr+1)+0;\) if \(r=3,\) then \(n=4(4q^2+2qr+2)+1.\) In each case, the remainder is \(0\) or \(1.\)

Remark 2.1.3.

The Division Algorithm is just grade school division in disguise.

Definition 2.1.4.

We say that a non-zero integer \(a\) divides \(b,\) and write \(a\vert b,\) if there is some integer \(c\) such that \(b=ac.\)

We will prove just \((f)\) and \((g),\) the rest are left to the reader.

For \((f),\) note that if \(a\vert b\) and \(b\neq 0,\) then there is a \(c\in\mathbb{Z}\) with \(c\neq 0\) such that \(b=ac.\) Thus \(\vert b\vert =\vert a\vert \vert c\vert.\) Now \(\vert c\vert \geq 1\) so multiplying on each side by \(\vert a\vert\) gives

\begin{equation*} \vert a\vert \leq \vert a\vert \vert c\vert =\vert b\vert. \end{equation*}

For \((g),\) we have that \(a\vert b\) and \(a\vert c\) give the existence of \(n,m\in\mathbb{Z}\) such that \(b=an\) and \(c=am.\) Now for any \(x,y\in\mathbb{Z}\) we have

\begin{equation*} bx+cy=anx+amy=a(nx+my), \end{equation*}

so that \(a\vert (bx+cy)\) for any integers \(x\) and \(y.\)

Definition 2.1.6.

The greatest common divisor of \(a,b\in\mathbb{Z}\) is the number \(d\gt 0\) such that

  1. \(d\vert a\) and \(d\vert b\)

  2. if \(c\vert a\) and \(c\vert b,\) then \(c\leq d.\)

Definition 2.1.7.

Two integers \(a,b\) are said to be relatively prime or coprime, provided \(\gcd(a,b)=1.\)

Consider the set \(S\) of all linear combinations of \(a,b\text{:}\)

\begin{equation*} S=\{au+bv: au+bv\gt 0, u,v\in\mathbb{Z}\} \end{equation*}

The set \(S\) is non-empty since if \(u=1, v=0\) we have \(a\in S.\) By the Well Ordering Principle, \(S\) must contain a smallest element \(d.\) Thus by the definition of \(S,\) there are \(x,y\in\mathbb{Z}\) such that \(d=ax+by.\) (We claim \(\gcd(a,b)=d.\))

Using the division algorithm, we can obtain integers \(q,r\) such that \(a=qd+r,\) where \(0\leq r\lt d.\) So \(r\) can be written

\begin{equation*} r = a-qd = a-q(ax + by) = a(1-qx) + b(-qy). \end{equation*}

Now if \(r\gt 0,\) than this implies \(r\in S,\) but \(r\lt d,\) the smallest element. Thus \(r = 0,\) so \(a = qd\) and so \(d\vert a.\) Likewise \(d\vert b,\) and so \(d\) is a common divisor of a and b. Now if c is another common divisor of \(a\) and \(b,\) then \(c\vert (ax + by)=d,\) so that \(c\leq d.\) Thus \(d\) is the greatest common divisor of \(a\) and \(b,\) and there exist \(x,y\in\mathbb{Z}\) such that \(ax+by=\gcd(a,b).\)

For \(n\in\mathbb{N},\) we have \(\gcd(n,n+1)=1.\) This is easy to see using the previous theorem. Note that for \(x=-1\) and \(y=1\) we have

\begin{equation*} 1=ax+by=n\cdot(-1)+(n+1)\cdot 1. \end{equation*}