Finding the Minimum $x$ for a Prime Product

[anemone]

Find the minimum value for $x$ where $x\in \mathbb{N} $ and $x^2-x+11$ can be written as a product of 4 primes, which are not necessarily distinct.

 

[Opalg]

Spoiler: Hint

The key question to ask is: which primes can occur as factors of $N = x^2 - x + 11$, where $x$ is an integer?

Spoiler: Solution

If $x$ is an integer then either $x$ or $x-1$ is even, so $x^2-x = x(x-1)$ is always even and therefore $N = x^2 - x + 11$ is always odd. Thus the prime $2$ can never be a divisor of $N$.

Can the prime $3$ occur as a divisor of $N$? If so then (working mod $3$) $$0 \equiv x^2 - x + 11 \equiv x^2 + 2x + 2 \equiv (x+1)^2 + 1 \pmod3.$$ Therefore $(x+1)^2 \equiv -1\equiv 2 \pmod3$. But that equation has no solutions. In the language of number theory, $2$ is not a quadratic residue mod $3$. Therefore $3$ can never be a prime factor of $N$.

Can the prime $5$ occur as a divisor of $N$? If so then $0 \equiv x^2 - x + 11 \equiv x^2 + 4x + 1 \equiv (x+2)^2 + 2 \pmod5$. Therefore $(x+2)^2\equiv -2\equiv3 \pmod5$. But $3$ is not a quadratic residue mod $5$. Therefore $5$ can never be a prime factor of $N$.

Can the prime $7$ occur as a divisor of $N$? If so, then $0 \equiv x^2 - x + 11 \equiv x^2 + 6x + 4 \equiv (x+3)^2 + 2 \pmod7$. Therefore $(x+3)^2\equiv -2\equiv5 \pmod7$. But $3$ is not a quadratic residue mod $7$. Therefore $7$ can never be a prime factor of $N$.

But the prime $11$ can occur as a divisor of $N$. So can the prime $13$. So the smallest possible candidate for $N$ to be a product of four primes would be if $N = 11^4 = 14641$. However, if $x = 121$ then $x^2 - x + 11 = 121*120 + 11 = 14531 < 14641$, but if $x = 122$ then $x^2 - x + 11 = 122*121 + 11 = 14773 > 14641$. So $11^4$ falls between two values of $x^2 - x + 11$ and therefore does not give a solution to the problem.

The next smallest possible candidate for $N$ is $11^3*13 = 17303$. This time we strike lucky, because if $x=132$ then $x^2 - x + 11 = 132*131 + 11 = 17303$. So the minimum value for $x$ such that $x^2 - x + 11$ is a product of four primes is $x = 132$, and the primes are then $11,11,11,13$.