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!

Finding x = ymod(n) for x=2^71 and n=23

  1. Nov 9, 2008 #1
    1. The problem statement, all variables and given/known data
    In this statement find the integer y such that x == y mod(n) where 0 =< y < n
    x=2^71 n=23

    2. Relevant equations
    Let p be a prime number and let a be an integer which is not divisible by p. Then a^(p-1) == 1mod(p)


    3. The attempt at a solution
    I am really struggling as to where to start out with this as obviously 2^71 is too large a number to show fully on any normal or scientific calculator(something like 2.361... x 10^21) and so when dividing by 23 this merely gives 1.0266... x 10^20 which doesn't allow you to find a remainder.
    I'm not sure if the above equation using p as a prime number is of any relevance, but this would suggest that a^22 ==1mod(23). But i don't know where to go from there, if I can use it at all.
     
  2. jcsd
  3. Nov 9, 2008 #2
    Okay so after reading through my notes for about the millionth time, I'm not sure if i've just worked it out. See whether you think this is right?!

    As n is a prime number, 2^22 == 1 mod(23)

    Hence 2^71 == 2^66.2^5
    == (2^22)^3 . 2^5
    == 2^5 == 32
    == 9 mod(23)

    So y = 9
     
  4. Nov 9, 2008 #3
    Yes, of course, that's correct. Why the doubt?
     
  5. Nov 9, 2008 #4
    because I'm appalling at Number Theory so normally I'm wrong :-p
     
  6. Nov 9, 2008 #5
    Times have changed :-)
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Finding x = ymod(n) for x=2^71 and n=23
  1. Prove x^n < n! (Replies: 4)

Loading...