I have noticed whispers regarding the notion of using Euler's Theorem to verify if a number is prime or not.
Typically, it is written as 6n +/- 1 (plus or minus), and this site has it marked as 6n + 1 only.
When I went to test this, I found numbers such as "143" showed incorrectly as being prime due to :
143 – not a prime
6n + 1 = 143
6n = 143 - 1
n = 142 / 6
n = 23.666~7
6n - 1 = 143
6n = 143 + 1
n = 144 / 6
n = 24
149 – prime
6n + 1 = 149
6n = 149 - 1
n = 148 / 6
n = 24.666~7
6n - 1 = 149
6n = 149 + 1
n = 150 / 6
n = 25
If you notice both pass Euler's test under the evaluation of 6n-1. Am I oversimplifying Euler's theorem as used in so called prime verification, or is it just broken for this purpose ?
Is the only real way to validate primes reliably to use the sieve of Eratosthenes ? Or is there another method, or am I just not understanding what appears to be a very simple theorem ?
Best Answer
What you wrote has very little to do with any primality test I've ever heard of. You seem to be just verifying that your number can be written as $6n \pm 1$. If you're talking about Euler's $6n+1$ theorem, what that says is that any prime of the form $6n+1$ can be written as $x^2 + 3 y^2$ where $x$ and $y$ are positive integers. But that's not a primality test either: there are lots of composite numbers of the form $x^2 + 3 y^2$.
A primality test associated with the name Euler is: if $b$ is a positive integer and $n$ is an odd prime that does not divide $b$, $b^{(n-1)/2} \equiv \pm 1 \mod n$. That's a necessary condition but not sufficient: a composite $n$ with this property for a given $b$ is called an Euler pseudoprime to base $b$.