Need help to prove this

Watch this thread
username3599094
Badges: 10
Rep:
? You'll earn badges for being active around the site. Rep gems come when your posts are rated by other community members.
#1
Report Thread starter 2 years 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:
? You'll earn badges for being active around the site. Rep gems come when your posts are rated by other community members.
#2
Report Thread starter 2 years 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:
? You'll earn badges for being active around the site. Rep gems come when your posts are rated by other community members.
#3
Report 2 years 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:
? You'll earn badges for being active around the site. Rep gems come when your posts are rated by other community members.
#4
Report Thread starter 2 years 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:
? You'll earn badges for being active around the site. Rep gems come when your posts are rated by other community members.
#5
Report Thread starter 2 years ago
#5
It's something to do with Bezout's identity
0
reply
username3599094
Badges: 10
Rep:
? You'll earn badges for being active around the site. Rep gems come when your posts are rated by other community members.
#6
Report Thread starter 2 years 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:
? You'll earn badges for being active around the site. Rep gems come when your posts are rated by other community members.
#7
Report 2 years 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; 2 years ago
0
reply
username3599094
Badges: 10
Rep:
? You'll earn badges for being active around the site. Rep gems come when your posts are rated by other community members.
#8
Report Thread starter 2 years 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:
? You'll earn badges for being active around the site. Rep gems come when your posts are rated by other community members.
#9
Report 2 years 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:
? You'll earn badges for being active around the site. Rep gems come when your posts are rated by other community members.
#10
Report Thread starter 2 years ago
#10
How do i show that rule 3 is satisfied?
0
reply
RDKGames
Badges: 20
Rep:
? You'll earn badges for being active around the site. Rep gems come when your posts are rated by other community members.
#11
Report 2 years 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:
? You'll earn badges for being active around the site. Rep gems come when your posts are rated by other community members.
#12
Report Thread starter 2 years 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:
? You'll earn badges for being active around the site. Rep gems come when your posts are rated by other community members.
#13
Report 2 years 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

Do you know what you'll do if you don't get the grades you're hoping for?

Find something else in clearing (30)
28.85%
Take a gap year (16)
15.38%
Resit my exams (28)
26.92%
Look for alternate pathways to the career I want (15)
14.42%
I don't know yet (10)
9.62%
Something else (tell us in the thread) (5)
4.81%

Watched Threads

View All