I want to check the validity of my proof to the following question.

Prove that (a,b) = (a,b,a+b) and more generally (a,b) = (a,b,ax+by).

Note that (a,b) is the greatest common divisor of $a$ and $b$, $a$ and $b$ are integers.

My Prove:

let $(a,b)$ = $g$ and $(a,b,a+b)$ = $g^*$. Since $g$|$a$, $g|b$ $\rightarrow$ $g|a+b$ implying that $g|g^*$. On the other hand, $g^*|a$, $g^*|b$, following that $g^*|g$.

From the previous argument, $g=\pm g^*$. However, $g,g^*$, by definition, cannot be negative, thereby, $g=g^*$ as required. The general case can be proved analogously.

Thanks in advance

  • $\begingroup$ Compare with the proof here, which also gives your claim. $\endgroup$ – Dietrich Burde Sep 17 '18 at 12:06
  • $\begingroup$ Thanks for commenting @DietrichBurde, nevertheless, it did not give a proof to the question I am asking neither check the proof I wrote. $\endgroup$ – Maged Saeed Sep 17 '18 at 12:15
  • $\begingroup$ Yes, but you can easily check your proof with the given standard proofs. Do you have a special doubt about your proof? Then this would improve your question. Actually, $g\mid g*$ and $g*\mid g$ imply that $g$ and $g*$ are associated, and not necessarily $g=\pm g*$. Think of the ring $\Bbb{Z}[i]$. $\endgroup$ – Dietrich Burde Sep 17 '18 at 12:26
  • $\begingroup$ to the point I am supposed to know "I did not do group and ring theory yet", it seems that my proof is correct. Thanks for your useful notes @DietrichBurde $\endgroup$ – Maged Saeed Sep 17 '18 at 12:52
  • $\begingroup$ @Maged Saeed The (slight) problem is that you assume everybody knows what notation you use and about what kind of numbers you talk. $(a,b)$ can mean a many different things in math, depending on which branch you are in. And you don't state what kind of numbers $a,b\ldots$ are. I think you talk about integers, but you never mention it anywhere. It can be guessed only from mentions of 'negative', which don't make sense in many contexts where your question would otherwise make total sense. $\endgroup$ – Ingix Sep 17 '18 at 13:29

This proof is fine.

Depending on the level of your audience*, you may want to be more explicit in the implication "$g|a$ and $g|b$ implies $g|a+b$". In any case, showing the details here would certainly make the "analogously" for the general case more believable; as it is currently written, it took me a minute to see exactly how the analogy worked.

(* If you are in a course, and you don't have other instructions, a good rule of thumb is: your audience consists of you-from-a-week-ago, the weakest student in the course, and the grader.)


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.