Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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!

share|cite|improve this question
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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.