Results 1 to 8 of 8

Thread: Square Root Modulo Composite

  1. #1
    Member
    Joined
    Nov 2009
    Posts
    169

    Square Root Modulo Composite

    Show that if $\displaystyle n$ is composite, $\displaystyle 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
    5
    Quote Originally Posted by EinStone View Post
    Show that if $\displaystyle n$ is composite, $\displaystyle 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 $\displaystyle \{0,1,\ldots,n-1\}$, the standard residue system modulo $\displaystyle n$. Given any $\displaystyle n$ composite, we're always guaranteed two residues with this property since $\displaystyle 1^2\equiv 1\pmod{n}$ and $\displaystyle (n-1)^2\equiv n^2-2n+1\equiv 1\pmod{n}$.

    Let $\displaystyle a$ be a residue modulo $\displaystyle n$ (where $\displaystyle n\neq 2p$) with $\displaystyle 1<a<n-1$ and let $\displaystyle (a,n)=1$. Then $\displaystyle a^{\varphi(n)}\equiv 1\pmod{n}$ by Euler's Theorem. Keeping in mind that $\displaystyle 2\mid \varphi(n)$ when $\displaystyle n>2$, we see that $\displaystyle a^{\varphi(n)}\equiv \left(a^{\varphi(n)/2}\right)^2\equiv 1\pmod{n}$. Thus, $\displaystyle a^{\varphi(n)/2}$ is a residue that satisfies this property. Consequently, $\displaystyle -a^{\varphi(n)/2}\equiv n-a^{\varphi(n)/2}\pmod{n}$ is also another residue. This one generates a residue different from $\displaystyle 1$ since we required $\displaystyle n\neq 2p$ and it can't generate $\displaystyle n-1$; if it did, then $\displaystyle 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 $\displaystyle n$ with this property. We then allow for the possibility of more residues as we allow $\displaystyle n$ to increase.

    Does this make sense?
    Last edited by Chris L T521; May 20th 2010 at 06: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 $\displaystyle 1$ since we required $\displaystyle n\neq 2p$ and it can't generate $\displaystyle n-1$; if it did, then $\displaystyle 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 $\displaystyle n-1\equiv n-a^{\varphi(n)/2}\pmod{n}$

    This shows that we are guaranteed four different residues modulo $\displaystyle n$ with this property. We then allow for the possibility of more residues as we allow $\displaystyle 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
    5
    Quote Originally Posted by EinStone View Post
    Can you explain this again, esepcially how you get $\displaystyle n-1\equiv n-a^{\varphi(n)/2}\pmod{n}$
    I was claiming that $\displaystyle n-1$ couldn't be generated from $\displaystyle n-a^{\varphi(n)/2}$. To show that, suppose that they were equivalent. Then $\displaystyle 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 $\displaystyle 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 $\displaystyle x^2\equiv 1\pmod{p_i}$ for each prime (power) divisor $\displaystyle p_i$. Does this yield at least four solutions modulo $\displaystyle 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
    $\displaystyle \implies 1\equiv a^{\varphi(n)/2}\pmod{n}$, which can not happen.
    $\displaystyle (2k+1)^{\phi(8)/2}=(2k+1)^2=4k(k+1)+1\equiv1\bmod{8} $
    Last edited by chiph588@; Jun 2nd 2010 at 10: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
    $\displaystyle (2k+1)^{\phi(8)/2}=(2k+1)^2=4k(k+1)+1\equiv1\bmod{8} $
    In fact with a little work one can show $\displaystyle a^{\phi(m)/2}\equiv1\bmod{m} $ when $\displaystyle m $ is not of the form $\displaystyle 1,2,4,p^a,2p^a $, where $\displaystyle p $ is a prime.

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

    -------

    I think the best way to approach this problem would be to show there exists $\displaystyle a $ such that $\displaystyle |a|\not\equiv1\bmod{n} $ and $\displaystyle a\equiv a^{-1}\bmod{n} $.
    Last edited by chiph588@; Jun 2nd 2010 at 02: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 $\displaystyle n$ is composite, $\displaystyle 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 $\displaystyle 18=2\cdot3^2\neq2p $ for a prime $\displaystyle p $

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

    Only $\displaystyle (\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 $\displaystyle x^2\equiv 1\pmod{p_i}$ for each prime (power) divisor $\displaystyle p_i$. Does this yield at least four solutions modulo $\displaystyle n$?
    Using this argument in a slightly altered way for my defense, my guess is this theorem is true when $\displaystyle n\neq2p^a $ where $\displaystyle p $ is an odd prime.
    Last edited by chiph588@; Jun 2nd 2010 at 04: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: Oct 10th 2011, 04:17 PM
  2. primitive root modulo p
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: Mar 23rd 2010, 02:42 AM
  3. Replies: 12
    Last Post: Nov 22nd 2008, 12:41 PM
  4. Square root modulo a prime
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: Jun 16th 2008, 11:40 AM
  5. Primitive root modulo 121
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: Jun 8th 2008, 07:09 AM

Search Tags


/mathhelpforum @mathhelpforum