3
$\begingroup$

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

$\endgroup$
8
$\begingroup$

Even I can do this one!

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

$\endgroup$
1
  • 3
    $\begingroup$ Who'd believe it. I actually got an answer accepted. You can take your head out of the oven now Mother! $\endgroup$
    – gamma
    Aug 8 '13 at 22:32
2
$\begingroup$

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$

$\endgroup$
5
  • $\begingroup$ 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 $\endgroup$
    – Ergo
    Aug 8 '13 at 20:35
  • $\begingroup$ @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. $\endgroup$ Aug 8 '13 at 20:39
  • $\begingroup$ 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. $\endgroup$
    – Ergo
    Aug 8 '13 at 20:42
  • $\begingroup$ @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. $\endgroup$
    – dtldarek
    Aug 8 '13 at 20:53
  • $\begingroup$ Thanks for the explanation, helps clear it up cheers :) $\endgroup$
    – Ergo
    Aug 8 '13 at 21:01
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$

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.