I was trying to prove that if $d \mid a$ and $d \mid b$ then $d \mid \gcd(a,b)$ but wanted a proof that didn't require me to know that $\gcd(a,b) = ax + by$, i.e. that didn't require me to know that the $\gcd(a,b)$ was a linear combination of $a$ and $b$. With that knowledge the proof is trivial (plus for further understanding I wanted a different perspective on this fact that seems to me that doesn't necessarily require that knowledge).

I was trying to think in terms of factorizations to see if I could make it work and these are my current thoughts: if some prime number $p$ divides $a$, and it divides $b$, then it must also divide the GCD. This seems intuitive for primes but if the divisor $d$ is not a prime, I am not sure how to extend the argument. Anyone have any ideas?

  • $\begingroup$ $gcd$ is a factor of both $a$ and $b$ $\endgroup$ – Anthony Oct 7 '15 at 15:18
  • $\begingroup$ @Anthony so? just because $d$ divides both a and b its not necessarily obvious it must divide the gcd of a and b. Only if d were prime its obvious. $\endgroup$ – Charlie Parker Oct 7 '15 at 15:20
  • $\begingroup$ As it has been answered, $d=p_1^{\alpha_1}\times\ldots\times p_r^{\alpha_r}$ $\endgroup$ – Anthony Oct 7 '15 at 15:26
  • $\begingroup$ One could answer, the Fundamental Theorem of Arithmetic. But then comes the question, how does one prove the FTA? Usually Euclid's Lemma, with usual proof using the Bezout Identity! However, in The Higher Arithmetic, Davenport shows how to sidestep that. $\endgroup$ – André Nicolas Oct 7 '15 at 15:35

Well, if you are willing to use Unique Factorization then, for every prime $p$, $ord_p$ of the gcd is $\min(ord_p(a),ord_p(b))$. But your assumption on $d$ implies that $ord_p(d) \leq \min(ord_p(a),ord_p(b))$.

To elaborate: in the above, $ord_p(n)$ denotes the largest integer $a_p$ such that $p^{a_p}$ divides $n$. Thus, for example, $ord_2{12}=2$, $ord_3{12}=1$. Unique Factorization tells you that $$n=\prod_{p\;prime}p^{ord_p(n)}$$

It follows quickly that $d$ divides $n\;\iff\;ord_p(d)≤ord_p(n)\;\forall\;p$. This quickly implies that $$gcd(a,b)=\prod_{p\;prime}p^{min(ord_p(a),ord_p(b))}$$

I think this should be enough to help you fill in the gaps in my initial argument.

Note: I am not a big fan of this proof, as I think Unique Factorization is a deeper result than the statement about getting the gcd as a linear combination of the terms. Indeed, it is not unusual to use the linear combination principle along the path toward proving Unique Factorization.

  • $\begingroup$ I won't lie to you but I don't quite follow your proof. I'm not familiar with what $ord_p$ means or how those inequality matter. I need more details/explanation for it to make sense. Sorry, but at least I was honest. $\endgroup$ – Charlie Parker Oct 7 '15 at 15:55
  • $\begingroup$ I elaborated somewhat, see the edits. $\endgroup$ – lulu Oct 7 '15 at 16:05

By definition, GCD is the largest integer number that divides $a$ and $b$.

  • $\begingroup$ So you get that $d < \text{gcd}(a,b)$, but how do you deduce from this definition that $d | \text{gcd}(a,b)$? $\endgroup$ – Tryss Oct 7 '15 at 15:28
  • $\begingroup$ Well that's exactly what we are trying to prove in a formal way $\endgroup$ – Shailesh Oct 7 '15 at 15:43
  • $\begingroup$ By that definition, $\gcd (a,b)$ must be divisible by every number that divides both $a$ and $b$. $\endgroup$ – 1-___- Oct 7 '15 at 15:44
  • 1
    $\begingroup$ I mean, if you want every single tiny detail then prime factorization is the way to go. $\endgroup$ – 1-___- Oct 7 '15 at 15:44
  • $\begingroup$ with all due respect, you think I didn't know what the definition of GCD was before posting my question? It should be clear that it wasn't going to be a satisfying answer for me. $\endgroup$ – Charlie Parker Oct 7 '15 at 15:56

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.