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)$.
This seems a dead end.
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
Best Answer
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$.