I have to prove the following lemma: $\gcd(ab,c) =\gcd(a,c) \gcd(b,c)$ I am using prime factorization to proof this lemma.

We have $a,b,c\in \mathbb N$

Let the prime factorizations of $a,b,c$ be:

$a = p_1^{a_1}p_2^{a_2}\cdots p_n^{a_n}$

$b = p_1^{b_1}p_2^{b_2}\cdots p_n^{b_n}$

$c = p_1^{c_1}p_2^{c_2}\cdots p_n^{c_n}$

$p_i,a_i,b_i,c_i \in \mathbb N$

I. $ \gcd(ab,c) = p_1^{\min (a_1+b_1,c_1)}p_2^{\min (a_2+b_2,c_2)} \cdots p_n^{\min (a_n+b_n,c_n)}$

II. $gcd(a,c) = p_1^{\min (a_1,c_1)}p_2^{\min (a_2,c_2)} \cdots p_n^{\min (a_n,c_n)}$

III $gcd(b,c) = p_1^{\min (b_1,c_1)}p_2^{\min (b_2,c_2)} \cdots p_n^{\min (b_n,c_n)}$

Now we look at the product $\gcd(a,c)\gcd(b,c)$ which is

$= p_1^{\min (a_1,c_1)}p_1^{{\min} (b_1,c_1)} \cdots p_n^{\min (a_n,c_n)}p_n^{\min (b_n,c_n)}$

$= p_1^{\min (a_1+b_1,c_1)} \cdots p_n^{\min (a_n+b_n,c_n)}$

At Roman I we see how the prime factorization of $\gcd(ab,c)$ looks like. It is the same exponentiation with the added exponents as the product of $\gcd(a,c)$ and $\gcd(b,c)$. Due to this identity $\gcd(ab,c)$ should divide the product of $\gcd(a,c)$ and $\gcd(b,c)$. $\blacksquare$

I don't know whether this proof is correct or not. I would like to receive some feedback.

  • $\begingroup$ I think you had the correct formatting @Anil but forgot to add the dollar signs! I fixed it for you in the edit I made. $\endgroup$
    – Toby Mak
    May 8, 2017 at 12:46
  • $\begingroup$ thank you. I am completely new to mathjax $\endgroup$
    – Anil
    May 8, 2017 at 12:51
  • $\begingroup$ No probs! For a new user, you have done extremely well in formatting! Keep it up! $\endgroup$
    – Toby Mak
    May 8, 2017 at 12:52
  • $\begingroup$ The last part you product gcd's has some issues. For example: you have $p_1^{\min(a_1,c_1)}p_1^{\min(b_1,c_1)}=p_1^{\min(a_1+b_1,c_1)}$. Let $a_1=1$, $b_1=4$, and $c_1=3$ then for the powers you should have equality $\min(1,3)+\min(4,3)=\min(1+4,3)$ that is $4=3$. You only need to check $p_1^{\min(a_1+b_1,c_1)}$ divides $p_1^{\min(a_1,c_1)}p_1^{\min(b_1,c_1)}$, which is easy by what @Paolo Leonetti said. $\endgroup$
    – SaeidAli
    May 8, 2017 at 12:57
  • 1
    $\begingroup$ The equality is not correct, e.g if $\,a=b=c > 1$ then it claims $\,a = (a^2,a) = a\cdot a.\,$ It is true if $\,(a,b,c) = 1.\ $ Double-check the statement of the exercise for the required hypotheses. $\endgroup$ May 9, 2017 at 23:03

1 Answer 1


The exponents are not exactly the same. But, in general, given integers $a,b,c\ge 0$, then $$ \min(a+b,c) \le \min(a,c)+\min(b,c), $$ from which the claimed divisibility follows.

  • $\begingroup$ Okay I got your point, but this isn't the whole proof is it? $\endgroup$
    – Anil
    May 8, 2017 at 13:20
  • $\begingroup$ @Anil This is just the conclusion, the first part of your proof is correct. $\endgroup$ May 8, 2017 at 13:25

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.