• Support PF! Buy your school textbooks, materials and every day products Here!

Using the Euclidean algorithm .I think

  • Thread starter trap101
  • Start date
  • #1
342
0
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?
 

Answers and Replies

  • #2
Dick
Science Advisor
Homework Helper
26,258
618


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?
 
  • #3
342
0


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
Dick
Science Advisor
Homework Helper
26,258
618


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.
 
  • #5
epenguin
Homework Helper
Gold Member
3,724
765


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:
 
  • #6
epenguin
Homework Helper
Gold Member
3,724
765


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.
 

Related Threads on Using the Euclidean algorithm .I think

  • Last Post
Replies
4
Views
2K
  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
6
Views
333
  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
5
Views
1K
  • Last Post
Replies
6
Views
1K
  • Last Post
Replies
0
Views
2K
Replies
0
Views
3K
Replies
10
Views
1K
Replies
8
Views
2K
Top