> What I am looking for is a proof that for

Well, first, the choice of 'p' to represent an odd composite

> x^2 = 1 mod p

> where p is an odd composite and x is not 1 that x is always even.

is, well, a bit *odd*... :)

Other than that, how about a counter-example:

x = 11

p = 15- --- Kevin Acres wrote:
> So what I am getting at, is that every odd composite will have

Okay, let's look at this a couple of things at a time...

> a case where x is even (and less than p-1), but may not have a

> case where x is odd.

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.