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

Re: [PrimeNumbers] Modulo 1 question

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