prove that x^2 congruent c mod p^n has solution if and only if (c/p)=1;
find all primes p such that (10/p)=1;
One direction is obvious. We will show that if has a solution then has a solution. Let satisfy . We want to find an so that would satisfy i.e. . We can write this as ( this is because divides ). Finally since this congruence is solvable for . And we found our solution.
Therefore we will assume it is any other prime.
Notice that .
Therefore for it means two things: (i) (ii) .
We know that iff and iff .
We will not find those primes so that .
Note that and by quadradic reciprocity it means .
Thus, iff - for those are the squares mod .
Therefore, iff and iff .
Therefore, (and ) precisely if any eight of the conditions are satisfies:
Using the Chinese remainder theorem we get:
Thus, needs to have the form .