Smallest $x$ that allows for division by $y$ Assume we know $y$ which is prime of form $6k+1$ (may not be relevant). I want a simplified way to find the smallest positive $x$ where $y$ divides $x^2-x+1$. Is there a better way than just testing $x=1, 2, 3$ etc?
 A: What you are looking for is a value of $x$ that satisfies
$$
x^2-x+1 \equiv 0 \mod 6k+1
$$
where $6k+1$ is a prime number. Now, we can complete the square to get
$$
\left(x-\frac12\right)^2 = x^2-x+\frac14\equiv -\frac34 \mod 6k+1
$$
So there can only be a solution if $-3$ is a quadratic residue mod $6k+1$. As it happens, for all primes of that form, $-3$ is a quadratic residue.
Now, you can use any of the modular square root algorithms, like Tonelli-Shanks, to find $\sqrt{-3}$. If $m\equiv \sqrt{-3}$, then you have
$$
x \equiv \frac{m+1}2 \mod 6k+1
$$
Now, let's look at an example of using this. Consider the case of $k=10$, so $y=61$, a prime. You're looking for solutions to
$$
m^2 \equiv -3 \mod 61
$$
Generally, you'd use Tonelli-Shanks or another modular square root algorithm, but I'll skip those details - the two solutions are $m\equiv27$ and $m\equiv34$.
Now, we have $x\equiv 14$ and $x\equiv \frac{35}{2} \equiv 48$.
So our smallest $x$ such that $x^2-x+1|y$ is $x=14$. $14^2-14+1 = 183 = 3\cdot 61$.
