username3599094
Badges: 10
Rep:
?
#1
Report Thread starter 1 year ago
#1
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)
0
reply
username3599094
Badges: 10
Rep:
?
#2
Report Thread starter 1 year ago
#2
I have to prove it using the three rules.

I've done the first rule.
It's the second rule I'm stuck on.
0
reply
RDKGames
Badges: 20
Rep:
?
#3
Report 1 year ago
#3
(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.
0
reply
username3599094
Badges: 10
Rep:
?
#4
Report Thread starter 1 year ago
#4
(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
0
reply
username3599094
Badges: 10
Rep:
?
#5
Report Thread starter 1 year ago
#5
It's something to do with Bezout's identity
0
reply
username3599094
Badges: 10
Rep:
?
#6
Report Thread starter 1 year ago
#6
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.
0
reply
RDKGames
Badges: 20
Rep:
?
#7
Report 1 year ago
#7
(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)t... so what does Bezout's say about this? How are md, am, and bm related?
Last edited by RDKGames; 1 year ago
0
reply
username3599094
Badges: 10
Rep:
?
#8
Report Thread starter 1 year ago
#8
(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)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
0
reply
RDKGames
Badges: 20
Rep:
?
#9
Report 1 year ago
#9
(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 e|ma and e|mb then e \leq md.

If e|ma then ma = eK_1.
If also e|mb then mb = eK_2.

d = \gcd(a,b) = \gcd \left(\dfrac{eK_1}{m}, \dfrac{eK_2}{m} \right) \geq \dfrac{e}{m}.... hence the result follows.
0
reply
username3599094
Badges: 10
Rep:
?
#10
Report Thread starter 1 year ago
#10
How do i show that rule 3 is satisfied?
0
reply
RDKGames
Badges: 20
Rep:
?
#11
Report 1 year ago
#11
(Original post by Adil2400)
How do i show that rule 3 is satisfied?
You're given that m \geq 0 and by defining d = \gcd(a,b) you know that d\geq 0 ...
0
reply
username3599094
Badges: 10
Rep:
?
#12
Report Thread starter 1 year ago
#12
(Original post by RDKGames)
You're given that m \geq 0 and by defining d = \gcd(a,b) you know that d\geq 0 ...
Is it as simple as multiplying m by d?
0
reply
RDKGames
Badges: 20
Rep:
?
#13
Report 1 year ago
#13
(Original post by Adil2400)
Is it as simple as multiplying m by d?
Yep..
0
reply
X

Quick Reply

Attached files
Write a reply...
Reply
new posts
Back
to top
Latest
My Feed

See more of what you like on
The Student Room

You can personalise what you see on TSR. Tell us a little about yourself to get started.

Personalise

Have you experienced financial difficulties as a student due to Covid-19?

Yes, I have really struggled financially (53)
17.21%
I have experienced some financial difficulties (88)
28.57%
I haven't experienced any financial difficulties and things have stayed the same (117)
37.99%
I have had better financial opportunities as a result of the pandemic (40)
12.99%
I've had another experience (let us know in the thread!) (10)
3.25%

Watched Threads

View All
Latest
My Feed