Before we begin i would like to apologise for the lack of posts over the last week or so but Noah and I have both been quite busy.
In this second part of the Facts About Primes series, I will be looking at a fact which seems strange and perhaps unimportant at first, but is actually both quite simple and also quite useful.
Fact #2: All primes excepting 2 and 3 can be expressed as a multiple of six plus or minus one. For example, 7 = 6 x 1 + 1, 17 = 6 x 3 - 1, and so on.
Before we go into the proof of why this is true, we will first write out this fact in a more formal way.
N ∈ P, N > 3, N = 6k ± 1
This means as follows: The first part states that an integer N is prime (n ∈ m means n is part of the set m, and in this case the set P means the set containing all prime numbers). The second phrase then says N is larger than three. The third phrase then states that N = a multiple of six plus or minus one (6k just means a multiple of six, as k can represent any number).
The proof is quite simple and intuitive, and is as follows:
let N be any integer.
N can equal
6k = 6k, N is multiple of six and therefore not prime.
6k+1 can be prime, as it does not specifically factorise down further.
6k+2 = 2(3k+1), N is multiple of 2 and therefore not prime.
6k+3 = 3(2k+1), N is multiple of 3 and therefore not prime.
6k+4 = 2(3k+2), N is multiple of 2 and therefore not prime.
6k+5, or 6k-1, can be prime, as it does not specifically factorise down further.
Thus, for an integer N where N ∈ P, N > 3, N = 6k±1.
Of course, this doesn't mean that every multiple of six plus or minus one is prime. For example, 25 = 6x4+1, but is not prime as it is divisible by five.
If you can find another proof as to why this is true, please post it in the comments below.
Comments
Post a Comment