Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
2  
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
2  
...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

3 Answers 3

up vote 2 down vote accepted

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

share|improve this answer

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$

share|improve this answer
    
this is overly complicated, and most likely will confuse the asker. Dont you think so? –  Marvin Gaye 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?

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.