# Proving that if $xo + yp = 1$, then $\gcd(o,p) = 1\;$?

I'm currently trying to prove the equation that you see above.

I know that it must have something to do with the laws of divisibility, and these rules in conjunction with rules about integers, but other than that I'm rather stumped as to how one might begin looking at a problem like this.

I tried setting all the given variables equal to the rest of them, but couldn't really go anywhere with that. Any help/suggestions of ways to approach and think about this problem is most appreciated!

-
We don't usually like to use the letter 'o' as a variable because it looks so much like a number zero that people will be confused. –  MJD Dec 6 '12 at 22:11
If I'm not mistaken, the greatest common divisor of 0 and p is p. So, is that 0 or O, that is involved? –  Chris Leary Dec 6 '12 at 22:12
I assume Bezout's lemma is off-limits? –  Mike Dec 6 '12 at 23:54

If you don't mind, I will use $a$ for your $o$ and $b$ for your $p$.

Suppose that $d\ge 1$ divides $a$ and $b$. Then $d$ divides $xa+yb$. So $d$ divides $1$. We conclude that $d=1$.

Thus nothing bigger than $1$ divides both $a$ and $b$. It follows that the gcd of $a$ and $b$ is $1$.

We used the fact that if $d$ divides $a$ and $b$, then $d$ divides $xa+yb$. For completeness, let's prove it.

Because $d$ divides $a$, we have $a=dm$ for some integer $m$. similarly, $b=dn$ for some integer $n$. It follows that $$xa+yb=xdm+ydn=d(xm+yn),$$ so $d$ divides $xa+yb$.

Remark: Why reject the letters $o$ and $p$? The letter $o$ can look a lot like the number $0$, which occurs very often in mathematics. And in number theory, as much as possible we reserve the letter $p$ as a name for a prime.

-