# Prove that $\forall x\in\mathbb{N}\ \text{ there always exists a prime }p\equiv1 \pmod 6 \text{ s.t. }p|(2x)^2+3;$

I want to prove the following:

$$\forall x\in\mathbb{N}\ \text{ there always exists a prime }p\equiv1 \pmod 6 \text{ s.t. }p|(2x)^2+3;$$$$\ \text{i.e. } (2x)^2\equiv-3 \pmod p$$ where $$p$$ is some prime sufficing $$p\equiv1 \pmod 6$$ has to be true for all $$x\in\mathbb{N}$$.

I want to represent $$2x$$ as a product of 2 and primes $$p_i$$ of the form $$6k_i+1$$; i.e. $$p_i\equiv1(\mod 6)$$ and $$2x=2\prod_{i=1}^{n}p_i$$. Note that $$x\in\mathbb{N}$$ is chosen arbitrarily beforehand. Is this even possible?

What I've tried so far: I've prove with the Legendre symbol that $$\big(\frac{-3}{p}\big)=1$$ when $$p\equiv1(\mod6)$$ which clarifies the existence of an element $$y\in\mathbb{Z}/(p)$$ s.t. $$y^2\equiv-3(\mod p)$$. But since I want to show that it holds for all $$y=2x$$ where $$x$$ is chosen, this is useless i.m.o..

So maybe brainless trial and error will get me somewhere:

$$x=1$$: $$2^2+3\equiv0(\mod p)$$ where we choose $$p=7\equiv1(\mod6)$$ prime.

$$x=2$$: $$4^2+3=19\equiv0(\mod p)$$ where we choose $$p=19\equiv1(\mod6)$$ prime.

...

$$x=a$$: $$4a^2+3\equiv0(\mod p)$$ for some $$p\equiv1(\mod6)$$ iff (?) $$4a^2+3\equiv1(\mod6)$$.

I also was considering $$\big(\frac{-3\cdot4^{-1}}{p}\big)$$, but this is difficult to compute since we don't know the inverse of 4 explicitly modulo $$p$$. Of course there's an algorithm for it, but I doubt it will bring succes in computing the Legendre symbol.

Still, $$x\in\mathbb{N}$$ is fixed, hence we cannot just manipulate $$x$$. Clearly, I'm stuck. Could anyone get me on the right track? All help is appreciated!

EDIT:

First title that is now deleted: For every $$x\in\mathbb{N}$$ write $$2x=2\prod_{i=1}^{n}p_i$$ with $$p_i=6k_i+1$$ primes

• "Is this even possible?" What about $2x=10$? – Winther Oct 15 '18 at 21:16
• Right now the title is different from the "I want to prove the following" statement. I suggest putting the real problem statement in the title. It's good you add what you have tried, but try to make the question about the problem you are solving not about your attempt. – Winther Oct 15 '18 at 21:18
• Part of your question asks about primes dividing $(2x)^2+3$ being $1$ mod $6$. I have answered what I think that is asking about. Another part asks about primes dividing $2x$ being $1$ mod $6$. I don't understand what that part is asking since $x$ is allowed to be anything in $\mathbb{N}$. – alex.jordan Oct 16 '18 at 1:15
• $x$b is any member of $\Bbb N$. So you can't generally express $2x$ as twice the product of primes that are each $\equiv 1 \mod 6.$ E.g, if $x=5$ – DanielWainfleet Oct 16 '18 at 1:29
• @Winther "Is this even possible?" in the sense of could there possibly be a counter example. Thanks for the tips. – Algebear Oct 16 '18 at 10:11

In fact something stronger is true. All of the prime divisors of $$(2x)^2+3$$ ($$x\in\mathbb{N}$$) are either equal to $$3$$ or are congruent to $$1$$ mod $$6$$. (And then since they can't all be equal to $$3$$, there is always some prime divisor congruent to $$1$$ mod $$6$$.)

Suppose $$p$$ is some odd prime dividing $$(2x)^2+3$$. Note that either $$p=3$$, or $$p\equiv1$$ or $$p\equiv5$$ mod $$6$$. Assume that $$p\equiv5$$ mod $$6$$. Then $$(2x)^2\equiv-3\mod{p}$$ So $$-3$$ is a square mod $$p$$. So using Legendre symbols and quadratic reciprocity:\begin{align} 1&=\left(\frac{-3}{p}\right)\\ &=\left(\frac{-1}{p}\right)\left(\frac{3}{p}\right)\\ &=\left(\frac{-1}{p}\right)\left(\frac{p}{3}\right)(-1)^{(p-1)(3-1)/4}\\ &=\left(\frac{-1}{p}\right)\left(\frac{p}{3}\right)(-1)^{(p-1)/2}\end{align} Since $$p\equiv5$$ mod $$6$$, then $$p\equiv2$$ mod $$3$$. So $$p$$ is not a square mod $$3$$. So continuing: $$1=\left(\frac{-1}{p}\right)(-1)^{(p+1)/2}$$

It is "well-known" that $$-1$$ is a quadratic residue mod $$p$$ if and only if $$p$$ is congruent to $$1$$ mod $$4$$. So if $$p$$ is congruent to $$1$$ mod $$4$$, the above says: $$1=(1)(-1)$$ and if $$p$$ is not congruent to $$1$$ mod $$4$$, the above says: $$1=(-1)(1)$$

So it is a contradiction either way. We conclude that all primes dividing $$(2x)^2+3$$ are either equal to $$3$$ or are $$1$$ mod $$6$$. There is the possibility that $$(2x)^2+3$$ is a power of $$3$$, but we can eliminate that easily. Mod $$9$$, $$6$$ is not a square. So $$(2x)^2+3\not\equiv0$$ mod $$9$$ no matter what $$x$$ is. So $$(2x)^2+3$$ is sometimes divisible by $$3$$ but never divisible by $$9$$.

So $$(2x)^2+3$$ is always the product of some primes that are congruent to $$1$$ mod $$6$$, sometimes with a single factor of $$3$$ thrown in the mix. But $$(2x)^2+3$$ always has prime factors congruent to $$1$$ mod $$6$$.

• Thank you. I actually wanted the statement to be like you stated it, so thanks for the feedback. Most of what you're doing is very clear to me. Reading the very last two paragraphs, I suppose you mean that since $2x^2+3$ is never divisible by 9, but it can sometimes be divisible by 3. Since $3\not\equiv1(\mod6)$, how can we say that there still exists a prime $p\equiv1(\mod6)$ that divides this? – Algebear Oct 16 '18 at 10:43
• Suppose $x=3^ky$ for some $0<k\in\mathbb{Z}$ and $3\nmid y$. Then we have that $(2x)^2+3=4\cdot3^{2k}y^2+3=3(4y^2 3^{2k-1}+1)$. So we must have that $p|4y^2 3^{2k-1}+1$ where $p\equiv1(\mod6),\ 3\nmid y$ and $k\in\mathbb{N}$. How is that always possible? So actually, we must have that $6|4y^2 3^{2k-1}$ and we have that $k>0$; hence we have that $6|4\cdot 3^{2k-1},\ \forall k>0$. I've now answered my own question I think. Thank you for you time! – Algebear Oct 16 '18 at 10:58
• With my last comment above we don't need the part where you state that $(2x)^2+3$ is not divisible by 9, am I right? – Algebear Oct 16 '18 at 12:36
• A priori, the primes dividing $(2x)^2+3$ are either (a) equal to $3$ (b) congruent to $1$ mod $6$, or (c) congruent to $5$ mod $6$. Most of the argument eliminates (c) as an option. If somehow there were also no divisors of type (b), then $(2x)^2+3$ would have to be a power of $3$. My goal is to rule that out, but to me it feels easier to rule out something "bigger". I rule out that $9$ will not divide $(2x)^2+3$. This implies $(2x)^2+3$ is not a power of $3$. – alex.jordan Oct 16 '18 at 17:59
• Suppose that $9$ divides $(2x)^2+3$. Then $(2x)^2+3\equiv0$ mod $9$. So $(2x)^2\equiv6$ mod $9$. But this is where it comes in that $6$ is not a quadratic residue mod $9$. All this leaves you knowing a lot about how $(2x)^2+3$ factors. It is built from one or more primes that are $1$ mod $6$. And then there might be a single factor of $3$. And that is it. – alex.jordan Oct 16 '18 at 17:59