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?

  • $\begingroup$ Look up the "Euclidean Algorithm" $\endgroup$ – Nick Mar 17 '16 at 20:08
  • $\begingroup$ Look up the "Extended Euclidean Algorithm" $\endgroup$ – mvw Mar 17 '16 at 20:09
  • $\begingroup$ I see how that works but how does it relate to this? $\endgroup$ – 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.

| cite | improve this answer | |
  • $\begingroup$ What do you mean smallest possible integers? 0? $\endgroup$ – Augs Mar 17 '16 at 20:27
  • $\begingroup$ Sorry I meant positive. Autocorrect $\endgroup$ – Augs Mar 17 '16 at 20:37
  • $\begingroup$ 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? $\endgroup$ – Augs Mar 17 '16 at 20:42
  • $\begingroup$ Where did I say they were positive? Indeed you have just established that only one of $k,l$ will be positive! $\endgroup$ – almagest Mar 17 '16 at 21:30
  • $\begingroup$ Ah you were talking about the whole sum being positive $\endgroup$ – Augs Mar 17 '16 at 21:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.