# 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 $\displaystyle p$ an odd prime.

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

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

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

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

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

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

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

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