- #1

- 35

- 0

## Homework Statement

Find all pairs of integers a, b such that their GCD and LCM are 14 and 168 respectively.

## Homework Equations

a x b = gcd(a,b) x lcm(a,b) (useful?)

## The Attempt at a Solution

confused...

- Thread starter bphysics
- Start date

- #1

- 35

- 0

Find all pairs of integers a, b such that their GCD and LCM are 14 and 168 respectively.

a x b = gcd(a,b) x lcm(a,b) (useful?)

confused...

- #2

Hurkyl

Staff Emeritus

Science Advisor

Gold Member

- 14,916

- 19

Maybe, maybe not. What does it tell you?a x b = gcd(a,b) x lcm(a,b) (useful?)

- #3

- 35

- 0

that i can use the gcd and lcm to get axb

so, a x b = 14 x 168

a x b = 2352...

so, a x b = 14 x 168

a x b = 2352...

- #4

Hurkyl

Staff Emeritus

Science Advisor

Gold Member

- 14,916

- 19

That looks correct. Is it useful?a x b = 2352...

- #5

- 35

- 0

- #6

Hurkyl

Staff Emeritus

Science Advisor

Gold Member

- 14,916

- 19

You don't know how to find all of the solutions to a x b = 2352?

- #7

- 35

- 0

- #8

Hurkyl

Staff Emeritus

Science Advisor

Gold Member

- 14,916

- 19

Ah. So you

This particular method could be streamlined a bit, because it's easy enough to limit yourself to writing down just those pairs with, for example,

- #9

- 35

- 0

wait a dividing lcm(a, b)?

can you explain more?

can you explain more?

- #10

Hurkyl

Staff Emeritus

Science Advisor

Gold Member

- 14,916

- 19

But in the end, I think that after optimization, both methods would lead to the same algorithm.

- #11

- 35

- 0

because i have trouble spotting them...

could you lead me though it?

could you lead me though it?

- #12

Hurkyl

Staff Emeritus

Science Advisor

Gold Member

- 14,916

- 19

Er, what is there to explain? You know how to find all the solutions to a x b = 2352, so now we're just imposing some of the information from the original problem to streamline our work.wait a dividing lcm(a, b)?

can you explain more?

I thought that's what I was doing....could you lead me though it?

- #13

- 35

- 0

Thanks. =D

- #14

- 35

- 0

so are the answers (14, 168) and (42, 56)?

- #15

Hurkyl

Staff Emeritus

Science Advisor

Gold Member

- 14,916

- 19

(1) There's no shame in having an inelegant solution!

If you have a line of thought that looks like it will work, then it's worth pursuing. I'm fairly good at solving hard problems, and one of the reasons is that if I see a path that I can make progress upon, then I go down that path, even if it appears long and tedious. Quite often, I can finish that long and tedious path in much less time than it would take to come up with the clever, "quick" proof.

And that said, once you take a path and have worked stuff out... you can learn from it and use that experience to continue attacking the problem.

(2) Divisibility is very, very important in number theory.

This is something you should take the time to understand thoroughly -- you should be able to answer questions like "find all numbers

- #16

Hurkyl

Staff Emeritus

Science Advisor

Gold Member

- 14,916

- 19

Hrm. I expected three answers. (But I could be wrong)so are the answers (14, 168) and (42, 56)?

- #17

- 35

- 0

... can't find the other one.... was looking at it and can't seem to come up with another pair....

- #18

- 35

- 0

- #19

- 35

- 0

- Last Post

- Replies
- 4

- Views
- 2K

- Last Post

- Replies
- 1

- Views
- 1K

- Last Post

- Replies
- 9

- Views
- 2K

- Last Post

- Replies
- 0

- Views
- 2K

- Last Post

- Replies
- 6

- Views
- 2K

- Last Post

- Replies
- 1

- Views
- 1K

- Replies
- 1

- Views
- 2K

- Replies
- 3

- Views
- 1K

- Last Post

- Replies
- 4

- Views
- 928

- Last Post

- Replies
- 9

- Views
- 13K