# Is my proof for this lemma of gcd correct?

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.

• 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. – Toby Mak May 8 '17 at 12:46
• thank you. I am completely new to mathjax – Anil May 8 '17 at 12:51
• No probs! For a new user, you have done extremely well in formatting! Keep it up! – Toby Mak May 8 '17 at 12:52
• 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. – SaeidAli May 8 '17 at 12:57
• 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. – Bill Dubuque May 9 '17 at 23:03

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.