# Euler's theorem as primality test?

1. Jul 6, 2008

### huba

Using Euler's theorem, and the fact that $$\varphi(p) = p - 1$$ when p is prime, and the fact that 2 is coprime to all odd numbers, is it right to say that

$$2^{m-1} \equiv 1 \ (mod \ m)$$ iff m is prime > 2?

2. Jul 6, 2008

### ehrenfest

Yes, I think so.

3. Jul 6, 2008

### huba

Thanks. My question was related to another thread about prime numbers which resulted in the observation that Wilson's theorem can be used to test if an odd number is prime, but it is a far less efficient way of testing primality than trying factors <= the square root of a number.
I assume that Euler's theorem offers a primality testing method which is better than Wilson's theorem but still worse than the "square root method", in terms of the efficiency of the necessary computation. Does $$2^{m-1}$$ have to be calculated to check if $$2^{m-1}\equiv \ 1 (mod \ m)$$, or is there a shortcut?

4. Jul 6, 2008

### gel

Note that to calculate e.g., 232 you don't need to do 31 multiplications. 5 is enough.
\begin{align*} &2^2=4,\\ &2^4=4^2=16,\\ &2^8=16^2=256,\\ &2^{16}=256^2=65536,\\ &2^{32}=65536^2=4294967296. \end{align*}
To calculate 2(m-1) will require on the order of log(m) multiplications and additions. As you only need to do it modulo n, the multiplications are done on numbers no bigger than n.

Multiplying two numbers of size about n requires log(n)2 operations using the normal method of multiplication that you learn as a kid, because they will have log(n) digits.
However, Fast Fourier Transforms can improve this to log(n)log(log(n)).

Altogether, this gives a time on the order of log(n)2log(log(n)) to calculate 2n-1 modulo n.

However, does this really work as a primality test?

edit: it doesn't. Just tried some examples and got 561 = 3 * 11 * 17 is not prime, but 2560=1 (mod 561).

Last edited: Jul 6, 2008
5. Jul 6, 2008

### matt grime

No, it's not. Primes may be in P, but not by doing this. What you're describing isn't even as strong as being a Carmichael number.

6. Jul 6, 2008

### gel

Ah, looking at this I see that my counterexample of 561 is actually the smallest Carmichael number.

7. Jul 6, 2008

### gel

actually, 341=11*13 is the smallest counterexample. 2340=(210)34= 134=1 (mod 341).