Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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.
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$
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?
