Solve 2^27841 mod 34 by Hand: Discrete Math Problem Solution

[raross]

could someone show me how u would solve 2^27841 mod 34 by hand? I know what theorm to use, I am just having trouble using it? Thanks

 

[AKG]

What theorem would you use? Anyways, if it helps, 27841 = 11x2531 and 34 = 2x17. I found that 11 was a factor of 27841 by trial and error, and then by a lot more trial and error, found that 2531 is prime. Hopefully I didn't make a mistake in the calculations.

 

[amcavoy]

Is there any other way to do this without changing the base?

 

[NateTG]

Euler's totient theorem?
Is a bit tricky because 34 and 2 are not co-prime.
but
2^{17} \equiv 2 \mod 34
Then we can use that
27841 \equiv 1 \mod 16
to get
2^{27841} \equiv 2^{1} \equiv 2 \mod 34

 

[raross]

hrm yeah that works. How would you solve it with modular exponentiation?