checking if a number is a prime

Question

I was reading Wikipedia, and it was given that "all primes are of the form 6k ± 1" (other than 2 and 3), where k = 1,2,3,4,...

Is this statement correct? If yes, can we use this to test if a given number is a prime number? For instance, we can say that 41 is a prime number, since there exists an integer K (K >= 1), such that 6k - 1 = 41 ==> k = 7.

I am confused why this test cannot be used to test if a number is prime?

Thanks, Sekhar

All primes $\neq 2,3$ are of the form $6k\pm 1$, but not all numbers of the form $6k\pm 1$ are primes. — user236182, Oct 10 '15 at 21:24
Please notice that comments are not for answering the question. Please consider posting these as answers, or someone else will do this. — dbanet, Oct 10 '15 at 21:27

score 1 · Answer 1 · edited Jun 06 '16 at 15:49

1

For $k\ge 1$ no prime can be of the form $6k$ (obvious), $6k+2=2(3k+1)$, $6k+3=3(2k+1)$, $6k+4=2(3k+2)$. There remains $6k+1$ and $6k+5=6(k+1)-1$.

edited Jun 06 '16 at 15:49

hardmath

37,015

answered Oct 10 '15 at 21:37

Bernard

175,478

score 1 · Answer 2 · answered Oct 10 '15 at 22:00

1

If a number can be in the form $6k\pm1$ "CAN" be a prime number but not always. A prime number $p>3$ can be always in this form. If you want a text to know if a number is prime you can use the Wilson's theorem : $(p-1)\equiv -1\pmod p$

answered Oct 10 '15 at 22:00

Domenico Vuono

2,672

Your statement of Wilson's theorem isn't right: it should say that $p$ is prime iff $(p-1)! \equiv -1$ (mod $p$). Wilson's theorem is not a practical test for primality. – Rob Arthan Oct 10 '15 at 22:30
@DomenicoVuono, you may want to edit your answer to reflect what have been discussed in the comments. – Element118 Dec 23 '15 at 12:35

checking if a number is a prime

2 Answers2

Linked

Related