5
$\begingroup$

I know that a similar question already exists, but I have a different question to ask.

We want to examine if $x^2 \equiv -1 \pmod{365}$ has a solution.

My thought is: $365=5\cdot 73$. So,The congruence $x^2 \equiv -1 \pmod{365}$ has solution, if and only if, the congrueces $x^2 \equiv -1 \pmod 5$ and $x^2 \equiv -1 \pmod{73}$ has solutions. So, if we use Legendre's Symbol we have

  • $x^2 \equiv -1 \pmod 5$ has solution $\iff (-1/5)=1 $ (and with simple calculations, indeed)
  • $x^2 \equiv -1 \pmod{71}$ has solution $\iff (-1/73)=1 $

Now, can we conclude that the congruence $x^2 \equiv -1 \pmod{365}$ has solution?

And more general: If we have the congruence $x^2 \equiv a \pmod n$ with $n=p_1^{n_1}\cdots p_k^{n_k},\ \gcd(a,n)=1$, which is equivalent with the system $x^2 \equiv a {\pmod p_1^{n_1}},\ldots,x^2 \equiv a \pmod{p_k^{n_k}}$, can we conclude that the first has solution if and only if each one of $x^2\equiv a\pmod{p_i^{n_i}},\ \forall i=1,\ldots,k$ has solution?

Thank you.

$\endgroup$
  • 2
    $\begingroup$ Change $71$ to $73$ and it's fine. $\endgroup$ – Robert Israel Feb 7 '17 at 16:12
  • $\begingroup$ @RobertIsrael Thank you for your comment and your correction. $\endgroup$ – Chris Feb 7 '17 at 16:15
  • $\begingroup$ Note the use of \pmod rather than \bmod in my edit to the question. $\endgroup$ – Michael Hardy Feb 7 '17 at 16:51
  • $\begingroup$ @RobertIsrael Ok, thank you $\endgroup$ – Chris Feb 7 '17 at 16:58
2
$\begingroup$

We show the following result:

Let $n,m$ be coprime integers. Let $a \in \Bbb Z$. Then $a$ is a square modulo $nm$ iff $a$ is square mod $n$ and $a$ is square mod $m$.

Assume that there are integers $x_i$ such that $x_1^2 \equiv a \pmod m$ and $x_2^2 \equiv a \pmod n$ where $m,n$ are coprime. We show that $y^2 \equiv a \pmod {nm}$ has a solution (the converse is obvious).

We know that there is an integer $y$ such that $y \equiv x_1 \pmod m$ and $y \equiv x_2 \pmod n$, by the Chinese remainder theorem.

Then $y^2-a$ is a multiple of $m$ and $n$, so it is a multiple of $nm$ since $(n,m)=1$. Therefore $y^2 \equiv a \pmod {nm}$.


More generally, we have the following theorem (see Ireland Rosen, p. 50)

Let $a,n \in \Bbb N$ be coprime integers. Write $n=2^e p_1^{e_1} \cdots p_k^{e_k}$ as product of distinct prime powers. Then $a$ is a square modulo $n$ if and only if

  • $a$ is a square modulo $p_i$ (for $1 \leq i \leq k$) ; this is equivalent to $a^{\dfrac{p_i-1}{2}} \equiv 1 \pmod{p_i}$

  • $e>1 \implies a \equiv 1 \pmod{2^{2+r}}$ where $r = 1$ if $e \geq 3$ and $r=0$ if $e=2$.

$\endgroup$
  • 1
    $\begingroup$ It might be worth explicitly mentioning the CRT here where it's used, but this is elsewise a good, clean answer. $\endgroup$ – Steven Stadnicki Feb 7 '17 at 16:20
  • $\begingroup$ Thank you , now it's clear. $\endgroup$ – Chris Feb 7 '17 at 16:27
  • 1
    $\begingroup$ @Chris : you're welcome. It is chapter 5 in Ireland, Rosen. $\endgroup$ – Watson Feb 7 '17 at 16:28
  • $\begingroup$ Tell me please something else. If we have the congruence $x^2 \equiv 2 \bmod 118$ could we say that $118=2\cdot 59$ so it's in the form of $2p^m$ and $2^{\phi(118)/ \gcd(2,\phi(118))} \equiv -1 \bmod 118$ so there are no solutions (because it is not a quadratic residue mod 118)? $\endgroup$ – Chris Feb 7 '17 at 16:46
  • 1
    $\begingroup$ @Chris : since $2$ is not a square mod $59$, it is not a square mod $118$, that's correct! $\endgroup$ – Watson Feb 7 '17 at 16:50
3
$\begingroup$

We have $365 = 5 \times 73$. The congruence becomes $x^2 = -1 \mod 5$ and $x^2 = -1 \mod 73$.

We have if $p = 1 \mod 4 \implies x^2 = -1 \mod p$ has exactly $2$ solutions.

Thus $x^2 = -1 \mod 5$ has solutions $x_0,x_1$ and $x^2 = -1 \mod 73$ has solutions $y_0,y_1$.

The original solutions satisfies either: $x = x_0 \mod 5, x = y_0 \mod 73$; $x = x_0 \mod 5, x = y_1 \mod 73$; $x = x_1 \mod 5, x = y_0 \mod 73$ ; $x = x_1 \mod 5, x = y_1 \mod 73$.

For each pair of congruence , $x$ is uniquely determined $\mod 365$ by the Chinese remainder theorem. Hence the original congruence has $4$ solutions.

$\endgroup$
3
$\begingroup$

If $\,m,n\,$ are coprime then, by CRT, solving an integer coefficient polynomial $\,f(x)\equiv 0\pmod{\!mn}\,$ is equivalent to solving $\,f(x)\equiv 0\,$ mod $\,m\,$ and mod $\,n.\,$ By CRT, each combination of a root $\,r_i\bmod m\,$ and a root $\,s_j\bmod n\,$ corresponds to a unique root $\,t_{ij}\bmod mn,\,$ i.e.

$$\begin{eqnarray} f(x)\equiv 0\!\!\!\pmod{mn}&\overset{\rm CRT}\iff& \begin{array}{}f(x)\equiv 0\pmod m\\f(x)\equiv 0\pmod n\end{array} \\ &\iff& \begin{array}{}x\equiv r_1,\ldots,r_k\pmod m\phantom{I^{I^{I^I}}}\\x\equiv s_1,\ldots,s_\ell\pmod n\end{array}\\ &\iff& \left\{ \begin{array}{}x\equiv r_i\pmod m\\x\equiv s_j\pmod n\end{array} \right\}_{\begin{array}{}1\le i\le k\\ 1\le j\le\ell\end{array}}^{\phantom{I^{I^{I^I}}}}\\ &\overset{\rm CRT}\iff& \left\{ x\equiv t_{i j}\!\!\pmod{mn} \right\}_{\begin{array}{}1\le i\le k\\ 1\le j\le\ell\end{array}}\\ \end{eqnarray}\qquad\qquad$$

$\endgroup$
2
$\begingroup$

Yes. Let a solution to $x^2+1 \equiv 0 \pmod {5}$ be $r_{1}$, and let a solution to $x^2+1 \equiv 0 \pmod {73}$ be $r_{2}$

Then note that by CRT, we have that there exists such $x$ that $$x \equiv r_{1} \pmod {5}$$ $$x \equiv r_{2} \pmod {73}$$ Exists. Then note that for such $x$, $$x^2+1 \equiv 0 \pmod {5}$$ $$x^2+1 \equiv 0 \pmod {73}$$ Which gives $$x^2+1 \equiv 0 \pmod {365}$$

$\endgroup$
  • $\begingroup$ Seems alright now. $\endgroup$ – Wojowu Feb 7 '17 at 16:20
2
$\begingroup$

It is true because of the Chinese remainder theorem, which asserts the map \begin{align} \mathbf Z/n\mathbf Z&\longrightarrow \mathbf Z/p_1^{n_1}\mathbf Z\times\dotsm\times\mathbf Z/p_k^{n_k}\mathbf Z\\ x\bmod n&\longmapsto(x\bmod p_1^{n_1},\dots,x\bmod p_k^{n_k}) \end{align} is a ring isomorphism.

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