Results 1 to 3 of 3

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

  1. #1
    Newbie
    Joined
    Jul 2008
    Posts
    12

    Thumbs down 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;
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by vinodannu View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    10
    Quote Originally Posted by vinodannu View Post
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Is S_3 congruent to D_3?
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: September 29th 2011, 08:24 PM
  2. Replies: 6
    Last Post: March 14th 2011, 08:06 AM
  3. x^6 congruent to 1 (mod 19)
    Posted in the Number Theory Forum
    Replies: 10
    Last Post: March 2nd 2010, 07:54 PM
  4. Replies: 1
    Last Post: August 1st 2008, 11:01 AM
  5. congruent mod 9
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: January 11th 2007, 08:07 PM

Search Tags


/mathhelpforum @mathhelpforum