Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

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

1 Answer 1

up vote 2 down vote accepted

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

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.