Division theorem, Euclidean algorithm and Bezout's identity
Studying this course? Keep your progress in one place.
Key facts
- Division theorem: with , where is the quotient and the remainder.
- Euclidean algorithm: ; the last non-zero remainder is the hcf.
- , and integers with hcf are coprime.
- Bezout's identity: has integer solutions, found by back substitution.
- has integer solutions if and only if divides .
The division theorem
Any integer can be written with a unique quotient and remainder .
For integers and with , there are unique integers (the quotient) and (the remainder) with and .
Example: , so and .
In congruence notation, . Also exactly when divides . The theorem is the engine of the Euclidean algorithm.
- Division theorem
Write in the form with . What is ?
The Euclidean algorithm
Repeat the division theorem on the divisor and remainder; the last non-zero remainder is the hcf.
The highest common factor is the largest integer dividing both.
The key fact is : any common divisor of and divides , and any common divisor of and divides .
Repeat until the remainder is . Two integers with hcf are coprime, and .
Write every line as in full; you need it for back substitution.
- 1
Divide
write
- 2
Replace
move on to and
- 3
Repeat
until the remainder is 0
- 4
Read off
the last non-zero remainder is the hcf
Worked example
Find and .
- 1
- 2
- 3
- 4
- 5
The last non-zero remainder is , so .
What is ?
Bezout's identity
There are always integers with , found by working back up the algorithm.
Bezout's identity: for integers (not both zero) there exist integers with .
Find and by back substitution: rearrange each step of the algorithm as , then work upwards from the line with the hcf, replacing each remainder in turn.
Keep and as unevaluated terms and collect them at the end; expanding early makes it easy to lose track of which remainder is which.
- Bezout's identity
Worked example
Express in the form .
- 1
Forward: , , , . The hcf is .
- 2
Back: .
- 3
Replace : .
- 4
Replace : .
- 5
Replace : .
If , which statement must be true?
When ax + by = c is solvable
Exactly when divides .
Since divides for all integers , the equation has integer solutions if and only if divides .
If and , multiply the Bezout solution by .
In particular, and are coprime if and only if has a solution.
To show no solution exists, state the hcf and that it does not divide .
hcf divides c
- Integer solutions exist
- Scale the Bezout solution by c/d
hcf does not divide c
- No integer solutions
Worked example
Decide whether and have integer solutions.
- 1
, , , , so .
- 2
, so has no solution.
- 3
, so does. Back: .
Does have integer solutions?
Try an exam question
Use the Euclidean algorithm to find , and hence find integers and such that .
[4 marks]
- [1], , .
- [1].
- [1]Back substitution: .
- [1], so and .
That's the notes covered.
Carry on to the next subtopic.
Try a question
Write with . Find .
1 mark, marked against the mark scheme
Write with . Find .
1 mark, marked against the mark scheme