All prime numbers greater than 3 can be written in the form of 6n+1 or 6n-1
OR
All prime numbers greater than 3 are congruent to 1 mod 6 or 5 mod 6
Proofs:
I. Proved by casesAll positive integers can be written in the form of base 6, hence we can write all positive integers in an unique form of 6n+x, where x = 0, 1, 2, 3, 4, 5 strictly. The value of x is just the remainder of a particular number N when divided by 6, hence x >= 6 is simply not practical, eg. 6n+6 = 6(n+1) Now we have our proof:
- x = 0 -> N = 6n + 0 = 6n -> N is divisible by 6 -> N is not prime.
- x = 1 -> N = 6n + 1 -> Do not have obvious divisor, it has to depend on n
- x = 2 -> N = 6n + 2 = 2(3n+1) -> N is divisible by 2 -> N is not prime
- x = 3 -> N = 6n + 3 = 3(2n+1) -> N is divisible by 3 -> N is not prime
- x = 4 -> N = 6n + 4 = 2(3n+2) -> N is divisible by 2 -> N is not prime
- x = 5 -> N = 6n + 5 -> Do not have obvious divisor, it has to depend on n
Therefore, we can conclude that for all positive integers, when written in the form of 6n+x, if x = 0, 2, 3 or 4, it's not a prime number. So what we left is just the form of 6n+1 and 6n+5, where all prime numbers greater than 3 will lie in. Hence all prime numbers can be written in the form of either 6n+1 or 6n+5 (or 6n-1, they are equivalent). This also concludes that all prime numbers are congruent to either 1 mod 6 or 5 mod 6. This ends the proof.
Note: All prime numbers can be written in these 2 forms but it does NOT mean that all numbers given by 6n+1 and 6n-1 are prime numbers! This will be converse error!
II. Direct proof For all prime numbers larger than 2, it's odd. (Since 2 divides all even numbers)
Let p = any prime number, then
p = 2n+1 or 2n-1, n = positive integer
For all p > 3, p must not be divisible by 3. Since p = 2n+1 = 2(n-1) + 3, n-1 must not be divisible by 3, hence if n is a multiple of 3(simplest case), then n-1 is not divisible by 3. Similar reasoning for p = 2n-1.
Let n = 3N, where N is positive integer, then
p = 6N + 1 or 6N - 1 for all p > 3
This ends the proof.
-------------------------------------------------------------------------------------------
This statement gives us another way to determine whether a number is prime number, just divide the number by 6, if the remainder is not 1 or 5, then we can straight away say it's not a prime number. If the remainder happens to be 1 or 5, however, we still need a brute force checking before we can confirm it's a prime. Anyway there's a more general theorem for this, this is just a special case of that, which is more popular.