1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Using the Euclidean algorithm .I think

  1. Feb 26, 2013 #1
    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. jcsd
  3. Feb 26, 2013 #2

    Dick

    User Avatar
    Science Advisor
    Homework Helper

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

    Well, sure. Yes. Why not?
     
  4. Feb 26, 2013 #3
    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?
     
  5. Feb 26, 2013 #4

    Dick

    User Avatar
    Science Advisor
    Homework Helper

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

    Not that I know of. That sounds like the way to do it.
     
  6. Feb 26, 2013 #5

    epenguin

    User Avatar
    Homework Helper
    Gold Member

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

    Shouldn't that be MINUS 59y ?:shy:
     
  7. Feb 26, 2013 #6

    epenguin

    User Avatar
    Homework Helper
    Gold Member

    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



Similar Discussions: Using the Euclidean algorithm .I think
  1. Euclidean algorithm (Replies: 4)

  2. Euclidean algorithm (Replies: 3)

Loading...