I read online that even when Jacobi's Symbol is 1, it doesn't necessary means that it's legendre Symbol is 1: $$\left(\frac 2 {15}\right) = \left(\frac 2 3\right)\left(\frac 2 5\right) =-1*-1 = 1$$ and 2 is not quadratic residue of 15, I have following 2 questions

  1. can I prove this with this logic: if $x^2 \equiv a \pmod n$, then $x^2 \equiv a \pmod p$ where p is a prime factor of n, which should also prove the following using contrapositive?

    if jacob's symbol is -1, legendre symbol is also -1

  2. If Jacobi's symbol is 1 and all of its decomposition(legendre symbol) are also 1, can we prove that the legendre symbol is also 1? ie if u,v is the prime factorization of odd number b, and we know a is a quadratic residue of u and v:$$\left(\frac ab\right) = \left(\frac au\right) \left(\frac av\right) = 1*1 = 1$$ can we say that a is a quadratic residue of b? maybe use chinese remainder theorem but I couldn't figure out a proof...


1) Sure, if $p$ divides $n$ and $n$ divides $x^2-a$ then $p$ divides $x^2-a$.

2) We use the ordinary convention that the Jacobi symbol $(a/n)$ is only defined when $n$ is odd. Let $n=p_1^{a_1}\cdots p_k^{a_k}$ where the $p_i$ are distinct odd primes.

Suppose now that each of the Legendre symbols $(a/p_i)$ is equal to $1$, where $a$ is relatively prime to all the $p_i$. Then the congruence $x^2\equiv a\pmod{p_i}$ has a solution, which can be lifted to a solution of $x^2\equiv a\pmod{p_i^{a_i}}$. Let $x_i$ be a solution of this congruence.

By the Chinese Remainder Theorem, there is an $x$ such that $x\equiv x_i\pmod{p_i^{a_i}}$ for all $i$. Any such $x$ is a solution of $x^2\equiv a\pmod{n}$.

  • $\begingroup$ you lost me on the last sentence, I understand that $x \equiv x_i \pmod {p_i}$, but chinese remainder theorem gives that such x is of the form $$x \equiv \sum x_ib_ic_i \pmod n$$ $$b_i = n/p_i$$ $$c_i \equiv b_i^{-1} \pmod {p_i}$$, and I try square both side...but that looks like a lot of calculation, how did you get $x^2 \equiv a \pmod n$ $\endgroup$ – watashiSHUN Oct 29 '15 at 20:13
  • $\begingroup$ Don't worry about the mechanics of how we produce $x$. We have $x\equiv x_i\pmod{p_1^{a_i}}$. So $x^2\equiv x_i^2$ (same modulus, pain to type). If $x_i^2\equiv a$ (same modulus) then $x^2\equiv a$ (same modulus). Since $x^2\equiv a \pmod{p_i^{a_i}}$ for all $i$, it follows that $x^2\equiv a\pmod{n}$. $\endgroup$ – André Nicolas Oct 29 '15 at 20:19

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.