The Division Algorithm

For all positive integers a  and b,
where b ≠ 0,

1

   2

 

Example

Use the division algorithm to find
the quotient and remainder when
a = 158 and b = 17

 

3

The Euclidean Algorithm

This uses the division algorithm to:-

[ aka  highest common factor (hcf)]

4

 

    45  

(just divide top and bottom by the gcd)

These occur when the gcd (a,b) = 1

     gcd (a,b) =ax +by

6

 

Example

Find the gcd of  135 and 1780

8

 

Example

Find the lcm of  135 and 1780

7

 

Example

Reduce the fraction 1480/128600 to
its simplest form

9

 

Example

Show that  34 and 111 are co prime

10

 

Example

Solve  34x + 111y = 1 ,
where x and y are integers

11

12

Diophantine Equations

These are of the form

13

 

14

Example

Solve the linear Diophantine Equation
69x +27y = 1332, if it exists

15

16

17

 

Example

Find the positive integer values of x  and y that satisfy
69x +27y = 1332

18

19

20

22

21

 

Pythagorean Triples

12

To find these,
Pick an odd positive number
Divide its square into two integers which are
as close to being equal as is possible

e.g. 72 = 49 = 24 + 25
gives triples  7, 24, 25
                    72 + 242 = 252

 

Alternatively, pick any even integer n
triples are  2n , n2- 1 and n2 + 1
e.g. picking 8 gives  16, 63 and 65 
Indeed 162 + 632 = 652

 

Fermat’s LastTheorem

12

Number Bases

To convert a number into a different base,
use the Division Algorithm , taking b as the
 required base.

Example

Convert 36 into  binary 

25

26

Example

Convert 36 into hexadecimal

27

Example

Convert 503793 into hexadecimal
( Remember that hexadecimal uses letters

28

 

 

 

© Alexander Forrest