Finding Solutions for LCM and GCD Equations in Number Theory

[mtayab1994]

Homework Statement

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

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.

 

[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??

 

[mtayab1994]

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??

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

 

[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?

 

[mtayab1994]

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?

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 :(.

 

[micromass]

Here, you're given

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

What are the possibilities for x and y??

 

[mtayab1994]

Here, you're given

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

What are the possibilities for x and y??

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

 

[micromass]

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

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?

 

[Mark44]

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

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

 

[mtayab1994]

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?

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

 

[micromass]

(14,10) , (4,20) , (8,16) and the inverse of them.

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

 

[mtayab1994]

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

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

I had made an edit in the post before.

 

[micromass]

Yes, there is no solution.

 

[mtayab1994]

Yes, there is no solution.

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 .

 

[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).