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

Video solution by Clelland Maths 

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

Video solution by Clelland Maths 

Using the Euclidean algorithm:

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

Video solution by Clelland Maths 

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

Video solution by Clelland Maths 

\(3508\) just means the decimal number \(3508_{10}\small.\)

Base changes can be done using the division algorithm. We repeatedly divide by the base into which we are converting, continuing until the quotient is zero.

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

Note: We can easily check our answer by converting it back to decimal: \(1\!\times\!7^4+3\!\times\!7^3+1\!\times\!7^2+4\!\times\!7^1+1\!\times\!7^0=3508\small.\) ✓

Video solution by Clelland Maths 

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 \(5152_{10}\) 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.\)

Video solution by Clelland Maths 

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

Video solution by Clelland Maths 

We use the division algorithm, repeatedly dividing by the base into which we are converting.

$$ \begin{eqnarray} 572\div 9 &=& 63\ r\,5 \\[4pt] 63\div 9 &=& 7\ r\,0 \\[4pt] 7\div 9 &=& 0\ r\,7 \\[4pt] \end{eqnarray} $$

Reading the remainders backwards, \(572_{10} = 705_9\small.\)

Using the Euclidean algorithm:

$$ \begin{eqnarray} 533 &=& 1\,.\,455+78 \\[4pt] 455 &=& 5\,.\,78+65 \\[4pt] 78 &=& 1\,.\,65+13 \\[4pt] 65 &=& 5\,.\,13+0 \end{eqnarray} $$

So gcd (\(533\),\(\,455\)) = \(13\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} 13 &=& 78-1\,.\,65\\[4pt] &=& 78-1(455-5\,.\,78)\\[4pt] &=& 78-1\,.\,455+5\,.\,78\\[4pt] &=& 6\,.\,78-1\,.\,455\\[4pt] &=& 6(533-1\,.\,455)-1\,.\,455 \\[4pt] &=& 6\,.\,533-6\,.\,455-1\,.\,455\\[4pt] &=& 6\,.\,533-7\,.\,455\\[4pt] \end{eqnarray} $$

So \(a=6\) and \(b=-7\small.\)

(a)  Using the Euclidean algorithm:

$$ \begin{eqnarray} 1118 &=& 2\,.\,416+286 \\[4pt] 416 &=& 1\,.\,286+130 \\[4pt] 286 &=& 2\,.\,130+26 \\[4pt] 130 &=& 5\,.\,26+0 \end{eqnarray} $$

So the greatest common divisor \(d=26\small.\)

(b)  Now we have to find integer solutions \(a\) and \(b\) of \(1118a+416b=26\small.\)

Working backwards from the second last line:

$$ \begin{eqnarray} 26 &=& 286-2\,.\,130\\[4pt] &=& 286-2(416-1\,.\,286)\\[4pt] &=& 286-2\,.\,416+2\,.\,286\\[4pt] &=& 3\,.\,286-2\,.\,416\\[4pt] &=& 3(1118-2\,.\,416)-2\,.\,416 \\[4pt] &=& 3\,.\,1118-6\,.\,416-2\,.\,416\\[4pt] &=& 3\,.\,1118-8\,.\,416\\[4pt] \end{eqnarray} $$

So \(a=3\) and \(b=-8\small.\)