# Method to find smallest value of $x$ in $x^2-x+C$ to receive non-primes

$\textit{Problem statement}$: Given the function $f(x)=x^2-x+C$, where $x$ is a positive integer $>1$ and $C$ is a positive integer ($C=0$ is also allowed), find some method and/or set of rules to always find the smallest value of $x$ that will give a non-prime number for the function $x^2-x+C$.

To show the research that has been formulated so far, I have denoted these set of rules for the problem:

• If $C$ is an even number, the smallest $x$ value for a non-prime is $2$ because the function will always give a non-prime when $C$ is even.
• $x^2-x+C=x(x-1)+C$, this shows $x^2-x$ is always divisible by at least $x$.
• If $x=C$, then $x$ will result in a non-prime but isn't always the smallest non-prime.

The last bullet point here provides an initial method for when C is odd - it allows one to narrow their search for smallest values down to $C \geq x\geq 2$. Lastly, here are a few that have been completed for example:

• When $C=3$ the smallest $x$ for $f(x)$ that gives a non-prime is $3$
• When $C=5$ the smallest $x$ for $f(x)$ that gives a non-prime is $5$
• When $C=7$ the smallest $x$ for $f(x)$ that gives a non-prime is $2$
• When $C=9$ the smallest $x$ for $f(x)$ that gives a non-prime is $3$
• When $C=11$ the smallest $x$ for $f(x)$ that gives a non-prime is $11$
• When $C=13$ the smallest $x$ for $f(x)$ that gives a non-prime is $2$
• When $C=15$ the smallest $x$ for $f(x)$ that gives a non-prime is $3$
• When $C=1$ the smallest $x$ for $f(x)$ that gives a non-prime is $1$
• When $C=0$ the smallest $x$ for $f(x)$ that gives a non-prime is $2$
• You seem to assume that $C$ is positive in your bounds $2\leq x\leq C$... – Servaes Jun 4 '16 at 20:04
• @Servaes Have edited the post, thank you for the comment. Minor error on my part. – Colbi Jun 4 '16 at 20:05
• I don't quite understand; are there restrictions on $C$? Does it need to be at least $2$? – Servaes Jun 4 '16 at 20:07
• @Servaes The only restrictions on $C$ are that it has to be a positive integer, $C=0$ is also allowed. – Colbi Jun 4 '16 at 20:37

If $C$ is even then $f(2)$ is not prime, and if $C=1$ then $f(4)$ is not prime. So suppose $C>2$.
Let $p$ be the smallest prime dividing $C$. Then $p$ also divides $f(p)$, so $f(p)$ is not prime unless $f(p)=p$. But this is the case if and only if $C=p(2-p)$, which is impossible as $C$ is positive. Hence $2\leq x\leq p$.
Alternatively, as $f(x)>1$ and $f(x)$ is increasing for $C>2$, you could try to find the smallest composite $D>C$ for which $$x^2-x+(C-D)=0,$$ has integer roots. This is the case if and only if the discriminant is an integer square, that is, if and only if $1+4(D-C)$ is a square. So look for the least composite $D>C$ for which $1+4(D-C)$ is a square.
• Can you clarify some sort of method that would allow one to look for the least composite $D>C$? If $C$ becomes a large positive integer, let's say $189$, then I imagine that just guessing numbers will make it hard to find some number for which $1+4(D-C)$ is a square. – Colbi Jun 4 '16 at 21:30
• Do note that it could be easier to keep a list of values $k$ for which $1+4k$ is square. It starts with $k=2,6,12,20,30,\ldots$. Then you can check whether $C+k$ is composite for these $k$. But this is precisely brute-forcing the original problem. – Servaes Jun 4 '16 at 21:34