Loading ...
Sorry, an error occurred while loading the content.
 

Re: [PrimeNumbers] Modulo 1 question

Expand Messages
  • Kevin Acres
    I ll get this right in a minute :-( What I am looking for is a proof that for x^2 = 1 mod p where p is an odd composite and x is not 1 that x is always even.
    Message 1 of 9 , Oct 6, 2004
      I'll get this right in a minute :-(

      What I am looking for is a proof that for

      x^2 = 1 mod p

      where p is an odd composite and x is not 1 that x is always even.



      Kevin.




      >
      > Sorry,
      >
      > I should add "with the exception of 1 itself".
      >
      >
      >
      > >
      > > Hi,
      > >
      > > Can anyone tell me if a proof exists that shows that in the case:
      > >
      > > x^2 = 1 mod p
      > >
      > > That x is always an even number.
      > >
      > > Kevin.
      > >
      > >
      > >
      > > ------------------------ Yahoo! Groups Sponsor --------------------
      ~-
      > ->
      > > $9.95 domain names from Yahoo!. Register anything.
      > > http://us.click.yahoo.com/J8kdrA/y20IAA/yQLSAA/8HYolB/TM
      > > -------------------------------------------------------------------
      -
      > ~->
      > >
      > > Unsubscribe by an email to: primenumbers-
      unsubscribe@yahoogroups.com
      > > The Prime Pages : http://www.primepages.org/
      > >
      > >
      > > Yahoo! Groups Links
      > >
      > >
      > >
      > >
      > >
      > >
      > >
      > >
      > >
      >
      >
      >
      >
      > ------------------------ Yahoo! Groups Sponsor --------------------~-
      ->
      > $9.95 domain names from Yahoo!. Register anything.
      > http://us.click.yahoo.com/J8kdrA/y20IAA/yQLSAA/8HYolB/TM
      > --------------------------------------------------------------------
      ~->
      >
      > Unsubscribe by an email to: primenumbers-unsubscribe@yahoogroups.com
      > The Prime Pages : http://www.primepages.org/
      >
      >
      > Yahoo! Groups Links
      >
      >
      >
      >
      >
      >
      >
      >
      >
    • Jack Brennen
      ... Well, first, the choice of p to represent an odd composite is, well, a bit *odd*... :) Other than that, how about a counter-example: x = 11 p = 15
      Message 2 of 9 , Oct 6, 2004
        > What I am looking for is a proof that for

        > x^2 = 1 mod p

        > where p is an odd composite and x is not 1 that x is always even.

        Well, first, the choice of 'p' to represent an odd composite
        is, well, a bit *odd*... :)

        Other than that, how about a counter-example:

        x = 11
        p = 15
      • Kevin Acres
        Hi Jack, Your counter example threw me there for a minute. I need to tighten the constraints a little. I should specify that I am looking for the first value
        Message 3 of 9 , Oct 6, 2004
          Hi Jack,

          Your counter example threw me there for a minute. I need to tighten
          the constraints a little.

          I should specify that I am looking for the first value of x other than
          1. So in your example the first x that fits the requirements is 4.

          Regards,

          Kevin.

          >
          > > What I am looking for is a proof that for
          >
          > > x^2 = 1 mod p
          >
          > > where p is an odd composite and x is not 1 that x is always even.
          >
          > Well, first, the choice of 'p' to represent an odd composite
          > is, well, a bit *odd*... :)
          >
          > Other than that, how about a counter-example:
          >
          > x = 11
          > p = 15
          >
          >
          >
          >
          > ------------------------ Yahoo! Groups Sponsor --------------------~-
          ->
          > $9.95 domain names from Yahoo!. Register anything.
          > http://us.click.yahoo.com/J8kdrA/y20IAA/yQLSAA/8HYolB/TM
          > --------------------------------------------------------------------
          ~->
          >
          > Unsubscribe by an email to: primenumbers-unsubscribe@yahoogroups.com
          > The Prime Pages : http://www.primepages.org/
          >
          >
          > Yahoo! Groups Links
          >
          >
          >
          >
          >
          >
          >
          >
          >
        • Jack Brennen
          ... In that case, the smallest counterexample is for modulus 45. The smallest x 1 such that x^2 == 1 (mod 45) is x=19.
          Message 4 of 9 , Oct 6, 2004
            > I should specify that I am looking for the first value of x other than
            > 1. So in your example the first x that fits the requirements is 4.

            In that case, the smallest counterexample is for modulus 45.

            The smallest x>1 such that x^2 == 1 (mod 45) is x=19.
          • Kevin Acres
            Hi Jack, Thanks for that. I must admit that I wasn t looking at low numbers, but larger bi-primes. I ll have to revisit my stratgey to handle composites which
            Message 5 of 9 , Oct 6, 2004
              Hi Jack,

              Thanks for that. I must admit that I wasn't looking at low numbers,
              but larger bi-primes.

              I'll have to revisit my stratgey to handle composites which are the
              product of more than two (not necessarily unique) primes.

              Regards,

              Kevin.

              >
              > > I should specify that I am looking for the first value of x other
              than
              > > 1. So in your example the first x that fits the requirements is
              4.
              >
              > In that case, the smallest counterexample is for modulus 45.
              >
              > The smallest x>1 such that x^2 == 1 (mod 45) is x=19.
              >
              >
              >
              >
              > ------------------------ Yahoo! Groups Sponsor --------------------~-
              ->
              > $9.95 domain names from Yahoo!. Register anything.
              > http://us.click.yahoo.com/J8kdrA/y20IAA/yQLSAA/8HYolB/TM
              > --------------------------------------------------------------------
              ~->
              >
              > Unsubscribe by an email to: primenumbers-unsubscribe@yahoogroups.com
              > The Prime Pages : http://www.primepages.org/
              >
              >
              > Yahoo! Groups Links
              >
              >
              >
              >
              >
              >
              >
              >
              >
            • Kevin Acres
              Hi Jens, I think that my point is that every odd composite has an even x where x^2 = 1 mod p. In the case of p = 55 then x is 34. So what I am getting at,
              Message 6 of 9 , Oct 7, 2004
                Hi Jens,

                I think that my point is that every odd composite has an even 'x' where
                x^2 = 1 mod p. In the case of p = 55 then x is 34.

                So what I am getting at, is that every odd composite will have a case where
                x is even (and less than p-1), but may not have a case where x is odd.

                The counter example that I need to disprove this is where an odd composite
                (p) does not conform to the statement x^2 = 1 mod p where x is less than p-1.

                Regards,

                Kevin.






                At 07:53 PM 7/10/2004, you wrote:
                >----- Original Message -----
                >From: "Kevin Acres" <research@...>
                >To: "Jack Brennen" <jack@...>; "Primenumbers"
                ><primenumbers@yahoogroups.com>
                >Sent: Thursday, October 07, 2004 3:53 AM
                >Subject: Re: [PrimeNumbers] Modulo 1 question
                >
                >
                > > Hi Jack,
                > >
                > > Thanks for that. I must admit that I wasn't looking at low numbers,
                > > but larger bi-primes.
                > >
                > > I'll have to revisit my stratgey to handle composites which are the
                > > product of more than two (not necessarily unique) primes.
                > >
                > > Regards,
                > >
                > > Kevin.
                >
                >Smallest bi-prime counter example:
                >21^2 == 1 (mod 55)
                >
                >If you can program in any language, try experimenting before posting.
                >
                >--
                >Jens Kruse Andersen (offline)
              • jbrennen
                ... Okay, let s look at this a couple of things at a time... First, I ll change the modulus from p to m because p is usually reserved for primes: x^2 ==
                Message 7 of 9 , Oct 7, 2004
                  --- Kevin Acres wrote:
                  > So what I am getting at, is that every odd composite will have
                  > a case where x is even (and less than p-1), but may not have a
                  > case where x is odd.

                  Okay, let's look at this a couple of things at a time...

                  First, I'll change the modulus from 'p' to 'm' because 'p' is
                  usually reserved for primes:

                  x^2 == 1 (modulo m) {m is an odd composite}

                  Note that if there exists any solution x, with 1 < x < m-1, then
                  there exist two such solutions. This is easy to see, because
                  if we have:

                  a^2 == 1 (modulo m)

                  then x=(m-a) is also a solution:

                  (m-a)^2 == m^2-2*a*m+a^2 == m*(m-2*a)+a^2

                  m*(m-2*a)+a^2 == a^2 (modulo m)

                  m*(m-2*a)+a^2 == 1 (modulo m)

                  Now, since m is odd, the pair (a,m-a) contains both an odd
                  number and an even number.

                  So, we can restate: If there exists any solution x, with
                  1 < x < m-1, then there exist both odd and even solutions
                  which satisfy that constraint.

                  Assume that m is a product of two odd numbers j and k which
                  are greater than one and which are coprime.

                  To solve x^2 == 1 (modulo m), we can solve:

                  u^2 == 1 (modulo j)
                  v^2 == 1 (modulo k)

                  and then by the Chinese Remainder Theorem, each unique pair
                  of solutions (u,v) leads to a unique solution x. There are
                  at least 4 solutions to this system of modular equivalences:

                  (u,v) == (1,1)
                  (u,v) == (1,k-1)
                  (u,v) == (j-1,1)
                  (u,v) == (j-1,k-1)

                  The first of these four leads to the solution x == 1, and the
                  last leads to the solution x == m-1. The other two also lead
                  to solutions to the original equation, and the Chinese Remainder
                  Theorem states that those solutions will fall in the range:
                  0 <= x <= m-1, and that they will be distinct from the other
                  solutions. A little thought shows that these two solutions are
                  of the form x==a and x==(m-a) as discussed earlier, and that
                  the existence of both odd and even solutions is directly shown.

                  The only remaining problem is in the case where m cannot be
                  expressed as a product of coprime odd numbers > 1. If m is
                  an odd composite, the only way this can happen is if m is a
                  perfect power of a prime.

                  I won't go into the proof by induction that x^2 == 1 (mod p^n)
                  has only the two trivial solutions x == 1 and x == p^n-1, but
                  it's not too hard to find.

                  In any case, the final conclusion is that:

                  x^2 == 1 (mod m) {m an odd number}

                  has both odd and even non-trivial solutions (1 < x < m-1)
                  if and only if the modulus m is divisible by at least two
                  distinct primes.

                  Hope that helps.
                Your message has been successfully submitted and would be delivered to recipients shortly.