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.

So obviously because of the if and only if we must first prove that

If there exist integers $x$ and $y$ such that $x+y=S$ and $(x,y)=G$ then $G\mid S$.

And then if $G\mid S$, then there exist integers $x$ and $y$ such that $x+y=S$ and $(x,y)=G$.

Please help

share|improve this question
Cindy, please do not delete the question, leaving only "prove if and only if": Someone took the time to answer your question, which makes little sense without the question! –  amWhy Dec 9 '12 at 22:43
I have reverted the question to the original question. Please do not again overwrite it with a new question (which invalidates the answer below). Instead, please post the new question separately. –  Bill Dubuque Dec 10 '12 at 0:53
add comment

1 Answer 1

$G|x$ and $G|y$, hence $Gp=x$ and $Gq=y$ for some integers $p,q$. Thus, $G(p+q)=x+y$. therefore $G|x+y$

Converse: If $S=kG$, let $x=G$ and $y=(k-1)G$

share|improve this answer
I forgot a part of the question I will edit my answer –  Amr Dec 9 '12 at 22:03
could you elaborate on the converse? –  Cindy Dec 9 '12 at 22:12
Check that $x,y$ given in the converse satisfy $(x,y)=G$ and $x+y=S$ –  Amr Dec 9 '12 at 22:14
@Cindy: Just do the algebra. With Amr’s suggested values of $x$ and $y$, what are $x+y$ and $(x,y)$? –  Brian M. Scott Dec 9 '12 at 22:14
So with the converse y=(k-1)G => y=kG-G => y=S-G => y=S-x => x+y=S but how do you show (x,y)=G? –  Cindy Dec 9 '12 at 22:17
show 3 more comments

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.