1.) We proved Euclid’s theorem in k-index filtering. This is important and fundamental approach to the proof using positive integers k.
The Fundamental Partition
We begin with formal definitions. Let K be the set of positive integers. We define two disjoint subsets of K whose union is K.
Definition 1: Let C be the set of all integers k in K that can be expressed in the form k = xy + x + y for some positive integers x and y.
Definition 2: Let P be the complement of C in K, such that P = K \ C.
Theorem 1: The Structure of the Partition
The sets C and P have a fundamental connection to composite and prime numbers.
(i) An integer k is in C if and only if k+1 is a composite number.
- Proof: If k is in C, then k = xy + x + y for some positive integers x, y. Adding 1 to both sides gives k + 1 = xy + x + y + 1, which factors into k + 1 = (x + 1)(y + 1). Since x ≥ 1 and y ≥ 1, both (x + 1) and (y + 1) are integers greater than or equal to 2. Thus, k+1 is a product of two integers greater than 1, making it a composite number.
(ii) An integer k is in P if and only if k+1 is a prime number.
- Proof: Since P is the complement of C, k is in P if and only if k+1 is not composite. For a positive integer, not being composite means it is either 1 or a prime number. However, the smallest possible value for k in C is 1*1 + 1 + 1 = 3, which means the smallest composite number of the form k+1 is 4. Therefore, k+1 can never be 1 for any k in C. It follows that if k is in P, k+1 must be a prime number.
(iii) Both sets, C and P, are infinite.
- The infinitude of C is straightforward. For instance, letting x=1, we get k = 1*y + 1 + y = 2y + 1. As y ranges over all positive integers, this generates all odd integers greater than or equal to 3, which is an infinite set.
- The infinitude of P requires a more substantial proof.
Proving the Infinitude of P
Goal: To prove that the set P is infinite. This proof will adapt Euclid’s classic argument for the infinitude of primes to the structure of set P. Proving that P is infinite is logically equivalent to proving that the set of prime numbers is infinite.
Proof:
We will use a proof by contradiction.
- Assumption: Assume, for the sake of contradiction, that the set P is finite.
- Setup: If P is finite and non-empty, we can list all of its elements: P = {k₁, k₂, …, kₙ}.
- Map to Primes: By Theorem 1(ii), each element kᵢ in P corresponds to a unique prime number pᵢ = kᵢ + 1. If our list of elements in P is complete, then our corresponding list of primes {p₁, p₂, …, pₙ} must contain all prime numbers.
- Construction: Construct a new integer, M, by taking the product of all these primes:
M = p₁ * p₂ * … * pₙ - Consider a New Number: Now, consider the integer K = M + 1. Since M is a product of primes, M ≥ 2, and thus K > 1.
- Finding a Prime Factor: Every integer greater than 1 must have at least one prime divisor. Let q be a prime divisor of K.
- The Contradiction: We ask: is this prime q one of the primes in our supposedly complete list {p₁, p₂, …, pₙ}?
- Let’s assume it is. If q were equal to some pᵢ from our list, then q must divide M, since M is the product of all the pᵢ.
- By our construction, we also know that q divides K = M + 1.
- If q divides both M and M + 1, then it must also divide their difference, which is (M + 1) – M = 1.
- However, no prime number can divide 1. This is a contradiction.
- Conclusion: Our assumption that q was in the list {p₁, p₂, …, pₙ} must be false. Therefore, q is a prime number not in our original list. Since q is a prime number, the integer k_new = q – 1 must be an element of P. This k_new was not in our original finite list of elements of P.
We have demonstrated that for any finite subset of P, we can always construct another element of P that is not in that subset. Therefore, the set P cannot be finite and must be infinite.
Addendum Lemma: The Diophantine and Computable Nature of the Partition
We can further classify the sets C and P using the language of computability theory, which provides a deeper context for the partition.
(i) The Nature of C (The “Composite” Set)
- C is a Diophantine Set: An integer k is in C if and only if the polynomial equation P(k, x, y) = k – (xy + x + y) = 0 has a solution in the set of positive integers. This property, being definable by a polynomial equation, makes C a Diophantine set by definition.
- C is Recursively Enumerable: As a direct consequence of the Matiyasevich theorem (which establishes the equivalence of Diophantine sets and recursively enumerable sets), the set C is recursively enumerable (r.e.). This means an algorithm exists that can list every element of C, one by one, without end.
(ii) The Nature of P (The “Prime” Set)
- P is a Recursive Set: An integer k is in P if and only if k+1 is prime. Since there exists a terminating algorithm (a primality test, such as the AKS primality test) to decide whether any given integer k+1 is prime, the set P is a recursive set (also known as a decidable set). We can always determine membership in P in a finite number of steps.
- P is Recursively Enumerable and Diophantine: A fundamental result of computability theory is that every recursive set is also recursively enumerable. By applying the Matiyasevich theorem again, since P is r.e., P must also be a Diophantine set.
(iii) Conclusion and Significance
The Fundamental Partition is a case study where not only the initial set C but also its complement P are Diophantine. This reveals a symmetry in their classification, yet a deep asymmetry in their complexity.
- The set C (indices of composites minus one) is generated by a simple, explicit polynomial. It is “obviously” Diophantine.
- The set P (indices of primes minus one), while proven to be Diophantine by a chain of powerful theorems, is defined by a polynomial of immense complexity that is not easily constructed.
This demonstrates that the partition of natural numbers into prime- and composite-indexed sets (shifted by one) corresponds to a partition into two infinite, enumerable, and Diophantine sets. The deceptive simplicity of one side of the partition (C) belies the hidden structure and complexity of the other (P).
This proves that the method functions as a sieve over k using set-theoretic operations, and there are infinitely many such k in this framework which yield a prime number in n=k+1.
2.) We move the discussion to 6k+-1 numbers. We demonstrate all primes greater than 3 must be of this form using mod 6 arithmetic.
Why 6k ± 1?
Any integer can be represented in one of the following forms when divided by 6: 6k, 6k+1, 6k+2, 6k+3, 6k+4, or 6k+5.
Eliminating other forms:
6k is divisible by 6.
6k+2 is divisible by 2.
6k+3 is divisible by 3.
6k+4 is divisible by 2.
The remaining forms:
This leaves us with 6k+1 and 6k+5 (which is the same as 6k-1).
Not all are prime:
While all primes greater than 3 fit this form, not all numbers of this form are prime. For instance, 25 is of the form 6k+1 (6*4+1), but it is not a prime number.
3.) We generalize a parameterization of |6k+1| and show it has complete coverage for all composites in 6k ± 1, using non-zero variables k,x,y.
Lemma (Completeness of Composite Coverage)
Let N be a positive integer such that N ≡ ±1 (mod 6) and N is composite. Then the index k for which N = 6k ± 1 belongs to the set:
K_composite = { |6xy + x + y| : x, y ∈ ℤ \ {0} }
This proves that the k-index filter correctly identifies all composite numbers of the form 6k ± 1.
Proof
We must show that for any composite number N ≡ ±1 (mod 6), its corresponding index k can be generated by the form |6xy + x + y| for some non-zero integers x and y. We proceed by cases based on the residue of N modulo 6.
Note: Since N ≡ ±1 (mod 6), the prime factors of N must also be congruent to ±1 (mod 6). Thus, every prime divisor of N is of the form 6m ± 1.
Case 1: N is composite and N ≡ 1 (mod 6).
Since N is composite, write N = AB, where A, B > 1. To satisfy N ≡ 1 (mod 6), either:
Subcase 1a: A ≡ 1 (mod 6) and B ≡ 1 (mod 6).
Then A = 6x + 1, B = 6y + 1 for some x, y ∈ ℕ. Since A, B > 1, we have x, y ≠ 0. Then:
N = (6x + 1)(6y + 1) = 36xy + 6x + 6y + 1 = 6(6xy + x + y) + 1.
Thus, N = 6k + 1 where k = 6xy + x + y > 0, so k = |6xy + x + y| ∈ K_composite.
Subcase 1b: A ≡ -1 (mod 6) and B ≡ -1 (mod 6).
Then A = 6u − 1 and B = 6v − 1 for some u, v ∈ ℕ. Let x = –u and y = –v, which are non-zero integers. Then:
N = (6x + 1)(6y + 1) = 6(6xy + x + y) + 1.
So again, N = 6k + 1, with k = |6xy + x + y| ∈ K_composite.
Thus, in both subcases of Case 1, composite numbers N ≡ 1 (mod 6) yield indices k in K_composite.
Case 2: N is composite and N ≡ -1 (mod 6).
Write N = AB, A, B > 1, such that one of A, B ≡ 1 (mod 6), and the other ≡ -1 (mod 6). Without loss of generality, let A = 6x + 1 and B = 6y − 1, with x, y ∈ ℕ.
Then:
N = (6x + 1)(6y − 1) = 36xy − 6x + 6y − 1 = 6(6xy − x + y) − 1.
So N = 6k − 1 with k = 6xy − x + y.
Let a = x, b = −y. Then:
6ab + a + b = 6x(−y) + x − y = −6xy + x − y = –k.
Thus, k = |6ab + a + b|, and k ∈ K_composite.
Therefore, every composite N ≡ −1 (mod 6) has index k ∈ K_composite.
Conclusion
In all cases, whether N ≡ 1 or N ≡ –1 (mod 6), if N is composite, then its associated index k = (N – 1)/6 or (N + 1)/6 is in the set K_composite. Therefore, the filtering model using the form k = |6xy + x + y| correctly and completely identifies all indices corresponding to composite numbers of the form 6k ± 1.
(Q.E.D.)
4.) We show that Dirichlet’s theorem guarantees infinitely many primes in arithmetic progressions p=6k-1 and p+2=6k+1, where k have the same value; and that in combination, these two sequences in combination yield all primes >3.
Goal:
Show that:
Each of the sequences {6k – 1} and {6k + 1} contains infinitely many primes, and
Together, they include all primes greater than 3.
Step 1: Classification modulo 6
Every integer n can be written uniquely in one of the following forms:
n = 6k
n = 6k + 1
n = 6k + 2
n = 6k + 3
n = 6k + 4
n = 6k + 5
Now we examine these forms:
6k is divisible by 6 and therefore composite (except for 6 itself).
6k + 2 is divisible by 2 and is composite.
6k + 3 is divisible by 3 and is composite.
6k + 4 is divisible by 2 and is composite.
This leaves 6k + 1 and 6k + 5 as candidates for primes. Note that 6k + 5 is equivalent to 6(k + 1) – 1, which is in the form 6k – 1.
Therefore, all primes greater than 3 must be in the form 6k – 1 or 6k + 1.
Step 2: Application of Dirichlet’s Theorem
Dirichlet’s theorem on arithmetic progressions states:
If a and d are positive integers with gcd(a, d) = 1, then the arithmetic sequence a + nd contains infinitely many primes.
We apply this to two sequences:
Sequence 1: 6k + 1
This is an arithmetic progression starting at 1 with a common difference of 6. Since gcd(1, 6) = 1, Dirichlet’s theorem guarantees it contains infinitely many primes.
Sequence 2: 6k – 1
This can be rewritten as 6k + 5. It starts at 5 and has a common difference of 6. Since gcd(5, 6) = 1, Dirichlet’s theorem also guarantees this sequence contains infinitely many primes.
Step 3: Exhaustion of All Primes > 3
From Step 1, we saw that any prime greater than 3 must be congruent to either +1 or -1 modulo 6. This means any such prime must lie in either 6k + 1 or 6k – 1.
Conclusion:
Both sequences 6k – 1 and 6k + 1 contain infinitely many primes. Moreover, all primes greater than 3 are in one of these two sequences. Therefore, these sequences together not only cover all primes greater than 3, but each sequence individually contains infinitely many primes due to Dirichlet’s theorem.
Q.E.D.
5.) Returning to (3.) we show from the result in (4.) that there must be infinitely many -k in n=|6k+1| which yield a prime of the form n=6k-1 and there must be infinitely many +k yielding a prime in n=6k+1. (At this point we cannot prove this happens simultaneously infinite number of times for -k,k in n=|6k+1| where k has the same absolute value for -k and +k, but we can make a deterministic statement of the twin prime conjecture for twin prime pairs greater than 3,5 following from the prior steps.
We now extend the results from Point 3 (completeness of composite coverage) and Point 4 (Dirichlet’s theorem and 6k ± 1 primes) to make further conclusions about the form n = |6k + 1|.
Recall from Point 3:
Any composite number of the form 6k ± 1 corresponds to a value of k that lies in the set:
K_composite = { |6xy + x + y| : x, y ∈ ℤ \ {0} }
This means if a value of k is in K_composite, then either 6k − 1 or 6k + 1 is a composite number.
Conversely, if k is not in K_composite, then it is a candidate for generating a prime of the form 6k − 1 or 6k + 1 (or both).
From Point 4, we know that:
There are infinitely many primes of the form 6k + 1.
There are infinitely many primes of the form 6k − 1.
Now consider the form n = |6k + 1|.
This expression can produce either:
n = 6k + 1, if k > 0 (positive k)
n = −6k − 1 = 6(−k) − 1, if k < 0 (negative k)
So for every negative value of k, n = |6k + 1| generates a number of the form 6(−k) − 1. For positive k, n = |6k + 1| = 6k + 1.
Therefore, if we look at all values of k in the integers excluding zero, the set of outputs of |6k + 1| covers all numbers of the form 6k + 1 (when k > 0) and 6k − 1 (when k < 0, since −k > 0). In other words:
For k > 0, |6k + 1| = 6k + 1 → this maps to primes of the form 6k + 1.
For k < 0, |6k + 1| = −6k − 1 = 6(−k) − 1 → this maps to primes of the form 6k − 1.
Since both 6k + 1 and 6k − 1 contain infinitely many primes (as shown in Point 4), and both are reached via ±k in the function |6k + 1|, it follows that:
There must be infinitely many positive values of k such that 6k + 1 is prime.
There must be infinitely many negative values of k such that 6(−k) − 1 = |6k + 1| is prime.
In other words, there are infinitely many ±k values such that |6k + 1| yields a prime.
However, at this stage, we cannot yet prove that there are infinitely many pairs of values where both 6k − 1 and 6k + 1 are simultaneously prime for the same value of |k|. That is the twin prime condition. But what we can say deterministically is:
The function n = |6k + 1| generates both 6k + 1 and 6k − 1 depending on the sign of k.
Infinitely many of these outputs will be prime, due to the independent infinitude of 6k ± 1 primes.
Thus, we are now in a position to restate the twin prime conjecture deterministically in terms of indices k not belonging to K_composite. This sets the stage for the full index-based restatement in Point 6.
6.) We restate the Twin Prime Conjecture using the framework.
Twin Prime Index Conjecture
Let:f(x,y)=∣6xy+x+y∣
where 𝑥,𝑦 ∈ 𝑍∖{0} (i.e., both are non-zero integers, so may be positive or negative).
Define the set:
𝐾composite = {𝑓(𝑥,𝑦): 𝑥≠0, 𝑦≠0}
Then: A positive integer 𝑘 is the index of a twin prime pair (6𝑘−1,6𝑘+1) if and only if:
𝑘∉𝐾composite
Therefore, the Twin Prime Conjecture is true if and only if:
𝑍+∖𝐾composite is infinite
In plain language:
There are infinitely many twin primes if and only if there are infinitely many positive integers 𝑘 that cannot be written in the form ∣6𝑥𝑦+𝑥+𝑦∣ for any non-zero integers 𝑥,𝑦.