A Starting Place

Lets begin with definitions , then a theorem, and proceed with a proof and an example.

Definition: A prime is a positive integer greater than 1 that is divisible by no positive integer other than 1 and itself.

Definition: If a and b are integers with a ≠ 0, we say that a divides b if there is an integer c such that b = ac. If a divides b, we also say that a is a divisor or factor of b and that b is a multiple of a.

Theorem 0.1: Let S = { 6n ± 1, where n is a natural number}, and let p be a natural number with p > 3. If p is a prime number, then p is in S.

[Note: For my purpouses I am considering the natural numbers to be integers strictly greater than zero.]

Proof 0.1 (proof by contradiction): Let S = { 6n ± 1, where 0 < n and n is a natural number}. Let p be a natural number and let p > 3. Assume p is a prime number, and assume p is not in S. Because p is not in S, p is a natural number, and p > 3, then by inspection
p = 6k - 2, p = 6k, p = 6k, p = 6k + 2, or p = 6k +3 where k is natural.

Case 1: Consider when p = 6k - 2 or p = 6k + 2. Now we may write
6k - 2 = 2(3k - 1), and 6k + 2 = 2(3k + 1) by factoring out a 2. Now because k is a natural number 3k - 1 and 3k + 1 are also natural numbers. Then there exists a natural number m such that
p = 2m, so p is not prime because p is divisible by 2 and m (by the definitions of prime and divisible).

Case 2: Consider when p = 6k or p = 6k + 3. By factoring out a 3 we get 6k = 3(2k) and 6k + 3 = 3(2k + 1). We know 2k and 2k+1 are natural numbers because k is natural, so there exists a natural number l such that p = 3l. So p is not prime because it is divisible by 3 and l (by the definitions of prime and divisible).

Now we have a contradiction, because we assumed p was prime, and we showed that when p is not in S p is never prime. Therefore if p is a prime number, then p is in S. □

Example 0.1: Show that the prime number 101 is in set S.
101 = 6*17 - 1 and 17 is a natural number so 101 is in S.

[Definitions of prime and division taken from Elementary Number Theory and Its Applications Fifth Edition by Kenneth H. Rosen and AT&T Laboratories]

On the subject of the set S := { x , x = 6n ± 1 with n being a natural number }

For every x = 6n ± 1 (n being natural), let i be called the primary index number for x, such that when x = 6n - 1, i = 2n - 1, and when x = 6n + 1, i = 2n. Call n the secondary index number.

Claim 1: Every element of S that is not prime may be written as the product of two other elements of S.

Example 1: 25 = 6*4+1 so 25 is in S. 25 = 5*5 so it is not prime. 5 = 6*1 - 1, so 5 is in S. So 25 which is in S and not prime can be written as the product of two numbers also in S.

Claim 2: If m is an element of S is not prime, then i, the index number for m, may be written as i = 2kx + j OR i = 2kx - (j+1), where x is an element of set S, j is the primary index number for x, and k is a natural number.

Claim 2.1: In this form x is a factor of m and k is the secondary index number for another factor of m, call this factor y (y in S), where y = 6k - 1 when i = 2kx - (j+1), and y = 6k + 1 when i = 2kx + j.

Example 2: For m = 25, i = 8. We can write 8 = 2*1*5 - (1+1), where 5 is in S (shown in example 1), and 1, so the other factor of 25 is 6*1 - 1 = 5 (because we wrote 8 = 2*1*5 - (1+1)). So the factors of of 25 are 5 and 5.

Getting Started

I'm starting this blog to publish some thoughts, theorems, and proofs of those theorems. I see myself in the near future writing on the topic of prime numbers of the form 6n ± 1. Here is an example of a proof of a theorem on the topic.

[Note: I think my friend Avery Cotton is at slight confusion over the definitions of proof of contrapositive, and proof by contradiction. It is my understanding that proof by contradiction is a proof strategy in which one assumes both the negation of the conclusion, and the hypothesis (example: to prove "if P, then Q" by contradiction assume P and assume not Q). This works because the contrapositive (if not Q, then not P) is logically equivalent to the argument (if P, then Q). Therefore assume the the hypothesis and the negation of the conclusion and you will arrive at a contradiction if and only if the argument is valid.]


The strategy "proof by contradiction" examines the highlighted portion of the truth table. By showing this you show the argument is valid.