Take the 2-minute tour ×
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.

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|improve this question
add comment

2 Answers 2

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

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

share|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
add comment

$\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|improve this answer
add comment

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.