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.

  • 3
    $\begingroup$ Solve it modulo $5$, $13$ and $31$, and then apply the Chinese remainder theorem. $\endgroup$ – Dietrich Burde Feb 6 '16 at 14:55
  • 1
    $\begingroup$ $(2x+1)^2 \equiv 1 \pmod{2015}$ $\endgroup$ – Daniel Fischer Feb 6 '16 at 15:01
  • $\begingroup$ @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$. $\endgroup$ – David Feb 6 '16 at 15:15
  • $\begingroup$ 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$. $\endgroup$ – Dietrich Burde Feb 6 '16 at 15:21
  • $\begingroup$ 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? $\endgroup$ – 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}$$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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