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

Re: [PrimeNumbers] Modulo 1 question

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