# Ring theory?

1. Jan 20, 2013

### Zondrina

1. The problem statement, all variables and given/known data

Didn't know what to title this one. I found it while I was doing some practice problems :

http://gyazo.com/51a668d4db1a1638353a9de4b43d42ed

2. Relevant equations

lcm(m,n) = k for some integer k.

3. The attempt at a solution

I'm not really sure how to start this one. My guess is I want to argue with double inclusion? As in argue they're both subsets of each other.

Any help would be great.

2. Jan 20, 2013

### haruspex

Obvious approach is to let x be a member of the set on the LHS and show it is therefore in kZ; then show the converse (which is trivial).

3. Jan 20, 2013

### Zondrina

Hmm okay. So :

We want to show for some positive integers, m and n, that $m \mathbb{Z} \cap n \mathbb{Z} = k \mathbb{Z}$ for some integer $k \in \mathbb{Z} \space | \space lcm(m,n) = k$

Case : mZ$\cap$nZ $\subseteq$ kZ

Choose any a$\in$mZ$\cap$nZ. We want to show a$\in$kZ.

Observe that a is also a positive integer because mZ$\cap$nZ is the set of all positive integers such that a$\in$mZ and a$\in$nZ.

Hence a = mx and a = ny for some integers x and y. So that a is an integer multiple of m and n.

Is this on the right track? I'm getting a bit stuck.

Stuff I didn't quite know if it mattered :

---Now, since lcm(m,n) = k, we know that k is also a positive integer so that kZ is a set of positive integers---

Last edited: Jan 20, 2013
4. Jan 20, 2013

### Dick

Ok, you've shown a is a common multiple of m and n. Can you show ANY common multiple of m and n is a multiple of the least common multiple?

5. Jan 20, 2013

### Zondrina

Hmmm, I think I see what you're getting at here.

Since lcm(m,n) = k, then lcm(m,n)a = ka for any positive integer a ( Any integer really ). I wouldn't understand what you mean by 'show' though.

6. Jan 20, 2013

### Dick

There is some content here. You need to show that if a is any common multiple of n and m then it is an integer multiple of lcm(n,m). Think about what the lcm means in terms of prime factorization. See http://en.wikipedia.org/wiki/Least_common_multiple

7. Jan 20, 2013

### Zondrina

We need to show that if a is any common multiple of m and n, then it is an integer multiple of lcm(m,n) = k.

That is, we must show a = kr for some integer r.

Since m|k and n|k, we have k = mq and k = np for integers q and p.

Is this on the right track?

8. Jan 20, 2013

### Dick

You haven't made any false statements. But you need to use another property of the integers to prove it. Like the division algorithm or prime factorization. Did you look at the reference I gave you and think about it?

9. Jan 21, 2013

### Zondrina

Yeah I read a bit of the page. I didn't really see how the prime factorization would be appropriate here when I could apply the D.A. I thought of a slightly better way to go about this I think.

We need to show that if a is any common multiple of m and n ( which means it is also an multiple of m and n which I showed ), then it is an integer multiple of lcm(m,n) = k.

That is, we must show a = kq for some integer q.

So we divide a by k so that by the DA we write a = kq + r, 0 ≤ r < k.

Since m|a, n|a, m|k and n|k, they also divide r = a − kq. So, r is a common multiple of m and n. But k is the least positive common multiple of m and n.

So, we would have a contradiction unless r = 0. So, we must have r = 0 and k|a so that a = kq as contended.

Last edited: Jan 21, 2013
10. Jan 21, 2013

### Dick

Sure, that works.

11. Jan 21, 2013

### Zondrina

Some things I said were wrong in that post, so I edited it a bit. Like I got mixed up with a bunch of the letters, but hopefully that's right now. So i'll combine the work done in the posts so far into this one.

We want to show for some positive integers, m and n, that $m \mathbb{Z} \cap n \mathbb{Z} = k \mathbb{Z}$ for some integer $k \in \mathbb{Z} \space | \space lcm(m,n) = k$

Case : mZ$\cap$nZ $\subseteq$ kZ

Choose any a$\in$mZ$\cap$nZ. We want to show a$\in$kZ.

Observe that a is also a positive integer because mZ$\cap$nZ is the set of all positive integers such that a$\in$mZ and a$\in$nZ.

Hence a = mx and a = ny for some integers x and y. So that a is an integer multiple of m and n.

We need to show that if a is any common multiple of m and n ( which means it is also an multiple of m and n which I showed ), then it is an integer multiple of lcm(m,n) = k.

That is, we must show a = kq for some integer q.

So we divide a by k so that by the DA we write a = kq + r, 0 ≤ r < k.

Since m|a, n|a, m|k and n|k, they also divide r = a − kq. So, r is a common multiple of m and n. But k is the least positive common multiple of m and n.

So, we would have a contradiction unless r = 0. So, we must have r = 0 and k|a so that a = kq as contended.

Okay, so I've shown that a is both a integer multiple of m and n and also k. Since kZ is the set of all integer multiples of k, then it must be that a$\in$kZ as desired which implies that mZ$\cap$nZ $\subseteq$ kZ.

Lookin good so far?

12. Jan 21, 2013

### Dick

It looks good to me.

13. Jan 21, 2013

### Zondrina

Sweet, gotta love the mornings. So now for the other way.

Case : mZ$\cap$nZ $\supseteq$ kZ

I know there must be a trivial way to show this which doesn't require as much work as before. I believe this has something to do with the lcm(m,n) = k.

Hmm... Since lcm(m,n) = k, we know every member of kZ is an integer multiple of both m and n. Hence every element of kZ is also in mZ$\cap$nZ.

Is it really that straightforward?

Last edited: Jan 21, 2013
14. Jan 21, 2013

### Dick

Yes it is. That is the easy direction.

15. Jan 21, 2013

### Zondrina

Sweet. QED then I suppose.

Thanks for giving me the right pointers and confirming my work as usual :) I would probably be lost otherwise.

Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook