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

**vinodannu** · October 15th 2008, 09:27 AM

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;

**ThePerfectHacker** · October 15th 2008, 05:03 PM

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.

**ThePerfectHacker** · October 15th 2008, 05:41 PM

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$ .

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

LinkBack

Thread Tools

Display

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

Similar Math Help Forum Discussions

Is S_3 congruent to D_3?

Prove that [ a^phi(b) + b^phi(a) ] is congruent to 1 (mod ab)

x^6 congruent to 1 (mod 19)

(a,p)=1,(n,p-1)=1 then x^n congruent a mod p has exactly one solution

congruent mod 9

Search Tags