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

Modulo 1 question

Expand Messages
  • Kevin Acres
    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.
    Message 1 of 9 , Oct 6, 2004
    • 0 Attachment
      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.
    • Kevin Acres
      Sorry, I should add with the exception of 1 itself . ... - ... ~-
      Message 2 of 9 , Oct 6, 2004
      • 0 Attachment
        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
        >
        >
        >
        >
        >
        >
        >
        >
        >
      • 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 3 of 9 , Oct 6, 2004
        • 0 Attachment
          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 4 of 9 , Oct 6, 2004
          • 0 Attachment
            > 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 5 of 9 , Oct 6, 2004
            • 0 Attachment
              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 6 of 9 , Oct 6, 2004
              • 0 Attachment
                > 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 7 of 9 , Oct 6, 2004
                • 0 Attachment
                  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 8 of 9 , Oct 7, 2004
                  • 0 Attachment
                    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 9 of 9 , Oct 7, 2004
                    • 0 Attachment
                      --- 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.