So I know when two integers are relatively prime, their greatest common divisor is $1$ and it can we be written as a linear combination as: $1 = am + nb.$ But how would I prove the existence of these integers a and b?
$\begingroup$
$\endgroup$
4
-
1$\begingroup$ use the extended Euclidean algorithm $\endgroup$– J. W. TannerCommented Nov 8, 2019 at 1:53
-
$\begingroup$ Is that working backwards from the Euclidean algorithm? $\endgroup$– user717038Commented Nov 8, 2019 at 1:58
-
$\begingroup$ see this question $\endgroup$– J. W. TannerCommented Nov 8, 2019 at 2:00
-
1$\begingroup$ Scale the Bezout identity $\,m a + n b = 1\,$ by $\,x\,$ to get $\, (xm) a + (xn) b = x\ \ $ $\endgroup$– Bill DubuqueCommented Nov 8, 2019 at 2:26
Add a comment
|