Expand Messages
• 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 1 of 9 , Oct 6 6:14 PM
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/
>
>
>
>
>
>
>
>
>
>
>
• ... 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 2 of 9 , Oct 6 6:39 PM
> 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.
• 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 3 of 9 , Oct 6 6:53 PM
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/
>
>
>
>
>
>
>
>
>
>
>
• 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 4 of 9 , Oct 7 3:35 AM
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@...>
>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)
• ... 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 5 of 9 , Oct 7 6:51 AM
--- 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.