Proof verification: Let $a,b\in \mathbb{Z}_{0}$. If there exists integers $r$ and $s$ such that $ar+bs=1$, show that $gcd(a,b)=1$.

Question

Can someone please verify whether my proof is logically correct? :)

Let $a,b\in \mathbb{Z}_{0}$. If there exists integers $r$ and $s$ such that $ar+bs=1$, show that $gcd(a,b)=1$.

Proof:

Assume that $a$ and $b$ are not relatively prime. Then there exists an integer $k>1$ such that $k|a$ and $k|b$. Then $k|ar+bs$. Then $k|1$, which forms a contradiction ($k>1$ so $k$ does not divide $1$) by assuming $a$ and $b$ are not relatively prime. $\square$

Answer 1

Good job, the proof is correct.

Fact: If $\gcd(a,b)=1$, then there exists integers $r$ and $s$ such that $ar+bs=1$ as well.

Answer 2

It's ok...

But note: it is a little shorter if you don't use reductio ad absurdium...

Namely, suppose $ar+bs=1$ for some $r,s\in \mathbb Z$... Let $k | a$ and $k| b$ both. Then $k | ar+bs=1$, therefore $k=1$...