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

1. Nov 9, 2008

### vikkisut88

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. Nov 9, 2008

### 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

3. Nov 9, 2008

### borgwal

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

4. Nov 9, 2008

### vikkisut88

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

5. Nov 9, 2008

### borgwal

Times have changed :-)