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