The first is the correct one. Unfortunately, I don't understand your second method.
My way:
If 2 numbers a=b mod(n), does that imply they are congruent modulo as well?
Anyway on to the matter at hand. Calculate 2^258 (mod 259)I did it 2 different ways and unfortunatly got 2 different answers.
2^(64)=86 mod 259,
2^(128)=144,
2^(256)=16 so 2^256.2^2=64 (mod 259). I know my method isn't very clear but you probably get the idea.
Method 2
259 = 7 x 37
2^6=1 mod(7)
2^258=(2^6)^43=1 mod (7)
2^36=1 mod(37)
2^258=(2^36)^7.2^6=27 mod(37)
but 1 x 27=27 not 64.
I have a strong feeling my first method is correct. Which one is correct and why is the other wrong?
Explaining my second answer. I've seen it that you can express the modulus as a factor of primes and then find your a^b under each modulus you should get the same answer both times,(Your not meant to multiply them as i did). Here is a link with an example using this method.
http://uk.answers.yahoo.com/question...3030517AA4R5UI
Ok! Now I am understand what you tried to do!
You thought using Fermat's little theorem.
This theorem is not so helpful in your case. Why?
There is a lemma which states:
If and are different primes and and , then
Try to work with that in your question, and see what you get...