3
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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

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

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ I'm not sure I understand what your hint is referring to. Can you offer a little more clarification please? $\endgroup$ – user6548 Feb 2 '11 at 20:48
  • $\begingroup$ @user6548: $gn+g = g(n+1)$. If $g|s$, can you write $s$ as $g(n+1)$ for some $n$? $\endgroup$ – Arturo Magidin Feb 2 '11 at 20:51
  • $\begingroup$ 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? $\endgroup$ – user6548 Feb 2 '11 at 21:07
  • $\begingroup$ @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$? $\endgroup$ – Arturo Magidin Feb 2 '11 at 21:08
  • $\begingroup$ Ah, that clears things up perfectly. Thank you. $\endgroup$ – user6548 Feb 2 '11 at 21:18
1
$\begingroup$

$\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$

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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