Results 1 to 8 of 8

Math Help - Square Root Modulo Composite

  1. #1
    Member
    Joined
    Nov 2009
    Posts
    169

    Square Root Modulo Composite

    Show that if n is composite, n \neq 2p (for prime p), then there at least 4 different residues modulo n, whose squares equal 1.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Rhymes with Orange Chris L T521's Avatar
    Joined
    May 2008
    From
    Chicago, IL
    Posts
    2,844
    Thanks
    3
    Quote Originally Posted by EinStone View Post
    Show that if n is composite, n \neq 2p (for prime p), then there at least 4 different residues modulo n, whose squares equal 1.
    To make this easy to follow, suppose we're dealing with \{0,1,\ldots,n-1\}, the standard residue system modulo n. Given any n composite, we're always guaranteed two residues with this property since 1^2\equiv 1\pmod{n} and (n-1)^2\equiv n^2-2n+1\equiv 1\pmod{n}.

    Let a be a residue modulo n (where n\neq 2p) with 1<a<n-1 and let (a,n)=1. Then a^{\varphi(n)}\equiv 1\pmod{n} by Euler's Theorem. Keeping in mind that 2\mid \varphi(n) when n>2, we see that a^{\varphi(n)}\equiv \left(a^{\varphi(n)/2}\right)^2\equiv 1\pmod{n}. Thus, a^{\varphi(n)/2} is a residue that satisfies this property. Consequently, -a^{\varphi(n)/2}\equiv n-a^{\varphi(n)/2}\pmod{n} is also another residue. This one generates a residue different from 1 since we required n\neq 2p and it can't generate n-1; if it did, then n-1\equiv n-a^{\varphi(n)/2}\pmod{n}\implies a^{\varphi(n)/2}\equiv 1\pmod{n}, which isn't possible given the restrictions we made on the problem.

    This shows that we are guaranteed four different residues modulo n with this property. We then allow for the possibility of more residues as we allow n to increase.

    Does this make sense?
    Last edited by Chris L T521; May 20th 2010 at 07:02 AM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Nov 2009
    Posts
    169
    Quote Originally Posted by Chris L T521 View Post
    This one generates a residue different from 1 since we required n\neq 2p and it can't generate n-1; if it did, then n-1\equiv n-a^{\varphi(n)/2}\pmod{n}\implies a^{\varphi(n)/2}\equiv 1\pmod{n}, which isn't possible given the restrictions we made on the problem.
    Can you explain this again, esepcially how you get n-1\equiv n-a^{\varphi(n)/2}\pmod{n}

    This shows that we are guaranteed four different residues modulo n with this property. We then allow for the possibility of more residues as we allow n to increase.

    Does this make sense?
    What do you mean increase n, I mean n is fixed??
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Rhymes with Orange Chris L T521's Avatar
    Joined
    May 2008
    From
    Chicago, IL
    Posts
    2,844
    Thanks
    3
    Quote Originally Posted by EinStone View Post
    Can you explain this again, esepcially how you get n-1\equiv n-a^{\varphi(n)/2}\pmod{n}
    I was claiming that n-1 couldn't be generated from n-a^{\varphi(n)/2}. To show that, suppose that they were equivalent. Then n-1\equiv n-a^{\varphi(n)/2}\pmod{n}\implies 1\equiv a^{\varphi(n)/2}\pmod{n}, which can not happen.

    What do you mean increase n, I mean n is fixed??
    I mean as we pick larger values of n, the number of residues that satisfy the property of interest will be more than 4.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member roninpro's Avatar
    Joined
    Nov 2009
    Posts
    485
    I was actually thinking that you could use the Chinese Remainder Theorem. Just look at x^2\equiv 1\pmod{p_i} for each prime (power) divisor p_i. Does this yield at least four solutions modulo n?
    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 Chris L T521 View Post
    \implies 1\equiv a^{\varphi(n)/2}\pmod{n}, which can not happen.
     (2k+1)^{\phi(8)/2}=(2k+1)^2=4k(k+1)+1\equiv1\bmod{8}
    Last edited by chiph588@; June 2nd 2010 at 11:55 AM.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor chiph588@'s Avatar
    Joined
    Sep 2008
    From
    Champaign, Illinois
    Posts
    1,163
    Quote Originally Posted by chiph588@ View Post
     (2k+1)^{\phi(8)/2}=(2k+1)^2=4k(k+1)+1\equiv1\bmod{8}
    In fact with a little work one can show  a^{\phi(m)/2}\equiv1\bmod{m} when  m is not of the form  1,2,4,p^a,2p^a , where  p is a prime.

    So unfortunately I believe your proof (for most  n ) only finds  2 such numbers, namely  \{1,n-1\} , where  a^2\equiv1\bmod{n} .

    -------

    I think the best way to approach this problem would be to show there exists  a such that  |a|\not\equiv1\bmod{n} and  a\equiv a^{-1}\bmod{n} .
    Last edited by chiph588@; June 2nd 2010 at 03:08 PM.
    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 EinStone View Post
    Show that if n is composite, n \neq 2p (for prime p), then there at least 4 different residues modulo n, whose squares equal 1.
    I believe this statement is false. Consider  18=2\cdot3^2\neq2p for a prime  p

     \begin{tabular}{|c c | c c|}\hline<br />
      a & a squared & a & a squared \\\hline<br />
      1 & 1 & 10 & 10\\<br />
      2 & 4 & 11 & 13\\<br />
      3 & 9 & 12 & 0\\<br />
      4 & 16 & 13 & 7\\<br />
      5 & 7 & 14 & 16\\<br />
      6 & 0 & 15 & 9\\<br />
      7 & 13 & 16 & 4\\<br />
      8 & 10 &  17 & 1\\<br />
      9 & 9 & & \\\hline<br />
      \end{tabular}

    Only  (\pm1)^2\equiv1\bmod{18} , thus a counterexample.

    Quote Originally Posted by roninpro View Post
    I was actually thinking that you could use the Chinese Remainder Theorem. Just look at x^2\equiv 1\pmod{p_i} for each prime (power) divisor p_i. Does this yield at least four solutions modulo n?
    Using this argument in a slightly altered way for my defense, my guess is this theorem is true when  n\neq2p^a where  p is an odd prime.
    Last edited by chiph588@; June 2nd 2010 at 05:47 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Square root inside square root equation
    Posted in the Algebra Forum
    Replies: 3
    Last Post: October 10th 2011, 05:17 PM
  2. primitive root modulo p
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: March 23rd 2010, 03:42 AM
  3. Replies: 12
    Last Post: November 22nd 2008, 01:41 PM
  4. Square root modulo a prime
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: June 16th 2008, 12:40 PM
  5. Primitive root modulo 121
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: June 8th 2008, 08:09 AM

Search Tags


/mathhelpforum @mathhelpforum