2.2 Euclid's Algorithm and Diophantine Equations Flashcards
What is euclids algorithm used for
To find the hcf of 2 integers
Describe how euclids algorithm works
Example 5 and 12
Bigger number: 12
12/5 = 2 r 2
Move the remainder down and start again
2 integers are now 5 and 2
5/2 = 2 r 1
2/1 = 2 r 0
When there is no remainder left, the thing that is left over is the hcf, so 1.
What is a diophantine problem
One where we are only interested in integer solutions to an equation, typically a polynomial with fewer equations than unknowns
Solve 630x + 132y = h where h = hcf(630,132)
How to prove a linear diophantine equation has an integer solution
If and only if h is a factor of c (number on the right) then there is a solution.
If there is a solution to a diophantine linear equation then how many solutions will there be
Infinite
How to find the general solution to ax + by = c
Use euclids to find h = hcf(a,b)
If h is not a factor of c, there no solutions so STOP
Else, run euclids backwards to find the integers satisfying as + bt = c
The general solution is now given by letting k vary in the formulae
x = s + kb/h y = t - ka/h
Find general solution to 1071x + 462y = 42
