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

Re: Modulo 1 question

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