Number theory (LCM , GCD)

  • Thread starter mtayab1994
  • Start date
  • #1
584
0

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

  • #2
22,097
3,283
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
584
0
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.
 
  • #4
22,097
3,283
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
584
0
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 :(.
 
  • #6
22,097
3,283
Here, you're given

[tex]lcm(x,y)=2^3*5[/tex]

What are the possibilities for x and y??
 
  • #7
584
0
Here, you're given

[tex]lcm(x,y)=2^3*5[/tex]

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.
 
  • #8
22,097
3,283
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?
 
  • #9
33,741
5,432
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.
 
  • #10
584
0
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?
 
  • #11
22,097
3,283
(14,10) , (4,20) , (8,16) and the inverse of them.
And which ones satisfy lcm(x,y)=40?
 
  • #12
584
0
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.
 
  • #13
22,097
3,283
Yes, there is no solution.
 
  • #14
584
0
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 .
 
  • #15
473
13
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:

Related Threads on Number theory (LCM , GCD)

  • Last Post
Replies
4
Views
40K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
4
Views
3K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
2
Views
436
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
2
Views
3K
  • Last Post
Replies
21
Views
3K
  • Last Post
Replies
3
Views
1K
  • Last Post
Replies
1
Views
409
Top