# Solving $x^2 \equiv -x\pmod{2015}$

Problem: Find all integer solutions of $x^2 \equiv -x \pmod{2015}$.

I proceeded this way: first, I realized that $2015 = 5 \times 13 \times 31$. I rewrote $x^2 \equiv -x$ as $x^2 + x \equiv 0$.

Then, for each factor $d$, I have that $d\ |\ x(x+1)$, therefore $d\ |\ x$ or $d\ |\ x + 1$.

This gives eight cases:

• $3,13,31\ |\ x$
• $3,13\ |\ x\quad{\rm and}\quad 31\ |\ (x + 1)$
• etc.

Solving each case separately and taking union of the results gives correct results (the conditions are both necessary and sufficient), but it's really tedious.

I am sure someone can come up with a better approach.

• Solve it modulo $5$, $13$ and $31$, and then apply the Chinese remainder theorem. – Dietrich Burde Feb 6 '16 at 14:55
• $(2x+1)^2 \equiv 1 \pmod{2015}$ – Daniel Fischer Feb 6 '16 at 15:01
• @DietrichBurde Great, Chinese remainder theorem will give me range in which I can found the unique $x$ for which these properties hold; but how do I actually find it? (Sorry to be a nob.) For each case (modulo $5$, $13$, $31$), I still have two options: either it divides $x$ or $x + 1$. – David Feb 6 '16 at 15:15
• For modulo $5$, say, just test all possible numbers $0,1,2,3,4$ whether or not they satisfy $x^2+x\equiv 0 \bmod 5$. – Dietrich Burde Feb 6 '16 at 15:21
• Sure, I am doing that :). It's easy to find solutions to these individual subproblems, but the question is, how do I find the intersection of those solutions? – David Feb 6 '16 at 15:25

There's this general trick for solving quadratic congruences: if $\gcd(4a,n)=1$, then:

$$ax^2+bx+c\equiv 0\pmod{n}\stackrel{\cdot 4a}\iff (2ax+b)^2\equiv b^2-4ac\pmod{n}$$

In your case, $2015=5\cdot 13\cdot 31$ and:

$$x^2\equiv -x\pmod{2015}\iff (2x+1)^2\equiv 1\pmod{2015}$$

$$\iff \begin{cases}(2x+1)^2\equiv 1\pmod{5}\\(2x+1)^2\equiv 1\pmod{13}\\(2x+1)^2\equiv 1\pmod{31}\end{cases}$$

$$(2x+1)^2-1=((2x+1)+1)((2x+1)-1),$$ so by Euclid's Lemma:

$$\iff \begin{cases}2x+1\equiv \pm 1\pmod{5}\\2x+1\equiv \pm 1\pmod{13}\\2x+1\equiv \pm 1\pmod{31}\end{cases}$$

$$\iff \begin{cases}x\equiv \{-1,0\}\pmod{5}\\x\equiv \{-1,0\}\pmod{13}\\x\equiv \{-1,0\}\pmod{31}\end{cases}$$

By Chinese Remainder Theorem (CRT), this gives $8$ solutions mod $2015$.

E.g., if $x\equiv -1\pmod{5}$, $x\equiv -1\pmod{13}$, $x\equiv 0\pmod{31}$, then $x\equiv 1364\pmod{2015}$.

Etc. You should already know how to apply CRT. You'll get: $$x\equiv \{-1,0,155,650,805,1209,1364,1859\}\pmod{2015}$$