Results 1 to 10 of 10

Math Help - Square Roots and Su mof Two Squares (involves modulos)

  1. #1
    Banned
    Joined
    Apr 2009
    Posts
    96

    Square Roots and Su mof Two Squares (involves modulos)

    Hello all,

    I have a few questions about how squares affect mods. Here they are:

    1. Assume p to be an odd prime and a is any integer not congruent to 0 modulo p. It can be proven that the congruence (x^2) = ((-a)^2)(mod p) has solutions IFF p = 1 (mod 4).

    How is that proven?

    2. Assume there are two numbers c and d where GCD[c,d]=1. If p is any prime number and p|((c^2)+(d^2)), then p = 1 (mod 4),

    How is this also proven ?

    Any help is greatly appreciated!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by 1337h4x View Post
    Hello all,

    I have a few questions about how squares affect mods. Here they are:

    1. Assume p to be an odd prime and a is any integer not congruent to 0 modulo p. It can be proven that the congruence (x^2) = ((-a)^2)(mod p) has solutions IFF p = 1 (mod 4).

    How is that proven?

    2. Assume there are two numbers c and d where GCD[c,d]=1. If p is any prime number and p|((c^2)+(d^2)), then p = 1 (mod 4),

    How is this also proven ?

    Any help is greatly appreciated!
    2.) This follows directly from 1.):

     p\mid c^2+d^2 \iff c^2+d^2\equiv 0\bmod{p}\iff c^2\equiv-d^2\bmod{p}\implies p\equiv1\bmod{4}

    Now I'll help you out with 1.) if no one else does after a while.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Banned
    Joined
    Apr 2009
    Posts
    96
    Quote Originally Posted by chiph588@ View Post
    2.) This follows directly from 1.):

     p\mid c^2+d^2 \iff c^2+d^2\equiv 0\bmod{p}\iff c^2\equiv-d^2\bmod{p}\implies p\equiv1\bmod{4}

    Now I'll help you out with 1.) if no one else does after a while.

    So how did you get 1 and 4 out of that expression? I'm sure its really simple, but trial and error is the only way I've shown it thus far. Isn't there a more "concrete" way to get 1 and 4 and not using guess & check?

    I will certainly appreciate it if you help me with 1.) . Much thanks will be given!
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by 1337h4x View Post
    So how did you get 1 and 4 out of that expression? I'm sure its really simple, but trial and error is the only way I've shown it thus far. Isn't there a more "concrete" way to get 1 and 4 and not using guess & check?

    I will certainly appreciate it if you help me with 1.) . Much thanks will be given!
    I got it from applying what #1 says.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by 1337h4x View Post
    1. Assume p to be an odd prime and a is any integer not congruent to 0 modulo p. It can be proven that the congruence (x^2) = ((-a)^2)(mod p) has solutions IFF p = 1 (mod 4).

    How is that proven?
    One way is easy:

    Assume  p\equiv 1\bmod{4} .

    Consider  \left(\frac{p-1}{2}\right)! = (2n)! since  \frac{p-1}{2} is even.

    I'm assuming you're familiar with Wilson's Theorem that states  (p-1)!\equiv -1 \bmod{p} when  p is prime.

    So  -1\equiv (p-1)! = (1\cdot2\cdots2n)((2n+1)\cdots(4n)) = (1\cdot2\cdots2n)((p-2n)\cdots(p-1))  \equiv (1\cdot2\cdots2n)((-2n)\cdots(-1)) = (-1)^{2n}\left(\left(\frac{p-1}{2}\right)!\right)^2 \bmod{p} .

    Thus given  p\equiv -1\bmod{4} , the solution to  x^2\equiv -a^2\bmod{p} is  x\equiv a\cdot\left(\frac{p-1}{2}\right)!

    -------

    I'll post the other direction later.
    Last edited by chiph588@; May 28th 2010 at 07:16 PM.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by 1337h4x View Post
    1. Assume p to be an odd prime and a is any integer not congruent to 0 modulo p. It can be proven that the congruence (x^2) = ((-a)^2)(mod p) has solutions IFF p = 1 (mod 4).

    How is that proven?
    Now for the other direction:

    -------

    Lemma: Given  (a,p)=1 , suppose  n is the smallest number greater than  0 such that  a^n\equiv1\bmod{p} and  a^m\equiv1\bmod{p} where  m>n , then  n\mid m .

    Proof: By the division algorithm,  m=qn+d where  0\leq d <n . So we then get  1\equiv a^m=a^{qn+d}=\left(a^n\right)^q\cdot a^d \equiv 1\cdot a^d=a^d\bmod{p} . Since  d<n and  a^d\equiv1\bmod{p} , by the minimality of  n this forces  d=0 . So we see that  m=qn\implies n\mid m .

    -------

    Suppose  x^2\equiv-a^2\bmod{p} is solvable. This implies  \left(a^2\right)^{-1}\cdot x^2=\left(xa^{-1}\right)^2\equiv-1\bmod{p}\implies y^2\equiv-1\bmod{p} is solvable. So observe that it's equivalent to show  x^2\equiv-1\bmod{p} solvable implies  p\equiv1\bmod{4} .

    Since  p is odd,  x\neq1 , so we have the following:
     x^1\not\equiv1\bmod{p}
     x^2\equiv-1\not\equiv1\bmod{p}
     x^3\equiv(-1)x\not\equiv1\bmod{p}
     x^4\equiv(-1)^2\equiv1\bmod{p}

    So as you can see,  4 is the smallest exponent greater than  0 such that  x^n\equiv 1\bmod{p} . Now by Fermat's little theorem, since  (x,p)=1\implies x^{p-1}\equiv1\bmod{p} . By our above Lemma, this implies  4\mid p-1 \implies p\equiv1\bmod{4} .
    Last edited by chiph588@; May 29th 2010 at 07:18 AM.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Banned
    Joined
    Apr 2009
    Posts
    96
    Quote Originally Posted by chiph588@ View Post
    Now for the other direction:

    -------

    Lemma: Given  (a,p)=1 , suppose  n is the smallest number greater than  0 such that  a^n\equiv1\bmod{p} and  a^m\equiv1\bmod{p} where  m>n , then  n\mid m .

    Proof: By the division algorithm,  m=qn+d where  0\leq d <n . So we then get  1\equiv a^m=a^{qn+d}=\left(a^n\right)^q\cdot a^d \equiv 1\cdot a^d=a^d\bmod{p} . Since  d<n and  a^d\equiv1\bmod{p} , by the minimality of  n this forces  d=0 . So we see that  m=qn\implies n\mid m .

    -------

    Suppose  x^2\equiv-a^2\bmod{p} is solvable. This implies  \left(a^2\right)^{-1}\cdot x^2=\left(xa^{-1}\right)^2\equiv-1\bmod{p}\implies y^2\equiv-1\bmod{p} is solvable. So observe that it's equivalent to show  x^2\equiv-1\bmod{p} solvable implies  p\equiv1\bmod{4} .

    Since  p is odd,  x\neq1 , so we have the following:
     x^1\not\equiv1\bmod{p}
     x^2\equiv-1\not\equiv1\bmod{p}
     x^3\equiv(-1)x\not\equiv1\bmod{p}
     x^4\equiv(-1)^2\equiv1\bmod{p}

    So as you can see,  4 is the smallest exponent greater than  0 such that  x^n\equiv 1\bmod{p} . Now by Fermat's little theorem, since  (x,p)=1\implies x^{p-1}\equiv1\bmod{p} . By our above Lemma, this implies  4\mid p-1 \implies p\equiv1\bmod{4} .

    So are you saying, this is just another way of skinning the cat? Are your "directions" different "ways" of solving the same problem? Both correspond to my first question right?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by 1337h4x View Post
    So are you saying, this is just another way of skinning the cat? Are your "directions" different "ways" of solving the same problem? Both correspond to my first question right?
    Both are for the first question.

    This is what I mean by directions: Your theorem was of the form  a\iff b .

    So in my first post I proved  b\implies a and in my second post I proved  a\implies b .

    Putting these two together gives  a\iff b .
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Banned
    Joined
    Apr 2009
    Posts
    96
    Quote Originally Posted by chiph588@ View Post
    Both are for the first question.

    This is what I mean by directions: Your theorem was of the form  a\iff b .

    So in my first post I proved  b\implies a and in my second post I proved  a\implies b .

    Putting these two together gives  a\iff b .

    So does this mean that you have to have both to adequately prove the theorem ?
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by 1337h4x View Post
    So does this mean that you have to have both to adequately prove the theorem ?
    yes
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. square root and squares
    Posted in the Pre-Calculus Forum
    Replies: 4
    Last Post: September 13th 2010, 01:32 PM
  2. Replies: 2
    Last Post: March 15th 2010, 06:03 PM
  3. Replies: 0
    Last Post: February 28th 2010, 06:59 AM
  4. Math problem (involves square roots)
    Posted in the Math Topics Forum
    Replies: 3
    Last Post: April 1st 2007, 01:08 PM
  5. Rules for squares and square roots
    Posted in the Algebra Forum
    Replies: 0
    Last Post: October 17th 2006, 03:19 PM

Search Tags


/mathhelpforum @mathhelpforum