1
$\begingroup$

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.

$\endgroup$
  • $\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 '17 at 12:46
  • $\begingroup$ thank you. I am completely new to mathjax $\endgroup$ – Anil May 8 '17 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 '17 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 '17 at 12:57
  • $\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$ – Bill Dubuque May 9 '17 at 23:03
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Okay I got your point, but this isn't the whole proof is it? $\endgroup$ – Anil May 8 '17 at 13:20
  • $\begingroup$ @Anil This is just the conclusion, the first part of your proof is correct. $\endgroup$ – Paolo Leonetti May 8 '17 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.