# Number theory (LCM , GCD)

## 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.

Last edited:

## Answers and Replies

Related Calculus and Beyond Homework Help News on Phys.org
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??

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.

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?

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

Here, you're given

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

What are the possibilities for x and y??

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.

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
Mentor
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.

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?

(14,10) , (4,20) , (8,16) and the inverse of them.
And which ones satisfy lcm(x,y)=40?

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.

Yes, there is no solution.

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 .

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: