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;
We will work with an odd prime.
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.
Of course because otherwise .
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:
1) and
2) and
3) and
4) and
5) and
6) and
7) and
8) and
Using the Chinese remainder theorem we get:
1)
2)
3)
4)
5)
6)
7)
8)
Thus, needs to have the form .