Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

1 Answer

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

share|improve this answer
    
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
show 2 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.