Q:

Euler's theorem to validate prime numbers shows non-primes as valid

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 ?

A:

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

