# Using the Euclidean algorithm .I think

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?

Dick
Homework Helper

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?

Well, sure. Yes. Why not?

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?

Dick
Homework Helper

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?

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

epenguin
Homework Helper
Gold Member

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?

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

epenguin
Homework Helper
Gold Member

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?

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.