# Homework Help: Number theory (LCM , GCD)

1. May 7, 2012

### mtayab1994

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

Solve in N^2 the following system of equations:

1- gcd(x,y)=7 and Lcm(x,y)=91

2- x+y=24 and Lcm =40

3. The attempt at a solution

Let d=gcd(x,y)

I said there exists an α and β so that x=dα and y=dβ and gcd(α,β)=1

And after doing some work i reached that α divides αβ=13 so that gives only two solutions that satisfy gcd(α,β)=1 and they are α=1 and β=13 and vise versa. So I got S={(7,91);(91,7)}. Can someone help me with the second one. Thank you.

Last edited: May 7, 2012
2. May 7, 2012

### micromass

If you know the prime factorization of x and y, then what can you say about the prime factorization of lcm(x,y)?? Does this have an easy form??

3. May 7, 2012

### mtayab1994

I know that lmc(x,y)=40 ⇔ x divides 40 and y divides 40 , but I don't know what to do from there.

4. May 7, 2012

### micromass

OK, I'll do some examples. See if you can spot the pattern:

If x=3, y=5, then lcm(x,y)=3*5
If x=3, y=2*5, then lcm(x,y)=2*3*5
If x=3², y=5, then lcm(x,y)=3²*5
If x=3², y=3³*5, then lcm(x,y)=3³*5
If x=3³*2², y=3²*5, then lcm(x,y)=2²*3³*5

Can you see an easy way to find the prime factorization of lcm(x,y), given the prime factorization of x and y?

5. May 7, 2012

### mtayab1994

Yes i can but i don't know how to use that with my situation, and I really need to finish this because I still have a lot more stuff to do :(.

6. May 7, 2012

### micromass

Here, you're given

$$lcm(x,y)=2^3*5$$

What are the possibilities for x and y??

7. May 7, 2012

### mtayab1994

Possibilities of x and y could be: (1,40) (5,2^3) and (2^2,10) and the inverse of them too.

8. May 7, 2012

### micromass

The last one is not correct as it would have an lcm of 2^2*5, and you're missing things like (8,10) and (8,40), etc. . But your idea is right: x and y can only be divisible by 2 and 5. Furthermore, at least one of x and y has to be divisible by 8.

Now, which numbers x and y such that x+y=24 are only divisible by 2 and 5?

9. May 7, 2012

### Staff: Mentor

There are quite a few pairs of numbers that you missed.

10. May 7, 2012

### mtayab1994

(14,10) , (4,20) , (8,16) and the inverse of them, but I don't think this system has a solution. Am I correct?

11. May 7, 2012

### micromass

And which ones satisfy lcm(x,y)=40?

12. May 7, 2012

### mtayab1994

Well none of them do. Aren't I correct?

I had made an edit in the post before.

13. May 7, 2012

### micromass

Yes, there is no solution.

14. May 7, 2012

### mtayab1994

Ok thank you and is there a better way of writing it out. Also I have a different problem that I'm I'm having difficulties with, so i'll post that as well .

15. May 7, 2012

### Joffan

I tihnk the simplest way is to focus on the fact that 40 is divisible by the prime number 5, therefore (at least) one of x and y is also divisible by 5. Taking x as divisible by 5, there are only four possible values (in $\mathbb{N}$) less than 24 for x, and the resulting (x,y) pairs satisfying x+y=24 can be considered in turn and rejected. (Actually there are only three x values consistent with lcm(x,y) = 40, as 15 does not divide 40).

Last edited: May 7, 2012
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook