Browse Groups

• ## Re: [PrimeNumbers] Modulo 1 question

(9)
• NextPrevious
• I ll get this right in a minute :-( 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.
Message 1 of 9 , Oct 6, 2004
View Source
I'll get this right in a minute :-(

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.

Kevin.

>
> Sorry,
>
> I should add "with the exception of 1 itself".
>
>
>
> >
> > Hi,
> >
> > Can anyone tell me if a proof exists that shows that in the case:
> >
> > x^2 = 1 mod p
> >
> > That x is always an even number.
> >
> > Kevin.
> >
> >
> >
> > ------------------------ 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 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/
>
>
>
>
>
>
>
>
>
>
>
• ... 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 2 of 9 , Oct 6, 2004
View Source
> 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
• 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 3 of 9 , Oct 6, 2004
View Source
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 4 of 9 , Oct 6, 2004
View Source
> 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 5 of 9 , Oct 6, 2004
View Source
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 6 of 9 , Oct 7, 2004
View Source
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 7 of 9 , Oct 7, 2004
View Source
--- 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.
• Changes have not been saved
Press OK to abandon changes or Cancel to continue editing
• Your browser is not supported
Kindly note that Groups does not support 7.0 or earlier versions of Internet Explorer. We recommend upgrading to the latest Internet Explorer, Google Chrome, or Firefox. If you are using IE 9 or later, make sure you turn off Compatibility View.