# How can the gcd(a,b), t, be written as a linear combination t=la +kb for some integers?

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?

• 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

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.
• 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