Results 1 to 3 of 3

Thread: 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 $\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.
    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 $\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$.
    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: Sep 29th 2011, 07:24 PM
  2. Replies: 6
    Last Post: Mar 14th 2011, 07:06 AM
  3. x^6 congruent to 1 (mod 19)
    Posted in the Number Theory Forum
    Replies: 10
    Last Post: Mar 2nd 2010, 06:54 PM
  4. Replies: 1
    Last Post: Aug 1st 2008, 10:01 AM
  5. congruent mod 9
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Jan 11th 2007, 07:07 PM

Search tags for this page

Click on a term to search for related topics.

Search Tags


/mathhelpforum @mathhelpforum