# How to prove or disprove that $\gcd(ab, c) = \gcd(a, b) \times \gcd(b, c)$?

I'm new to proofs, and am trying to solve this problem from William J. Gilbert's "An Introduction To Mathematical Thinking: Algebra and Number Systems". Specifically, this is from Problem Set 2 Question 74. It asks:

How to prove or disprove that $\gcd(ab, c) = \gcd(a, b) \times \gcd(b, c)$?

What I've tried is to use the proposition that $\gcd(a, b) = ax + by$ to rewrite the whole equality, but I can't manage to equate the two statements.

Any help would be appreciated.

• Have you tried numerical examples? You should do so to either get a counter example, or on the contrary, convince yourself that the statement might be true. – Olivier Bégassat Dec 8 '13 at 4:49
• Let $a=b=c=2$... – Macavity Dec 8 '13 at 4:50
• Consider $a=b=6, c=12$ – abiessu Dec 8 '13 at 4:52
• ...or $a = b = 1928475618028127336$, $c=1$... – Josh Chen Dec 8 '13 at 4:54
• It is, isn't it? – Josh Chen Dec 8 '13 at 5:29

Notice if $a = b = c = 3$, then

$$\gcd(ab,c) = \gcd(9,3) = 3$$

while

$$gcd(a,b) \times gcd(b,c) = gcd(3,3) \times gcd(3,3) = 3 \times 3 = 9$$

$$\therefore gcd(ab,c) \neq gcd(a,b)\times gcd(b,c)$$

Let the highest powers of prime $p$ in $a,b,c$ be $A,B, C$ respectively.

So, the highest power of $p$ that divides $(ab,c)$ is min $(A+B,C),$

the highest power of $p$ that divides $(a,b)$ is min $(A,B)$

and the highest power of $p$ that divides $(b,c)$ is min $(B,C)$

$\implies$ the highest power of $p$ that divides $(a,b)\cdot(b,c)$ is min $(A,B)+$ min$(B,C)$

Now if $C\le B\le A+B,$ min $(A+B,C)=C$

We need min $(A,B)+C=C$ which is false unless min $(A,B)=0\implies A=B=0$ for any prime that divides $C$

• this is overly complicated, and most likely will confuse the asker. Dont you think so? – ILoveMath Dec 8 '13 at 4:55
• @DonAnselmo, What I've derived is from the definition of GCD. Also, it generalizes the solution – lab bhattacharjee Dec 8 '13 at 4:57
• Shouldn't all your $\max$'s be $\min$'s? – Josh Chen Dec 8 '13 at 5:10
• @JoshChen, thanks for your observation. Can you please verify the edited answer? – lab bhattacharjee Dec 8 '13 at 5:13

just a few remarks:

note: i use the standard abbreviation $(a,b)$ for the GCD of $a$ and $b$

a. it is possible to approach a problem in the wrong way. occasionally this may lead to startling insight, but usually it leads to a waste of time, and can even be demotivating. here, OP's introduction of:

$$(a,b) = ax+by$$ suggests that someone should explain why this property is unlikely to be helpful in the present case, or, alternatively, find a proof which is based on this approach.

b. sometimes an assertion smells fishy - an intuition which can be wrong, but is often correct. it directs us to look for a counterexample. finding counterexamples is a highly useful ability, which some have more of than others. psychologically, the heuristics of finding counter-examples are different from those of finding a proof of a result, and different again from those of making a discovery.

c. the assertion in this problem smells fishy, and it might be more interesting if, say, the question had been a request to evaluate: $$\frac{(a,c)(b,c)}{(ab,c)}$$ d. sometimes the sense of pain or aversion one feels on examining a problem (if you introspect the workings of the mind, which is inherently lazy, at least in my case) can actually serve as a guide to how the problem should be approached. i think the sense of "Oh, no!" i feel when i see the terms GCD or LCM is due to the fact that i like working with fields, rings, ideals and so on, but feel uncomfortable with boolean algebra. questions to do with division arise in an algebraic context of the ideals of $\mathbb{Z}$, but are often really about lattice properties.

e. so, given my mental unease, and OP's evident lack of experience, perhaps the following approach may generate some insight. i will assume the prime decomposition properties of $\mathbb{Z}$. if anyone objects i suggest they prove the necessary assertions as a lemma, and then continue as here.

let $\mathbb{P}$ be the set of prime numbers, and let $\mathbb{N}^+$ denote the set of positive integers. we define the map: $$\psi :\mathbb{P} \rightarrow \mathbb{N}^{\mathbb{N}^+}$$ we use the abbreviation $\mathfrak{p}_n$ for the more unwieldy $\psi(\mathfrak{p})(n)$. intuitively $\mathfrak{p}_n$ is the exponent of the highest power of $\mathfrak{p}$ which divides $n$.

LEMMA we use the symbol $m \land n$ for min$(m,n)$

for any $\mathfrak{p} \in \mathbb{P}$ $$\mathfrak{p}_{(a,b)} = \mathfrak{p}_a \land \mathfrak{p}_b$$ and $$\mathfrak{p}_{ab} = \mathfrak{p}_a + \mathfrak{p}_b$$ the claim in the question can now be expressed as a spurious assertion of distributivity, but which can be improved to: $$\\$$ THEOREM

$\forall \mathfrak{p} \in \mathbb{P}$, and $a,b,c \in \mathbb{N}^+$ we have: $$(\mathfrak{p}_a+\mathfrak{p}_b) \land \mathfrak{p}_c \le \mathfrak{p}_a \land \mathfrak{p}_c + \mathfrak{p}_a \land \mathfrak{p}_c$$ perhaps someone can produce an aesthetically satisfying demonstration?