5
$\begingroup$

Let $a, b, c$ be integers. Prove that if $\gcd(a,b)=1$ then $\gcd(ab,c) = \gcd(a,c) \gcd(b,c)$

First time asking here. I'm not sure what your policies are on general homework help but I truly am stuck.

So far I have shown $\gcd(a,c) \gcd(b,c)$ as an integer combination of $ab$ and $c$. So if I can show that $\gcd(a,c) \gcd(b,c)$ divides $ab$ and $c$ I can use the proof that if an integer $d$ is a common divisor of $a$ and $b$, and $d=ax+by$ for some $x$ and $y$, that $d=\gcd(a,b)$. However I don't really know where to start with this. Any help would be appreciated.

$\endgroup$
6
  • 2
    $\begingroup$ Welcome to Math.SE! Homework questions are definitely acceptable (and common) here, and you presented yours in the way we like (i.e., showing what you've done so far, where you're having trouble, etc.). You'll usually get answers in the form of hints (like the one I'm writing) for homework questions instead of explicit solutions. $\endgroup$ – Dan Oct 22 '13 at 21:21
  • $\begingroup$ Do you know the fundamental theorem of arithmetic yet? $\endgroup$ – davidlowryduda♦ Oct 22 '13 at 21:22
  • 1
    $\begingroup$ Someone is flagging my comment, and I don't know why. But I'll expand: in number theory classes, you start by understanding divisibility and gcd rules, and use these to prove the fundamental theorem of arithmetic (unique factorization). But this question is independent of unique factorization, and can be proved with or without it. I din't know which proof to guide the OP towards without knowing whether or not he or she knows the fundamental theorem of arithmetic. $\endgroup$ – davidlowryduda♦ Oct 22 '13 at 21:27
  • 1
    $\begingroup$ Nope. I'd prefer a simpler solution versus something requiring advanced knowledge, plus I doubt they'd accept a solution like that anyway. $\endgroup$ – Anonymous Oct 22 '13 at 21:28
  • $\begingroup$ math.stackexchange.com/questions/535961/… $\endgroup$ – njguliyev Oct 22 '13 at 21:42
2
$\begingroup$

I'm going to write $(m,n)$ for $\text{gcd}(m,n)$ throughout what follows.

You want to show that $(a,c)(b,c) \mid ab, c$. From the definition of $(m,n)$, it's easy to show that $(a,c)(b,c) \mid ab$ (since $(a,c) \mid a$ and $(b,c) \mid b$). So it really boils down to showing that $(a,c)(b,c) \mid c$.

Since $(a,c), (b,c) \mid c$, you can write $c = r(a,c) = s(b,c)$ for some integers $r$ and $s$. Therefore, to show that $(a,c)(b,c) \mid c$, it's enough to show that $(b,c) \mid r = c/(a,c)$. This is equivalent to showing that $p \nmid (a,c)$ for any prime number dividing $(b,c)$. This follows from $a$ and $b$ being coprime. (Why?)

$\endgroup$
0
$\begingroup$

Imagine the prime factorization of $a$ and the prime factorization of $b$. The primes in $a$ are all different from those in $b$ (because $a$ and $b$ are coprime).

Think about what GCD does. It cherry-picks the common primes of the inputs and multiplies them together. If $a$ and $b$ contain entirely different primes from one another, then separating the GCD into the two GCD's has no effect.

Try to formulate a proof from this.
Good luck

$\endgroup$
2
  • $\begingroup$ This is exactly what the OP said he didn't want in response to my comment above $\endgroup$ – davidlowryduda♦ Oct 22 '13 at 21:35
  • $\begingroup$ Oh, I hadn't read your comment. I think the OP was intimidated by the need to go read other references when the idea is actually quite simple. This is not exactly "advanced knowledge" but the OP might have gotten that gist. $\endgroup$ – ndh Oct 22 '13 at 21:51

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.