Advanced Higher Maths
Number Theory

The Euclidean algorithm is just repeated use of the theorem known as the division algorithm. We repeatedly divide the divisor by the remainder until the remainder is 0.

$$ \begin{array}{ll} 98=2\,.\,35+28&\small\textsf{so gcd(98,35) = gcd(35,28)} \\ 35=1\,.\,28+7&\small\textsf{so gcd(35,28) = gcd(28,7)} \\ 28=4\,.\,7+0&\small\textsf{so gcd(28,7) = 7} \\ \end{array} $$

Therefore the greatest common divisor of \(98\) and \(35\) is \(7\small.\)

Highest common factor (hcf) is the same as greatest common divisor (gcd).

$$ \begin{eqnarray} 714 &=& 3\,.\,221+51 \\[4pt] 221 &=& 4\,.\,51+17 \\[4pt] 51 &=& 3\,.\,17+0 \\[4pt] \end{eqnarray} $$

Therefore hcf (\(714\),\(\,221\)) = \(17\small.\)

$$ \begin{eqnarray} 319 &=& 2\,.\,132+55 \\[4pt] 132 &=& 2\,.\,55+22 \\[4pt] 55 &=& 2\,.\,22+11 \\[4pt] 22 &=& 2\,.\,11+0 \end{eqnarray} $$

So gcd (\(319\),\(\,132\)) = \(11\small.\)

Now we work backwards from the second last line, rewriting each remainder as a difference and simplifying before moving back another line:

$$ \begin{eqnarray} 11 &=& 55-2\,.\,22 \\[4pt] &=& 55-2(132-2\,.\,55) \\[4pt] &=& 55-2\,.\,132+4\,.\,55 \\[4pt] &=& 5\,.\,55-2\,.\,132 \\[4pt] &=& 5(319-2\,.\,132)-2\,.\,132 \\[4pt] &=& 5\,.\,319-10\,.\,132-2\,.\,132 \\[4pt] &=& 5\,.\,319-12\,.\,132 \end{eqnarray} $$

So \(a=5\) and \(b=-12\small.\)

$$ \begin{eqnarray} 612 &=& 4\,.\,133+80 \\[4pt] 133 &=& 1\,.\,80+53 \\[4pt] 80 &=& 1\,.\,53+27 \\[4pt] 53 &=& 1\,.\,27+26 \\[4pt] 27 &=& 1\,.\,26+1 \\[4pt] 26 &=& 26\,.\,1+0 \end{eqnarray} $$

So gcd (\(133\),\(\,612\)) = \(1\small.\)

Now we work backwards from the second last line, rewriting each remainder as a difference and simplifying before moving back another line:

$$ \begin{eqnarray} 1 &=& 27-1\,.\,26 \\[4pt] &=& 27-1(53-1\,.\,27) \\[4pt] &=& 27-1\,.\,53+1\,.\,27 \\[4pt] &=& 2\,.\,27-1\,.\,53 \\[4pt] &=& 2(80-1\,.\,53)-1\,.\,53 \\[4pt] &=& 2\,.\,80-2\,.\,53-1\,.\,53 \\[4pt] &=& 2\,.\,80-3\,.\,53 \\[4pt] &=& 2\,.\,80-3(133-1\,.\,80) \\[4pt] &=& 2\,.\,80-3\,.\,133+3.80) \\[4pt] &=& 5\,.\,80-3\,.\,133 \\[4pt] &=& 5(612-4\,.\,133)-3\,.\,133 \\[4pt] &=& 5\,.\,612-20\,.\,133-3\,.\,133 \\[4pt] &=& 5\,.\,612-23\,.\,133 \end{eqnarray} $$

So \(x=-23\) and \(y=5\small.\)

Base changes can be done using the division algorithm. We repeatedly divide by the base into which we are converting.

$$ \begin{eqnarray} 3508\div 7 &=& 501\ r\,1 \\[4pt] 501\div 7 &=& 71\ r\,4 \\[4pt] 71\div 7 &=& 10\ r\,1 \\[4pt] 10\div 7 &=& 1\ r\,3 \\[4pt] 1\div 7 &=& 0\ r\,1 \\[4pt] \end{eqnarray} $$

Reading the remainders backwards, \(3508_{10} = 13141_7\small.\)

First we convert \(7054_{9}\) into decimal:

$$ \begin{eqnarray} 7054_{9} &=& 7\!\times\!9^3+0\!\times\!9^2+5\!\times\!9^1+4\!\times\!9^0 \\[4pt] &=& 5103+45+4 \\[4pt] &=& 5152_{10} \\[4pt] \end{eqnarray} $$

Now we use the division algorithm to convert this into base \(8\small.\)

$$ \begin{eqnarray} 5152\div 8 &=& 644\ r\,0 \\[4pt] 644\div 8 &=& 80\ r\,4 \\[4pt] 80\div 8 &=& 10\ r\,0 \\[4pt] 10\div 8 &=& 1\ r\,2 \\[4pt] 1\div 8 &=& 0\ r\,1 \\[4pt] \end{eqnarray} $$

Reading the remainders backwards, we get \(12040_8\small.\)

(a)  We use Euclid's algorithm as follows:

$$ \begin{eqnarray} 703 &=& 1\,.\,399+304 \\[4pt] 399 &=& 1\,.\,304+95 \\[4pt] 304 &=& 3\,.\,95+19 \\[4pt] 95 &=& 5\,.\,19+0 \\[4pt] \end{eqnarray} $$

Therefore gcd (\(703\),\(\,399\)) = \(19\small.\)

(b)  We use our answer to part (a) and back-substitution, as follows:

$$ \begin{eqnarray} 19 &=& 304-3\,.\,95 \\[4pt] &=& 304-3(399-1\,.\,304) \\[4pt] &=& 4\,.\,304-3\,.\,399 \\[4pt] &=& 4(703-1\,.\,399)-3\,.\,399 \\[4pt] &=& 4\,.\,703-7\,.\,399 \\[4pt] \end{eqnarray} $$

So a solution is \(a=4\small,\) \(b=-7\small.\)

(c)  This part relies on us knowing that \(4\times 19=76\small,\) so the equation is simply multiplied through by \(4\small.\)

So \(p=4a=16\) and \(q=4b=-28\small.\)