# Quadratic reciprocity - legendre symbol $\neq$ jacobi symbol

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.

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