# calculating nested exponents modulo n

I'm writing a primality testing program and want to test numbers like $3^{3^{3^{100}}} + 4 \mod 7$.

I use Euler's theorem to do this, so that the exponents get smaller. Instead of calculating $a^{b^c} \mod n$, I calculate $a^{b^{c \mod n_2}\mod n_1} \mod n$, where $n_1 = \phi(n)$ and $n_2 = \phi(\phi(n))$. This works sometimes, however, sometimes the exponent and the modulo is not relativly prime and Euler's theorem can not be used. Like in the above example with $3^{3^{3^{100}}} + 4 \mod 7$, it works in the first step, but not in the second, because $\gcd(3,6)\neq 1$.

One mathematician told me many years ago that it doesnt matter, because if you calculate $a^{(b \mod n_1)+n_1} \mod n$, it will still equal $a^b \mod n$. Even in the cases where $\gcd(a, n)\neq 1$. I have tested this and it seems to work.

My questions are: Under what circumstances does this work? Are there any exceptions, like $a = 0$ or $1$ or anything?

What theorems does this trick rely upon? What is the formal proof that it works? I don't want to use math that I dont understand in my program and I dont really understand why this works.

The main idea is that the number that should be tested is large, and the modulo is small. However, if anybody could give any hints of how to do it when the modulo is large, like ($2^{300}+1$) it would also be appreciated. It might be good for further, more advanced testing. It is enough to know that $a^b \mod n = c$ with a certain probability, if $n$ is large. I feel that this should be possible to do in some way, but I don't know how.

Thanks for any help.

Note that I am looking for mathematical tricks, not programming, so please don't ask me to use Java's BigInteger package or anything like that.

Note 2: Before anybody complains that I am writing mod wrong. I am referring to the binary operation modulo, not modular congruence.

http://en.wikipedia.org/wiki/Modulo_operation

They basically work the same, but the notation is a bit different.

$3^{3^{100}}\equiv3\pmod 6=6k+3$ where $k$ is a positive integer.

Using Fermat's Little Theorem, $3^6\equiv1\pmod 7\implies 3^{6k}\equiv1\pmod 7$

So, $3^{3^{3^{100}}}=3^{6k+3}\equiv1\cdot3^3\pmod 7\equiv-1$

EDIT:

If $c=b+k\phi(n)$ where $0\le b<\phi(n)$

Using Euler's Totient Theorem, $a^{\phi(n)}\equiv1 \pmod n$

$$a^{b+k\phi(n)}=(a^{\phi(n)})^k\cdot a^b\equiv1 \cdot a^b\pmod n$$

• Thanks, are there any more generic solutions? The example 3^(3^(3^100)) + 4 modulo 7 was just an example. – user1661303 Dec 28 '12 at 17:33
• As $3^{n+1}-3=3(3^n-1)$ is divisible by $3\cdot 2$ if integer $n\ge 0$ – lab bhattacharjee Dec 28 '12 at 17:34
• @user1661303, if $r\equiv s\pmod{\phi(m)}, a^r\equiv a^s\pmod m$. – lab bhattacharjee Dec 28 '12 at 17:37
• A little bit more generic yet. Sorry. – user1661303 Dec 28 '12 at 17:42
• @user1661303, not sure if you want more generic? If yes, please raise some specific cases where you had difficulties? – lab bhattacharjee Dec 28 '12 at 17:45