# Thread: x^2 congruent c mod p^n has solution of(c/p)=1

1. ## x^2 congruent c mod p^n has solution of(c/p)=1

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;

2. Originally Posted by vinodannu
prove that x^2 congruent c mod p^n has solution if and only if (c/p)=1;
We will work with $p$ an odd prime.

One direction is obvious. We will show that if $x^2 \equiv c (\bmod p^n)$ has a solution then $x^2 \equiv c (\bmod p^{n+1})$ has a solution. Let $x_1$ satisfy $x_1^2 \equiv c(\bmod p^n)$. We want to find an $a$ so that $x_1+ap^n$ would satisfy $x^2 \equiv c(\bmod p^{n+1})$ i.e. $x_1^2 + 2ax_1p^n \equiv c (\bmod p^{n+1})$. We can write this as $2ax_1 \equiv ( c - x_1^2)/p^n (\bmod p^{n+1})$ ( this is because $p^n$ divides $c-x_1^2$). Finally since $\gcd(2x_1,p^{n+1}) = 1$ this congruence is solvable for $a$. And we found our solution.

3. Originally Posted by vinodannu
find all primes p such that (10/p)=1
Of course $p\not = 2,5$ because otherwise $(10/p)=0$.
Therefore we will assume it is any other prime.

Notice that $(10/p) = (2/p)(5/p)$.
Therefore for $(10/p)=1$ it means two things: (i) $(2/p)=(5/p)=1$ (ii) $(2/p)=(5/p)=-1$.

We know that $(2/p) = 1$ iff $p=8k\pm 1$ and $(2/p)=-1$ iff $p=8k\pm 3$.

We will not find those primes so that $(5/p)=1$.
Note that $5\equiv 1(\bmod 4)$ and by quadradic reciprocity it means $(5/p)=(p/5)$ .
Thus, $(p/5)=1$ iff $p\equiv \pm 1(\bmod 5)$ - for those are the squares mod $5$.
Therefore, $(5/p)=1$ iff $p=5k\pm 1$ and $(5/p)=-1$ iff $p=5k\pm 2$.

Therefore, $(10/p)=1$ (and $p\not =2,5$) precisely if any eight of the conditions are satisfies:
1) $p\equiv 1(\bmod 8)$ and $p\equiv 1(\bmod 5)$
2) $p\equiv 1(\bmod 8)$ and $p\equiv -1(\bmod 5)$
3) $p\equiv -1(\bmod 8)$ and $p\equiv 1(\bmod 5)$
4) $p\equiv -1(\bmod 8)$ and $p\equiv -1(\bmod 5)$
5) $p\equiv 3(\bmod 8)$ and $p\equiv 2(\bmod 5)$
6) $p\equiv 3(\bmod 8)$ and $p\equiv -2(\bmod 5)$
7) $p\equiv -3(\bmod 8)$ and $p\equiv 2(\bmod 5)$
8) $p\equiv -3(\bmod 8)$ and $p\equiv -2(\bmod 5)$

Using the Chinese remainder theorem we get:
1) $p\equiv 1(\bmod 40)$
2) $p\equiv 9(\bmod 40)$
3) $p\equiv -9(\bmod 40)$
4) $p\equiv -1(\bmod 40)$
5) $p\equiv -13(\bmod 40)$
6) $p\equiv 3(\bmod 40)$
7) $p\equiv -3(\bmod 40)$
8) $p\equiv 13(\bmod 40)$

Thus, $p$ needs to have the form $40k\pm 1,40k \pm 3, 40k\pm 9, 40k\pm 13$.