Number theory GCD relatively prime question

  • #1
784
11

Homework Statement


let m|d, n|d and gcd(m,n) = 1. show mn|d

Homework Equations


gcd(m,n) = d = mx + ny for x and y in integers

The Attempt at a Solution


d = mr
d = ns
1 = mx + ny
1 = (d/r)x + (d/s)y
I don't know, a bit lost, just moving stuff around and not making any real progress. Any tips?
 

Answers and Replies

  • #2
Dick
Science Advisor
Homework Helper
26,258
619

Homework Statement


let m|d, n|d and gcd(m,n) = 1. show mn|d

Homework Equations


gcd(m,n) = d = mx + ny for x and y in integers

The Attempt at a Solution


d = mr
d = ns
1 = mx + ny
1 = (d/r)x + (d/s)y
I don't know, a bit lost, just moving stuff around and not making any real progress. Any tips?
Have you tried thinking about some of these problems in terms of the prime factorizations of m, n and d?
 
  • Like
Likes PsychonautQQ
  • #3
jbunniii
Science Advisor
Homework Helper
Insights Author
Gold Member
3,394
180
d = mr
d = ns
1 = mx + ny
So far so good. These three equations are all you need. Hint for the next step: try multiplying the last equation by ##d##.
 
  • Like
Likes PsychonautQQ
  • #4
784
11
Have you tried thinking about some of these problems in terms of the prime factorizations of m, n and d?
I have not tried thinking about this way. If n|d and m|d, we know that m and n each contain at least one prime that is also in the prime factorization of d. However, this does not mean we can conclude that mn|d does it? What if the only common prime in the factorization of m, n, and d is p, that would mean mn contains p^2 which wouldn't divide d's lone p.

Am I missing something?
 
  • #5
Dick
Science Advisor
Homework Helper
26,258
619
I have not tried thinking about this way. If n|d and m|d, we know that m and n each contain at least one prime that is also in the prime factorization of d. However, this does not mean we can conclude that mn|d does it? What if the only common prime in the factorization of m, n, and d is p, that would mean mn contains p^2 which wouldn't divide d's lone p.

Am I missing something?
The idea is that if gcd(m,n)=1 then m and n have no prime factor in common. Do you see how the proof would go from there? Proving it with jbunniii's hint is actually easier to write down. I just find it easier to think in terms of prime factors.
 
  • Like
Likes PsychonautQQ
  • #6
784
11
Yeah, I solved it with regards to jbunnii's hint, wish I would have seen it myself >.<. Right, gcd(m,n) = 1 so they each have a unique prime that divides d, so nm|d. Thanks man, I I appreciate ya'll being so patient with me.
 

Related Threads on Number theory GCD relatively prime question

  • Last Post
Replies
1
Views
345
  • Last Post
Replies
4
Views
497
  • Last Post
Replies
2
Views
436
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
15
Views
2K
  • Last Post
Replies
1
Views
972
  • Last Post
Replies
4
Views
3K
  • Last Post
Replies
14
Views
2K
  • Last Post
Replies
2
Views
3K
Replies
5
Views
1K
Top