Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I want to calculate wether $\exists x : x^2 \equiv 123 \mod 11\cdot 13$ or not. I do know that in terms of the legendre symbol follows that $\neg(\exists x: x^2 \equiv 123 \mod 11)$ and $\neg(\exists x: x^2 \equiv 123 \mod 13)$. How can i deduce from that, that $\neg(\exists x: x^2 \equiv 123 \mod 11 \cdot 13)$ ? The intention is that the values of the legende-symbol and the jacobi-symbol do not have to be equal.

share|cite|improve this question
Note that $x^2 = 123 + 11\cdot 13k = 123 + 11(13k)$. – M.B. Nov 15 '12 at 11:44
So assume that $x^2 = 123 + 11(13k)$. Then say $\alpha:= 13k$ and i have $x^2 = 123 + 11\alpha$. But I know $\neg(\exists x \exists \beta: x^2 = 123 + 11 \beta)$ so a contradiction follows ? – Epsilon Nov 15 '12 at 11:50
Yes. If $x^2 = 123 + (11\cdot 13)k$ then $x^2 = 123 + 11(13k) = 11k^\prime$ or $x^2 \equiv 123 \pmod{11}$. Contradiction. – M.B. Nov 15 '12 at 11:53
@André Your last sentence puzzles me: the Jacobi symbol extends the Legendre symbol, so they agree whenever both are defined. I think what you're trying to say is that the Jacobi symbol can't be relied upon to identify quadratic residues modulo composite bases. – David Loeffler Nov 15 '12 at 14:09

Assume there exists $x$ such that $x^2 \equiv 123 \pmod{11\cdot 13}$. Then, by definition, $$x^2 = 123 + 11\cdot 13\cdot k = 123 + 11(13k)$$ which implies that $x^2 \equiv 123 \pmod{11}$. Contradiction.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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