1
$\begingroup$

I want to prove the basic property of gcd that for some integer $a,b$ $gcd(a,b) = 1$ iff there exists some integers $k$ and $l$ in $ak + bl = 1$. I've been using this basic property for a long time and always assumed it to be true, but cannot find a basic proof for this.

I would express the gcd as the smallest linear combination of a and b, but this will force me to conclude that since 1 is the smallest linear combination, then the iff condition is satisfied. But this doesn't seem to be the right approach however intuitive, since I did not prove the implication both ways. Is there a way I could formally prove this?

$\endgroup$
3
$\begingroup$

One direction is easy, namely if $ax+by=1$, then the gcd is $1$.

For the converse you can use the Euclidean algorithm. See Bezóut's identity . ..

$\endgroup$
0
$\begingroup$

If I understand which direction you are trying to prove:

Suppose $d>0$ divides both $a$ and $b$, with $a=ed$ and $b=fd$.

Then given that $ak + bl = 1$, we have $(ke+fl)d=1$, so $d$ divides $1$, meaning that $d \le 1$. Combined with $d>0$ this gives $d=1$.

$\endgroup$
-1
$\begingroup$

The proof is rather long. but if you're interested you could look in this book which is a number theory book. http://www.fuchs-braun.com/media/532896481f9c1c47ffff8077fffffff0.pdf The theorem is called theorem 1.3 and it is stated and proven on page seven

$\endgroup$

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.