The Student Room Group

Need help to prove this

Let a,b be non zero integers and let m be an integer with m greater than or equal to 0.
Prove that gcd(am,bm)=m*gcd(a,b)
I have to prove it using the three rules.

I've done the first rule.
It's the second rule I'm stuck on.
Original post by Adil2400
I have to prove it using the three rules.

I've done the first rule.
It's the second rule I'm stuck on.


What three rules? If you tell us then we can guide you along the solution you're expected to follow.
Original post by RDKGames
What three rules? If you tell us then we can guide you along the solution you're expected to follow.

gcd(a,b)=d if

1) d divides a and d divides b

2)if e divides a and e divides b, then e is less than or equal to d

3)d is greater than or equal to 0
It's something to do with Bezout's identity
d=gcd(a,b)=as+bt

So md=m(as+bt)=am(s)+bm(t)

This is what I've done so far. Don't know what to do from here.
Original post by Adil2400
d=gcd(a,b)=as+bt

So md=m(as+bt)=am(s)+bm(t)

This is what I've done so far. Don't know what to do from here.



You can just apply Bezout's once more. You know that there exist integers s,t such that md=(am)s+(bm)tmd = (am)s + (bm)t... so what does Bezout's say about this? How are md, am, and bm related?
(edited 4 years ago)
Original post by RDKGames
You can just apply Bezout's once more. You know that there exist integers s,t such that md=(am)s+(bm)tmd = (am)s + (bm)t... so what does Bezout's say about this? How are md, am, and bm related?

That means that gcd(am,bm)=md but that still doesn't show that rule 2 is satisfied
Original post by Adil2400
That means that gcd(am,bm)=md but that still doesn't show that rule 2 is satisfied


It's satisfied. Think about it. You want to show that if emae|ma and embe|mb then emde \leq md.

If emae|ma then ma=eK1ma = eK_1.
If also embe|mb then mb=eK2mb = eK_2.

d=gcd(a,b)=gcd(eK1m,eK2m)emd = \gcd(a,b) = \gcd \left(\dfrac{eK_1}{m}, \dfrac{eK_2}{m} \right) \geq \dfrac{e}{m}.... hence the result follows.
How do i show that rule 3 is satisfied?
Original post by Adil2400
How do i show that rule 3 is satisfied?


You're given that m0m \geq 0 and by defining d=gcd(a,b)d = \gcd(a,b) you know that d0d\geq 0 ...
Original post by RDKGames
You're given that m0m \geq 0 and by defining d=gcd(a,b)d = \gcd(a,b) you know that d0d\geq 0 ...

Is it as simple as multiplying m by d?
Original post by Adil2400
Is it as simple as multiplying m by d?


Yep..

Quick Reply