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

1 Answer 1

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .