The first is the correct one. Unfortunately, I don't understand your second method.
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^(256)=16 so 2^256.2^2=64 (mod 259). I know my method isn't very clear but you probably get the idea.
259 = 7 x 37
2^258=(2^6)^43=1 mod (7)
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?
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...