1
$\begingroup$

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!

  • 0
    I assume Bezout's lemma is off-limits?2012-12-06

1 Answers 1

4

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.