# Homework Help: Discrete Math Problem

1. Nov 2, 2005

### raross

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

2. Nov 2, 2005

### 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.

3. Nov 2, 2005

### amcavoy

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

4. Nov 2, 2005

### 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$$

5. Nov 3, 2005

### raross

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