For all positive integers \(a\) and \(b\), with \(b \neq 0\), there exist unique integers
\(q\) and \(r\) such that
\( a = bq + r,\quad 0 \le r \lt b. \)
\[
\frac{a}{b}
= q + \frac{r}{b}
\]
\[
a \text{ divided by } b \text{ gives a quotient and remainder.}
\]
\[
\text{The quotient } q \text{ and remainder } r \text{ are integers.}
\]
\[
0 \le r \lt |b|
\]
Convention uses a dot \( \cdot \) to show multiplication instead of \( \times \).
This is fine, since we are purely dealing with integers - no decimals are involved.
Example
Use the division algorithm to find the quotient and remainder when
\(a = 158\) and \(b = 17\).
\[
a = qb + r
\]
\[
158 = 9 \cdot 17 + 5
\]
\[
\text{so } q = 9 \quad \text{and} \quad r = 5
\]
The Euclidean algorithm uses repeated applications of the division algorithm to:
Find the greatest common divisor (gcd)[also known as the highest common factor (hcf)]
\( \gcd(a,b) = \gcd(b,r) \quad \text{where } a = bq + r. \)
\[
\text{The greatest common denominator (gcd)}
\]
\[
\text{of two integers } a \text{ and } b,\ \text{at least one of which } \ne 0,
\]
\[
\text{is found when the remainder in the division algorithm is zero.}
\]
\[
\qquad a = qb + r
\]
\[
\text{so} \qquad a = qb + 0
\]
Example
Find the gcd of 135 and 1780.
\[
\qquad a = qb + r
\]
\[
1780 = 13 \,\cdot\, 135 + 25
\]
\[
\text{Now continue, replacing } a \text{ with } b \text{ and } b \text{ with } r
\]
\[
135 = 5 \,\cdot\, 25 + 10
\]
\[
25 = 2 \,\cdot\, 10 + 5
\]
\[
10 = 2 \,\cdot\, 5 + 0
\]
\[
\gcd(135, 1780) = 5
\]
Find the lowest common multiple (lcm) of two numbers
\( \operatorname{lcm}(a,b) = \dfrac{ab}{\gcd(a,b)} \)
Example
Find the lcm of 135 and 1780.
\[
\operatorname{lcm}
= \frac{ab}{(a,b)}
\]
\[
\qquad = \frac{135 \,\cdot\, 1780}{5}
\]
\[
\qquad = \frac{240300}{5}
\]
\[
\qquad = 48060
\]
\[
\operatorname{lcm}(135, 1780) = 48060
\]
Reduce a fraction to its simplest form
Just divide numerator and denominator by the gcd.
Example
Reduce the fraction \(1480/128600\) to its simplest form.
\[
\qquad a = qb + r
\]
\[
128600 = 86 \,\cdot\, 1480 + 1320
\]
\[
1480 = 1 \,\cdot\, 1320 + 160
\]
\[
1320 = 8 \,\cdot\, 160 + 40
\]
\[
160 = 4 \,\cdot\, 40 + 0
\]
\[
\gcd(128600, 1480) = 40
\]
\[
\text{Divide top and bottom by the gcd}
\]
\[
\frac{1480 \div 40}{128600 \div 40}
= \frac{37}{3215}
\]
Find relatively prime (coprime) integers
These occur when \(\gcd(a,b) = 1\).
Example
Show that 34 and 111 are coprime.
\[
\qquad a = qb + r
\]
\[
\quad 111 = 3 \,\cdot\, 34 + 9
\]
\[
\qquad 34 = 3 \,\cdot\, 9 + 7
\]
\[
\qquad\quad 9 = 1 \,\cdot\, 7 + 2
\]
\[
\qquad\quad 7 = 3 \,\cdot\, 2 + 1
\]
\[
\quad 2 = 2 \,\cdot\, 1 + 0
\]
\[
\gcd(34,\,111) = 1
\]
\[
\therefore\; 34 \text{ and } 111 \text{ are coprime.}
\]
Solve equations of the form
\( \gcd(a,b) = ax + by \)
\[
ax + by = d
\qquad\text{where }\gcd(a,b) = d
\]
\[
\text{then}
\]
\[
x_{n} = x_{0} + \left(\frac{b}{d}\right)m
\]
\[
y_{n} = y_{0} + \left(\frac{a}{d}\right)m
\]
\[
\text{describes the general solution } x_{n},\, y_{n}
\]
\[
\text{when the particular solutions } x_{0},\, y_{0} \text{ are known.}
\]
Example
Solve \(34x + 111y = 1\), where \(x\) and \(y\) are integers.
\[
\qquad a = qb + r
\]
\[
\quad 111 = 3 \,\cdot\, 34 + 9
\]
\[
\qquad 34 = 3 \,\cdot\, 9 + 7
\]
\[
\qquad\quad 9 = 1 \,\cdot\, 7 + 2
\]
\[
\qquad\quad 7 = 3 \,\cdot\, 2 + 1
\]
\[
\quad 2 = 2 \,\cdot\, 1 + 0
\]
\[
\text{change subject to } r \text{ and substitute}
\]
\[
\text{Start with the second last equation and work backwards}
\]
\[
\quad 1 = 7 - 3\cdot 2
\]
\[
\quad\; = 7 - 3\cdot(9 - 1\cdot 7)
\]
\[
\quad\; = 7 - 3\cdot 9 + 3\cdot 7
= 4\cdot 7 - 3\cdot 9
\]
\[
\quad\; = 4\cdot(34 - 3\cdot 9) - 3\cdot 9
= 4\cdot 34 - 15\cdot 9
\]
\[
\quad\; = 4\cdot 34 - 15\cdot(111 - 3\cdot 34)
\]
\[
\quad\; = 49\cdot 34 - 15\cdot 111
\]
\[
\text{compare to original}
\]
\[
34x + 111y = 1
\]
\[
\Rightarrow\; x = 49
\qquad\qquad y = -15
\]
These are equations of the form \(
a x^{n} + b y^{n} = c^{n}
\) , where the solutions are required to be integers
The equation
\(
ax + by + c
\)
has a solution only if the gcd is a factor of c.
To solve,
1) Find
\[
\text{Find} \gcd(a,\,b) = d
\]
\[
\text{then } \; |d| \mid c
\text{ so } \; c = dn \text{ for some integer }n
\]
\[
\text{Express } \; c \text{ in terms of }d
\]
2)
\( \text{Express } d \text{ in the form }
d \;=\; a s \;+\; b t \qquad \text{for some integers } s,t
\)
3)
\[
\text{Multiply by } n \text{ to get }
\qquad x = sn \quad \text{and} \quad y = tn
\]
Example
Solve the linear Diophantine equation \(69x + 27y = 1332\), if a solution exists.
\[
69x + 27y = 1332
\]
\[
\text{Find the gcd of } 69 \text{ and } 27
\]
\[
\quad 69 = 2\cdot 27 + 15
\]
\[
\qquad 27 = 1\cdot 15 + 12
\]
\[
\qquad\quad 15 = 1\cdot 12 + 3
\]
\[
\qquad\quad 12 = 4\cdot 3 + 0
\]
\[
\gcd(69, 27) = 3
\]
\[
\text{since } |3| \mid 1332,\ \text{a solution exists}
\]
\[
c = dn \quad\Rightarrow\quad 1332 = 3n \quad\Rightarrow\quad n = 444
\]
\[
3 = 15 - 1\cdot 12
\]
\[
= 15 - 1\cdot(27 - 1\cdot 15)
= 15 - 1\cdot 27 + 1\cdot 15
= 2\cdot 15 - 1\cdot 27
\]
\[
= 2\cdot(69 - 2\cdot 27) - 1\cdot 27
\]
\[
= 2\cdot 69 - 4\cdot 27 - 1\cdot 27
\]
\[
= 2\cdot 69 - 5\cdot 27
\]
\[
d = 69s + 27t
\]
\[
\Rightarrow\; s = 2
\qquad\qquad t = -5
\]
\[
\text{Multiply through by } n
\]
\[
x = 2n
\qquad\qquad y = -5n
\]
\[
= 2\cdot 444
\qquad\qquad = -5\cdot 444
\]
\[
\text{One solution is }
\quad x = 888,\qquad y = -2220
\]
\[
x_n = x_0 + \left(\frac{b}{d}\right)m
\quad=\quad 888 + \left(\frac{27}{3}\right)m
\quad=\quad 888 + 9m
\]
\[
y_n = y_0 + \left(\frac{a}{d}\right)m
\quad=\quad -2220 + 13m
\]
\[
\text{for some multiple } m
\]
Example
Find the positive integer values of \(x\) and \(y\) that satisfy
\(69x + 27y = 1332\).
\[
\text{From above, a solution exists}
\]
\[
\qquad 69x + 27y = 1332
\]
\[
\gcd(69,\,27) = 3
\]
\[
\qquad 23x + 9y = 444
\]
\[
\text{solving for } x
\]
\[
x = \frac{444 - 9y}{23}
\]
\[
= 19 \frac{7}{23} \;-\; \frac{9y}{23}
\]
\[
= 19 \;-\; \frac{9y}{23} \;+\; \frac{7}{23}
\]
\[
= 19 \;-\; \frac{9y - 7}{23}
\]
\[
\therefore\; \frac{9y - 7}{23} \le 18
\]
\[
\Rightarrow\; y \le \frac{23\cdot 18 + 7}{9}
\]
\[
\Rightarrow\; y \le \frac{421}{9}
\;\le\; 46\frac{7}{9}
\]
\[
0 \lt y \le 46
\qquad\qquad \Delta y = 9
\]
\[
\text{Lowest possible is } y = 11
\]
\[
\text{thus }
x = \frac{444 - 99}{23} = 15
\]
\[
\text{Alternatively, solving for } y
\]
\[
y = \frac{444 - 23x}{9}
\]
\[
= 49 \;-\; \frac{23x - 3}{9}
\]
\[
\therefore\; \frac{23x - 3}{9} \le 48
\]
\[
\Rightarrow\; x \le \frac{48\cdot 9 + 3}{23}
\]
\[
\Rightarrow\; x \le \frac{435}{23}
\;\le\; 18\frac{21}{23}
\]
\[
0 \lt x \le 18
\qquad\qquad \Delta x = 23
\]
\[
\text{Lowest possible answers}
\]
\[
x = 15
\]
\[
y = 49 - \frac{23\cdot 15 - 3}{9}
\]
\[
= 49 - 38
\]
\[
y = 11
\]
\[
\text{check}
\]
\[
69x + 17y
= 69\cdot 15 + 17\cdot 11
= 1035 + 187
= 1332
\]
\( a^{2} + b^{2} = c^{2} \)
To find Pythagorean triples:
Pick an odd positive integer \(n\).
Then \(n^{2}\) can be written as the sum of two consecutive integers:
For example, \(7^{2} = 49 = 24 + 25\), giving the triple \(7, 24, 25\), and
\( 7^{2} + 24^{2} = 25^{2}. \)
Alternatively, pick any even integer \(n\).
Then the triple
\( (2n,\; n^{2}-1,\; n^{2}+1) \)
is Pythagorean.
For example, picking \(n = 8\) gives \(16, 63, 65\), and
\( 16^{2} + 63^{2} = 65^{2}. \)
\( x^{n} + y^{n} = z^{n} \)
Fermat’s Last Theorem states that this equation has no non-zero integer solutions
for \(x, y, z\) when \(n > 2\).
To convert a number into a different
base,
use the Division Algorithm, taking \(b\) as the required base.
Example
Convert 36 into binary.
\[
\qquad a = qb + r
\]
\[
36 = 18\cdot 2 + 0
\]
\[
\text{Now continue, replacing } a \text{ with } q
\]
\[
18 = 9\cdot 2 + 0
\]
\[
9 = 4\cdot 2 + 1
\]
\[
4 = 2\cdot 2 + 0
\]
\[
2 = 1\cdot 2 + 0
\]
\[
1 = 0\cdot 2 + 1
\]
\[
\text{Read the remainder upwards}
\]
\[
36 = 100100 \qquad \text{in base 2}
\]
\[
\text{The base is often shown as a subscript}
\]
\[
36 = 100100_{2}
\]
Example
Convert 36 into hexadecimal.
\[
\qquad a = qb + r
\]
\[
36 = 2\cdot 16 + 4
\]
\[
2 = 0\cdot 16 + 2
\]
\[
36 = 24 \qquad \text{in base 16}
\]
Example
Convert 503793 into hexadecimal.
(Remember that hexadecimal uses
letters.)
\[
\qquad a = qb + r
\]
\[
503793 = 31487\cdot 16 + 1
\]
\[
31487 = 1967\cdot 16 + 15
\]
\[
1967 = 122\cdot 16 + 15
\]
\[
122 = 7\cdot 16 + 10
\]
\[
7 = 0\cdot 16 + 7
\]
\[
503793 = 7 A F F 1 \qquad \text{in base 16}
\]
\[
503793_{\text{dec}}
= 7 A F F 1_{\text{hex}}
\]
© Alexander Forrest