Using the Euclidean algorithm .I think

1. Feb 26, 2013

trap101

Using the Euclidean algorithm.....I think...

find the smallest natural number x such that 24x leaves a remainder of 2 upon division by 59

SO it seems to me that the way to approach this would be through the euclidean algorithm and a diophantine equation. Thinking about it for a moment would I perhaps set it up like this?

24x + 59y = 2

then proceed with the process?

2. Feb 26, 2013

Dick

Re: Using the Euclidean algorithm.....I think...

Well, sure. Yes. Why not?

3. Feb 26, 2013

trap101

Re: Using the Euclidean algorithm.....I think...

Thanks again, I can't even count the amount of times you've helped me in the last few days. I have one final question. It had to do with diophantines with 3 variables:

2x + 3y + 7z = 32

I read a long winded solution somewhere that involved guessing a value for one of the variables and then figuring them out for all the cases. Is there a more compact way of doing along the lines of 2 variables?

4. Feb 26, 2013

Dick

Re: Using the Euclidean algorithm.....I think...

Not that I know of. That sounds like the way to do it.

5. Feb 26, 2013

epenguin

Re: Using the Euclidean algorithm.....I think...

Shouldn't that be MINUS 59y ?:shy:

6. Feb 26, 2013

epenguin

Re: Using the Euclidean algorithm.....I think...

Maybe you can cut down the examples needing examination. Is it the case that y, z have to be both odd or both even? And probably it would be more efficient to examine different values of the number with the largest coefficient, z, first? Other shortcuts may suggest themselves as you proceed.

Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted