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.

  • $\begingroup$ 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. $\endgroup$ Dec 8, 2013 at 4:49
  • 2
    $\begingroup$ Let $a=b=c=2$... $\endgroup$
    – Macavity
    Dec 8, 2013 at 4:50
  • $\begingroup$ Consider $a=b=6, c=12$ $\endgroup$
    – abiessu
    Dec 8, 2013 at 4:52
  • 2
    $\begingroup$ ...or $a = b = 1928475618028127336$, $c=1$... $\endgroup$
    – Josh Chen
    Dec 8, 2013 at 4:54
  • $\begingroup$ It is, isn't it? $\endgroup$
    – Josh Chen
    Dec 8, 2013 at 5:29

3 Answers 3


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

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


$$ 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$

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


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.