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

Re: [PrimeNumbers] Modulo 1 question

Expand Messages
  • 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 1 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 2 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 3 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 4 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 5 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 6 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.