In Pinter's book it states that the greatest common divisor of a and b can be written as the linear combination:
$t=la + kb $ for some integers $l$ and $b$
What is the proof of this?
Asked
Active
Viewed 156 times
0
-
Look up the "Euclidean Algorithm" – Nick Mar 17 '16 at 20:08
-
Look up the "Extended Euclidean Algorithm" – mvw Mar 17 '16 at 20:09
-
I see how that works but how does it relate to this? – Augs Mar 17 '16 at 20:40
1 Answers
0
This is standard bookwork. Take the smallest positive $la+kb$ for integers $l,k$. Call it $d$. Suppose it does not divide $a$. Then we have $a=qd+r$ with $0<r<d$, but $r$ is a linear combination of $a,b$. Contradiction. Similarly $d$ must divide $b$ and hence $t$. But $t$ obviously divides $d$, so they are equal.
almagest
- 18,380
-
-
-
Also if l and k are positive won't t be bigger than a and b? How can the common divisor be bigger that either a or b? – Augs Mar 17 '16 at 20:42
-
Where did I say they were positive? Indeed you have just established that only one of $k,l$ will be positive! – almagest Mar 17 '16 at 21:30
-
-