# Using ordered pairs and sequences to give a required condition for any counter-example to Legendre's Conjecture

I found it very challenging to write this question. I apologize for any ambiguity.

This is an argument that I am working on related to Legendre's Conjecture. I appreciate any questions or any corrections. :-)

Let:

• $$x > 1$$ be an integer
• $$T(x)$$ be the set of primes $$p$$ such that $$0 < p < x$$ and $$p \nmid x(x+1)$$
• $$|T(x)|$$ be the count of elements in $$T(x)$$
• $$S_{T(x)}$$ be a set of ordered pairs $$(p_i,p_j)$$ with the following properties:
• $$p_i \ne p_j$$
• $$x^2 + x - p_i \equiv 0 \pmod {p_j}$$
• $$p_i,p_j \in T(x)$$

Definitions:

• A sequence of primes $$(p_1, p_2, p_3, p_4, \dots )$$ is constructible from $$S_{T(x)}$$ if the following:
• the first element $$c$$ in the sequence can be any prime such that $$c \in T(x)$$
• the next element $$n$$ can be any prime where the ordered pair $$(c,n) \in S_{T(x)}$$
• the sequence consists of $$2$$ or more elements where for each $$(p_i,p_{i+1})$$, it follows that $$(p_i,p_{i+1}) \in S_{T(x)}$$ and for each $$(\dots,p_j,p_{j+1}. \dots)$$, it follows that $$(p_j,p_{j+1},\dots) \in S_{T(x)}$$
• The set $$S_{T(x)}$$ is said to have repeats if a sequence is constructible that includes a prime more than once.

Example 1: $$x=16, T(x)=\{3,5,7,11,13\}, S_{T(x)} = \{ (5,3), (7,5), (11,3), (13,7) \}$$

In this example, $$S_{T(x)}$$ does not have repeats

Example 2: $$x=31, T(x)=\{3,5,7,11,13,17,19,23,29\}, S_{T(x)} = \{ (3,23), (5,3), (5,7), (7,5), (11,3), (13, 11), (17,3), (17,5), (17,13), (19,7), (23,3), (23,17), (23,19), (29,3) \}$$

In this example, $$S_{T(x)}$$ has repeats since the sequence $$(3,23,3)$$ is constructible from $$S_{T(x)}$$.

Claim: If a counter example exists to Legendre's Conjecture for a given $$x$$, the set of ordered pairs $$S_{T(x)}$$ will necessarily have repeats.

(1) Assume that for each $$p \in T(x)$$, there exists a $$q \in T(X)$$ such that $$(p,q) \in S_{T(X)}$$ [If this were not true, $$x^2 + x - p$$ would necessarily be a prime.]

(2) Let $$n = |T(x)|$$ be the number of elements in $$T(x)$$.

(3) We can arbitrarily order each $$p \in T(x)$$ up to $$p_{n-1}$$ in the following way:

• $$p_1 =$$ the least prime in $$T(x)$$.
• For each prime $$p_i$$, let $$p_{i+1}$$ be any prime where $$(p_i,p_{i+1}) \in S_{T(x)}$$ and $$p_{i+1}$$ has not yet been assigned an order. [If it has already been assigned an order, then we have a repeat]
• Assume that we do not run out of primes (otherwise, we have reached a repeat and the argument is proven)

(4) At $$p_n$$, there is no remaining unordered primes. Since, by assumption, there exists $$p_i \in T(x)$$ such that $$(p_n,p_i) \in S_{T(x)}$$, it follows that there must be a repeat.

Does this argument hold?

Thanks.

Edit:

Great comment from John Omielan. I have made changes to make the question less confusing.

• Added a definition for $$x$$
• Removed $$2$$ from examples since $$2 | x^2 + x$$ so it will never be an element of $$T(x)$$.
• Changed $$p_1$$ to $$p_4$$ in the definition of constructible to avoid any confusion.
• Add a specific $$x$$ value for the first example
• Removed some redundancies in the definition of $$S_{T(x)}$$
• Modified the title to make my question clearer.
• Updated Example 2 to make it complete
• Updated the third point in definition of constructible
• Your question text is now considerably better. In particular, your examples are consistent with your definitions, although I have a few suggestions in my answer below. Also, with your definition for $S_{T(x)}$, the first point of $p_i \neq p_j$ is redundant since, otherwise, the second point would give $x^2 + x - p_i \equiv 0 \pmod{p_i}$, which means $p_i \mid x^2 + x$, which is not allowed due to the third point. Nonetheless, you may wish to leave the first point is you wish to emphasize the values can't be equal. In my answer below, I also explain some issues I have with your Definitions. – John Omielan Jun 8 at 0:46
• Thanks, John! I will update the question to make it as clear as possible and respond to your comment in detail later today. – Larry Freeman Jun 9 at 20:52

In your Definitions: section, you wrote:

• A sequence of primes $$(p_1, p_2, p_3, p_4, \dots )$$ is constructible from $$S_{T(x)}$$ if the following:
• the first element $$c$$ in the sequence can be any prime such that $$c \in T(x)$$
• the next element $$n$$ can be any prime where the ordered pair $$(c,n) \in S_{T(x)}$$
• the sequence consists of $$1$$ or more elements where the first element in the sequence meets the first condition and all other elements meet the second condition.

I found this quite confusing. Your third point states the sequence consists of $$1$$ or more elements. However, your second point requires there to be at least $$2$$ elements. Also, the last part of the third point says "all other elements meet the second condition". However, the second condition uses $$c$$, which is defined in the first condition for the first element. This seems to imply all of the other elements, say $$p_i$$, must have $$(p_1,p_i) \in S_{T(x)}$$. However, your second example stating $$(3,23,3)$$ is constructible shows this is not the case.

Instead, from the context used later in your Claim, it seems the definition can be just simply stated as:

• A sequence of $$n \ge 2$$ primes $$(p_1, p_2, p_3, \dots, p_n)$$ is constructible from $$S_{T(x)}$$ if $$(p_i, p_{i+1}) \in S_{T(x)} \; \forall \; 1 \le i \le n - 1$$.

Assuming this is what you mean, then regarding your Claim, any counter-example to Legendre's conjecture would not have any prime $$p_L$$ where $$x^2 \lt p_L \lt x^2 + x$$, although the claim itself is for $$x^2 \lt p_L \lt x^2 + 2x + 1$$. As such, your first part $$(1)$$ must hold since, as you state, otherwise if it did not, then $$p_L = x^2 + x - p$$ must be a prime. This is because if it were composite, it would have at least $$2$$ factors, with the smaller one being less than $$x$$. Any prime factor of this smaller factor can't divide $$x^2 + x$$ (if it did, then it must also divide $$p$$), so it must be in $$T(x)$$.

The rest of your Claim only depends on your part $$(1)$$ since, using it, you can create an unlimited length chain of primes in multiple ways (the rest of your claim gives one method, although note $$p_1$$ can actually be chosen to be any prime, not necessarily the smallest one) that, since there are only a finite number of primes in $$T(x)$$, must eventually repeat.

In conclusion, your stated Claim is true.

• John, great points! I struggled to make the definition clear and precise and missed the ambiguities and incompleteness that you raised. Excellent. It has led me to a clearer understanding of my question! It has also shown me that my Example 2 is more interesting than I had previously realized. Thanks very much for your comments! – Larry Freeman Jun 12 at 15:44