Prove that if $gcd(a, b) = c$ then $c^2|ab$.

Question

I recently just started this topic in class and have been going over some examples without much success. I understand the concept behind if a|b and b|c then a|c but when it comes to more complex ones, I become a tad confused..

*Thanks for the help everyone!!

score 8 · Accepted Answer · edited Aug 08 '13 at 21:33

8

Even I can do this one!

If $\gcd(a,b) = c$ then $c | a$ and $c | b$, so $c$ squared divides $ab$.

edited Aug 08 '13 at 21:33

Jeel Shah

9,306

answered Aug 08 '13 at 20:25

gamma

1,957

3

Who'd believe it. I actually got an answer accepted. You can take your head out of the oven now Mother! – gamma Aug 08 '13 at 22:32

score 2 · Answer 2 · answered Aug 08 '13 at 20:27

2

Hint:

If $\frac{a}{x} \in \mathbb{N}$ and $\frac{b}{x} \in \mathbb{N}$ then then $\frac{ab}{xy} = \frac{a}{x}\cdot\frac{b}{y} \in \mathbb{N}$.

I hope this helps $\ddot\smile$

answered Aug 08 '13 at 20:27

dtldarek

37,381

I think I might be on the right tracks.. if gcd(a, b) = c, then c|a and c|b. c|a * c|b = (cc)|(ab) = c^2|ab – Ergo Aug 08 '13 at 20:35
@Androx, I'm afraid what you've written doesn't make much sense. I think it well help if you try to stay close to the definitions and perhaps read some of the posts here again. I'm sure all who posted here will be happy to give clarification if you are confused. – Alex Wertheim Aug 08 '13 at 20:39
Yeah, my answer isn't formatted correctly but I believe the principle behind achieving the correct answer is there, is it not? It can be seen that c|a and c|b so I multiply both together and end up with c²|ab. – Ergo Aug 08 '13 at 20:42
@Androx $c \mid a$ is not $\frac{c}{a}$ The first is a relation, the second is a fraction. Multiplying relations (in this context) makes no sense. – dtldarek Aug 08 '13 at 20:53
Thanks for the explanation, helps clear it up cheers :) – Ergo Aug 08 '13 at 21:01

score 1 · Answer 3 · answered Aug 08 '13 at 20:24

Hint:

If $\gcd(a, b) = c$, then $c|a$ and $c|b$. Hence, $a = k_{1}c$ for some $k_{1} \in \mathbb{Z}$ and $b = k_{2}c$ for some $k_{2} \in \mathbb{Z}$.

Can you take it from here? (Try writing $ab$ as some multiple of $c^{2}$ given the information you have!)

score 1 · Answer 4 · answered Aug 08 '13 at 20:25

1

Hint: write down with words what the definition of gcd is. Then make sure you understand it. Then you will see that $gcd(a,b)=c \Rightarrow c^2|ab$ follows immediately from the definition.

answered Aug 08 '13 at 20:25

Manos

25,833

score 1 · Answer 5 · answered Aug 08 '13 at 20:32

Easy! The key is to realize that if $\gcd(a, b) = c$, then we have both $c \vert a$ and $c \vert b$; greatest common divisor is, after all, a divisor. Thus there exist integers $k_1$, $k_2$ such that $a = k_1c$ and $b = k_2c$; then $ab = k_1k_2c^2$, showing that in fact $c^2 \vert ab$. Nice one! Cheers and QED, Bob Lewis

Prove that if $gcd(a, b) = c$ then $c^2|ab$.

5 Answers5