1. Limited time only! Sign up for a free 30min personal 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!

Modulo reduction problem

  1. Feb 27, 2010 #1
    1. The problem statement, all variables and given/known data

    Reduce 34567 modulo 19.

    2. Relevant equations



    3. The attempt at a solution
    I approached by first reducing 4567 modulo 18.

    I got the following: 34567= 318*253+13=(318)253*313 congruent to 12531594323 congruent to 14 mod 19

    Is this the correct approach? I am not sure where 14 came from in the end I just guess and checked until I found a value that worked which was 14. Any explanations on how to correctly find 14?
     
  2. jcsd
  3. Feb 27, 2010 #2
    You were exactly right to use Fermat's Little Theorem to show that 34567 = 313 mod 19. From there I'd use binary exponentiation: 313 = 38+4+1 = 3834*3.

    So mod 19, 34 = 5, so then 38 = 3434 = 25 mod 19 = 6 mod 19.

    Put it together: 3834*3 = 6*5*3 mod 19 = 90 mod 19 = 14.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Modulo reduction problem
  1. Modulo 5 problem (Replies: 7)

Loading...