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

[vikkisut88]

Homework Statement

In this statement find the integer y such that x == y mod(n) where 0 =< y < n
x=2^71 n=23

Homework 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)

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.

 

[vikkisut88]

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

 

[borgwal]

Yes, of course, that's correct. Why the doubt?

 

[vikkisut88]

Yes, of course, that's correct. Why the doubt?

because I'm appalling at Number Theory so normally I'm wrong

 

[borgwal]

because I'm appalling at Number Theory so normally I'm wrong

Times have changed :-)