Calculate 2^66 is congruant to 1(mod66)?

Question

And also need to calculate 3^44(mod43)
Thank you, any help much appreciated

Sorry the first question should be calculate 2^66 is congruant to 1(mod67)

i don't know how to apply fermats theorem. That should have been my question!

Answer 1

Do you want to use FLT? In that case, just notice that p=67 is prime and apply it directly. Similarly, with p=43, you find that 3^42=1 (mod 43). Now, 3^44=(3^42)(3^2)=1*9=9 (mod 43).

If you actually want to do the full multiplication, just do this:
2^6=64=(-3) (mod 67)
2^(12)=[2^6]^2=(-3)^2=9 (mod 67)
2^(24)=[2^12]^2=9^2=81=14 (mod 67)
2^(48)=[2^24]^2=14^2=196=(-5) (mod (67)
2^(66)=(2^48)(2^12)(2^6)=
(-5)(9)(-3)=135=1 (mod 67).

Answer 2

I think you put the question in wrong.
2^66 = 64(mod 66) But I think you meant
2^66 = 1 (mod 67) Which is called 'Fermats Little Theorem' and says if p is prime, then
a^(p-1) = 1 (mod p)

3^44 = 9 (mod 43) and *you* figure out the congruence relationship required ☺


Doug