# Help with modular arithmetic

• Jul 12th 2012, 08:23 PM
joatmon
Help with modular arithmetic
I'm doing some self-study in cryptography and have come across something that I don't understand. Hoping somebody can help me with the gap in my knowledge.

I'm trying to follow an algorithm to compute exponentiation using Euler (really Fermat), and am stuck on some modular arithmetic. The problem before me is to compute

$\displaystyle 2^{{{110001}^{11}}^{1100001}} mod 23$

The example that I am studying right now says that this is equal to: $\displaystyle 2^{{{110001}^{11}}^{1100001} mod 22} mod 23$ , which I can see is an application of Fermat's theorem (since 23 is prime). The next step is what I don't understand. They go on to apply Fermat again, saying that:

$\displaystyle 110001^{{11}^{1100001}} \equiv 110001^{{11}^{1100001} mod 10} mod 22$

I understand why they switched to mod 10 (there are 10 elements in the set phi(22)). What I don't understand are the following:

1) How can they drop the base 2?
2) Where did the mod 23 go? (these might be the same property)

Clearly, there is some property of modular arithmetic that I don't understand in applying these theorems. Can anyone explain this to me?

Thank you!
• Jul 12th 2012, 08:41 PM
joatmon
Re: Help with modular arithmetic
(Doh)Never mind, I figured it out. They weren't saying that all of these are equivalent. In the second step they are just isolating the exponent for the purpose of simplifying it by way of Fermat's theorem. As the solution goes on, once they get the exponent simplified all the way, they go on to build back up sequentially to the original problem, which is then easily solvable. Thanks anyway.