7
$\begingroup$

Find the solutions of $x^2\equiv -1\pmod{5}$ and $x^2\equiv -1\pmod{13}$

I know that they are both soluble since $5\equiv 1\pmod{4}$ and $13\equiv 1\pmod{4}$

What is the method to solving this simultaneous equation.

Looking for a standard method to use with this type of problem.

$\endgroup$
  • 4
    $\begingroup$ Solve the sub-problems, and combine with the Chinese remainder theorem. $\endgroup$ – Daniel Fischer Feb 23 '15 at 11:48
  • 1
    $\begingroup$ And you can solve the subproblems by seeing whether $1$ is a solution, whether $2$ is a solution, whether $3$ is a solution, and so on. $\endgroup$ – Gerry Myerson Feb 23 '15 at 12:23
  • $\begingroup$ The Chinese remainder theorem is crucial to this problem and many like it. $\endgroup$ – Robert Soupe Feb 23 '15 at 14:29
4
$\begingroup$

Hint: $x^2 \equiv -1$ mod $5$ $\iff$ $x^2 \equiv 4$ mod $5$ $\iff$ $(x-2)(x+2) \equiv 0$ mod $5$, whence $x \equiv 2$ or $x \equiv -2$ mod $5$.

$x^2 \equiv -1$ mod $13$ $\iff$ $x^2 \equiv 25$ mod $13$ $\iff$ $(x-5)(x+5) \equiv 0$ mod $13$, whence $x \equiv 5$ or $x \equiv -5$ mod $13$.

Now cross-solve these $4$ possibilities with the Chinese Remainder Theorem.

Example: if $x \equiv 2$ mod $5$ and $x \equiv 5$ mod $13$, this should give you $x \equiv 57$ mod $65$

$\endgroup$
  • $\begingroup$ Why -i is not solution? $\endgroup$ – Poutrathor Feb 23 '15 at 13:15
  • $\begingroup$ Because this is about integers and not complex numbers, see the tags. $\endgroup$ – Nicky Hekster Feb 23 '15 at 13:16
  • $\begingroup$ Oooo but could we solve it in C? $\endgroup$ – Poutrathor Feb 23 '15 at 13:17
  • $\begingroup$ Then one should clarify what you mean by mod $5$ or mod $13$. This can be done, but then we are talking algebraic number theory in $\mathbb{Z}[i]$ which is not elementary number theory as meant by the OP. $\endgroup$ – Nicky Hekster Feb 23 '15 at 13:20
1
$\begingroup$

by Wilson's theorem, for prime $p$: $$ (p-1)! \equiv_p -1 $$ if $p \equiv_4 1$ then $p-1 = 4n$ and $$ (p-1)! = \prod_{k=1}^{2n} k \prod_{k=2n+1}^{4n} k =\prod_{k=1}^{2n} k\prod_{k=1}^{2n}(p- k) \equiv_p (-1)^{2n} \left( \prod_{k=1}^{2n} k \right)^2 = ((2n)!)^2 $$ i.e. $$ \left( \left(\frac{p-1}2 \right)! \right)^2 \equiv_p -1 $$ so $(2!)^2 \equiv_5 -1$ and $(6!)^2 \equiv_{13} -1$, with $6! = 720 \equiv_{13} 720-650-65=5$

since, for any $m$ we have $j^2 \equiv_m (m-j)^2$ the square roots of $-1 \mod 5$ are $2,3$ and the square roots of $-1 \mod 13$ are $5,8$

$\endgroup$
1
$\begingroup$

Hint $\ $ By CRT the square roots mod $5$ and $13$ lift to $4$ square roots mod $65$. There is an obvious square root $\,{\rm mod}\ 65\!:\ x^2\equiv -1\equiv 64\,$ if $\,x\equiv \pm8\equiv \pm (2,5)\pmod {5,13}$. The other pair $\pm (-2,5),\,$ arise by multiplying the first pair by $\,(-1,1)\equiv 14,\,$ i.e. $\,\pm 8\cdot 14\equiv \pm18\pmod{65}.\ $ QED

$\endgroup$

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.