# 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?

-
Have you noticed that both solutions for $x$ are primitive sixth roots of unity? –  Hurkyl Apr 1 '13 at 3:41

## 1 Answer

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$.

-
I am sorry; I am not sure I quite understand. How does this help find the smallest x any faster than the current approach? –  Aruka J Apr 1 '13 at 3:37
Because you can use any of the modular square root algorithms, like Tonelli-Shanks, to compute the square root. –  Hurkyl Apr 1 '13 at 3:38
Seems to be for x^2 cases not x en.wikipedia.org/wiki/Tonelli%E2%80%93Shanks_algorithm –  Aruka J Apr 1 '13 at 3:39
Modular square root algorithms solve $x^2\equiv a$, which is useful, because you have $m^2\equiv -3$. –  Glen O Apr 1 '13 at 3:40
I am trying to find smallest x^2-x+1 that is divisible by (known) y –  Aruka J Apr 1 '13 at 3:41