Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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 am already able to prove that $g \mid s$ assuming $x+y=s$ and $(x,y)=g$, but I am having some trouble showing that assuming $g \mid s$, there exists an $x$ and $y$ such that $x+y=s$ and $(x,y)=g$. So far, I've started with saying that $g \mid 0$ necessarily. Therefore we also know that $g \mid (0x+sy)$. I'd like to be able to set the values of $x$ and $y$ to something to show that there exist an $x$ and a $y$ that satisfy $x+y=s$ and $(x,y)=g$, but I'm not really sure where to go from here. Can anyone offer any help?

share|cite|improve this question

HINT. $(gn,g) = g(n,1)=g$.

The converse follows because $a|b$ and $a|c$ implies $a|b+c$.

share|cite|improve this answer
I'm not sure I understand what your hint is referring to. Can you offer a little more clarification please? – user6548 Feb 2 '11 at 20:48
@user6548: $gn+g = g(n+1)$. If $g|s$, can you write $s$ as $g(n+1)$ for some $n$? – Arturo Magidin Feb 2 '11 at 20:51
I'm very sorry, but I'm still having trouble wrapping my head around how this fits in. Does this eliminate the need to mention that g|0 and thus, the need to mention that g|(0x+sy)? If not, how do these follow one another? – user6548 Feb 2 '11 at 21:07
@user6548: If $g|s$, then $s=gd$ for some $d$. Write $d=(d-1)+1$. Can you now write $s$ as the sum of $gn$ and $g$ for some $n$? – Arturo Magidin Feb 2 '11 at 21:08
Ah, that clears things up perfectly. Thank you. – user6548 Feb 2 '11 at 21:18

$\rm\ \ g = (x,s-x) = (x,s)\ \iff\ 1 = (x/g,\:s/g)\:,\ $ so choose $\rm x/g\ $ coprime to $\rm s/g\:,\ $ e.g. $\rm\ s/g + 1$

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.