Euler's theorem as primality test?

In summary: Yes, I think so.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. In summary, 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. However, 2^{m-1} has to be calculated to check if 2^{m-1}\equiv \ 1 (mod \ m), or is there a shortcut?
  • #1
huba
32
0
Using "[URL theorem[/URL], and the fact that [tex]\varphi(p) = p - 1[/tex] when p is prime, and the fact that 2 is coprime to all odd numbers, is it right to say that

[tex]2^{m-1} \equiv 1 \ (mod \ m)[/tex] iff m is prime > 2?
 
Last edited by a moderator:
Physics news on Phys.org
  • #2
huba said:
Using "[URL theorem[/URL], and the fact that [tex]\varphi(p) = p - 1[/tex] when p is prime, and the fact that 2 is coprime to all odd numbers, is it right to say that

[tex]2^{m-1} \equiv 1 \ (mod \ m)[/tex] iff m is prime > 2?

Yes, I think so.
 
Last edited by a moderator:
  • #3
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 [tex]2^{m-1}[/tex] have to be calculated to check if [tex]2^{m-1}\equiv \ 1 (mod \ m)[/tex], or is there a shortcut?
 
  • #4
Note that to calculate e.g., 232 you don't need to do 31 multiplications. 5 is enough.
[tex]
\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*}
[/tex]
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:
  • #5
ehrenfest said:
Yes, I think so.

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
matt grime said:
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.

Ah, looking at http://en.wikipedia.org/wiki/Carmichael_number" I see that my counterexample of 561 is actually the smallest Carmichael number.
 
Last edited by a moderator:
  • #7
actually, 341=11*13 is the smallest counterexample. 2340=(210)34= 134=1 (mod 341).
 

1. What is Euler's theorem as primality test?

Euler's theorem as primality test is a mathematical theorem that states that if a and n are coprime positive integers, then a raised to the power of φ(n) (Euler's totient function) is congruent to 1 modulo n. In simpler terms, this means that if a and n are relatively prime, then a raised to the power of φ(n) is divisible by n, making n a prime number.

2. How is Euler's theorem used as a primality test?

Euler's theorem can be used as a primality test by checking if a raised to the power of φ(n) is congruent to 1 modulo n. If it is, then n is likely to be a prime number. However, this test is not foolproof and may give false positives, so it is often used in conjunction with other primality tests.

3. Can Euler's theorem be used to test large numbers for primality?

Yes, Euler's theorem can be used to test large numbers for primality. However, as the numbers get larger, the calculations become more complex and time-consuming. Therefore, it is more commonly used for smaller numbers or in combination with other primality tests for larger numbers.

4. What are the advantages of using Euler's theorem as primality test?

One advantage of using Euler's theorem as a primality test is that it is relatively easy to understand and implement. Additionally, it is a deterministic test, meaning that it will always give the same result for a given input. However, as mentioned before, it is not a foolproof test and may give false positives, so it is often used in combination with other tests.

5. Are there any limitations to using Euler's theorem as primality test?

Yes, there are some limitations to using Euler's theorem as a primality test. One limitation is that it may give false positives for certain numbers, meaning that it may classify a composite number as prime. Additionally, as the numbers get larger, the calculations become more complex and time-consuming, making it less practical for testing extremely large numbers. It is also not as accurate as other primality tests, such as the Miller-Rabin test. Therefore, it is often used in combination with other tests to improve accuracy and efficiency.

Similar threads

I ##(p^k -1) \equiv X \mbox{(mod p)}## via Wilson's theorem
    • Linear and Abstract Algebra
Replies
2
Views
856
I Question on Primitive Roots and GCDs
    • Linear and Abstract Algebra
Replies
2
Views
785
MHB Show that the groups are abelian
    • Linear and Abstract Algebra
Replies
1
Views
782
I Proof for a congruence relation
    • Linear and Abstract Algebra
Replies
17
Views
1K
I Spectral theorem for Hermitian matrices-- special cases
    • Linear and Abstract Algebra
Replies
2
Views
596
If ## p ## and ## p^{2}+8 ## are both prime numbers, prove that....
    • Precalculus Mathematics Homework Help
Replies
16
Views
2K
Prove that ## 1^{p-1}+2^{p-1}+3^{p-1}+\dotsb +(p-1)^{p-1}\equiv -1 ##.
    • Precalculus Mathematics Homework Help
Replies
1
Views
1K
B Calculating the coprime probability of two integers in a different way
    • General Math
Replies
13
Views
1K
Show that the sum of twin primes ## p ## and ## p+2 ## is divisible?
    • Precalculus Mathematics Homework Help
Replies
17
Views
2K
Prove that ## 1^{p}+2^{p}+3^{p}+\dotsb +(p-1)^{p}\equiv 0\pmod {p} ##.
    • Calculus and Beyond Homework Help
Replies
6
Views
2K

Hot Threads

Recent Insights

Back
Top