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 theorem 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?