Q:

Let P and Q be integers such that P is odd, and gcd(P,Q)=1. Consider the congruence equation $X^2 \equiv Q \mod P$. Prove that

Let P and Q be integers such that P is odd, and gcd(P,Q)=1. Consider the congruence equation $X^2 \equiv Q \mod P$. Prove that

If the equation has a solution, then $(\frac{Q}{P})=1$
That the coverse is not true.

I just want help with the first part I am not sure how to approach the problem. I believe that it has to deal with Jacobi symbol. But I am not sure.

A:

Yes, it has to do with the Jacobi symbol. If we interpret $(Q/P)$ as a Legendre symbol (meaning in particular that $P$ is an odd prime) then the result is basically the definition of the Legendre symbol. 

Write $P$ as $p_1p_2\cdots p_m$ where the $p_i$ are primes, not necessarily distinct. 
Then the Jacobi symbol $(Q/P)$ is defined by
$$(Q/P)=(Q/p_1)(Q/p_2)\cdots (Q/p_m),$$
where the symbols on the right are Legendre symbols. 
If your congruence $x^2\equiv Q\pmod{P}$ has a solution, then it has solutions modulo all the $p_i$. So the Legendre symbols on the right are all $1$. The result follows. 
Remark: Since you explicitly asked for a solution only for the first part, we do not give an example to show that the implication in the other direction does not hold. 

