Why does 2^n != 1 (mod n) is true for every n

Main Page | Report this Page

Science Forum Index » Mathematics Forum » Why does 2^n != 1 (mod n) is true for every n > 1?...

Page 2 of 2 Goto page Previous 1, 2

Why does 2^n != 1 (mod n) is true for every n > 1?...

Author

Message

Pubkeybreaker...

Posted: Thu Nov 05, 2009 10:45 am

Guest

On Nov 5, 2:25 pm, master1729 <tommy1... at (no spam) gmail.com> wrote:
[quote]On Tue, 3 Nov 2009, Christopher Kolago wrote:

Why does:

2^n != 1 (mod n)

for every n > 1?

I managed to prove that 2^n != 1 (mod n) using the
Euler's theorem.

Then show us.

2^5 = 2 (mod 5)
2^7 = 2 (mod 7)
[/quote]
It is trivially true for primes, since 2^(p-1) = 1 mod p for all
odd primes. The trick is to show that it is true for COMPOSITES.

master1729...

Posted: Thu Nov 05, 2009 11:30 am

Guest

Pubkeybreaker wrote :

[quote]On Nov 5, 2:25Â pm, master1729 <tommy1... at (no spam) gmail.com
wrote:
On Tue, 3 Nov 2009, Christopher Kolago wrote:

Why does:

2^n != 1 (mod n)

for every n > 1?

I managed to prove that 2^n != 1 (mod n) using
the
Euler's theorem.

Then show us.

2^5 = 2 (mod 5)
2^7 = 2 (mod 7)

It is trivially true for primes, since 2^(p-1) = 1
mod p for all
odd primes. The trick is to show that it is true for
COMPOSITES.
[/quote]
but the OP didnt write 2^(p-1) = 1 mod p

occording to the OP : 2^p = 1 mod p !?!?
( follows from n is prime in 2^n = 1 mod n !! )

regards

tommy1729

Achava Nakhash, the Loving Snake...

Posted: Thu Nov 05, 2009 12:05 pm

Guest

On Nov 5, 7:08 am, Bill Dubuque <w... at (no spam) nestle.csail.mit.edu> wrote:
[quote]"Achava Nakhash, the Loving Snake" <ach... at (no spam) hotmail.com> writes:

On Nov 4, 7:44 am, Bill Dubuque <w... at (no spam) nestle.csail.mit.edu> wrote:
Christopher Kolago <krzysztof.kol... at (no spam) uj.edu.pl> wrote:

Why does: 2^n != 1 (mod n) for every n > 1?
Is there any "simple" proof of this fact?

HINT the least prime p|n cannot also divide 2^n - 1 since

THEOREM prime p|(n, 2^n - 1) => (n,p-1) > 1 => prime q|n for q<p

PROOF 1 = 2^n = 2^(p-1) => 1 = 2^(n,p-1) (mod p)

The theorem generalizes to a^n - 1 for (a-1,n) = 1.

Nice proof, Bill. I always enjoy it when there is a non-algebraic
side to a number theory proof. My own proof, perhpas not coincidentally,
also involves a least prime dividing n argument. The> key step that I
left for the OP above was to show that phi(n) cannot divide n.

Precisely how do you conclu the proof from that?
Are you presuming that 2 has order phi(n) (mod n)?
[/quote]
Have you ever read the Asimov robot mystery stories? In all of them
robots are constructed so that they cannot either harm a human or
through inaction let a human come to harm. And yet in one of them, a
robot hands a glass or cup or mug or whatever of poison and so causes
a human to die. The robot could do this because there was a
disconnect between the act of putting the poison in the cup - probably
done by robot A, but I don't remember any more, and handing the cup to
the human - probably done by robot B

Is that precise enough for you?

But seriously folks, it can't be done. The argument is wrong, so here
is one that appears to be quicker than anything else posted, and it
also uses a least prime dividing n argument. First of all, as a
general statement, if a divides b, and r is an integer prime to b,
then the order of r mod a must divide the order of r mod b. Now let p
be the smallest prime dividing n. If n is odd, then the order of 2
mod p must divide p-1 and so be relatively prime to n. Hence 2^n
cannot be 1 mod n. If nn is even, since no power of 2 is congruent 1
mod any power of 2, no power of 2 is congruent to 1 mod n.

There is nothing sacred about 2 here. The same argument clearly works
for any integer r in place of 2.

So now every posted proof has used a least prime arguemnt. Are there
any proofs of this interesting fact that don't? Anyone? Anyone?

Regards,
Achava

master1729...

Posted: Thu Nov 05, 2009 12:15 pm

Guest

i master1729 wrote :

[quote]Pubkeybreaker wrote :

On Nov 5, 2:25Â pm, master1729
tommy1... at (no spam) gmail.com
wrote:
On Tue, 3 Nov 2009, Christopher Kolago wrote:

Why does:

2^n != 1 (mod n)

for every n > 1?

I managed to prove that 2^n != 1 (mod n)
using
the
Euler's theorem.

Then show us.

2^5 = 2 (mod 5)
2^7 = 2 (mod 7)

It is trivially true for primes, since 2^(p-1) =
1
mod p for all
odd primes. The trick is to show that it is true
for
COMPOSITES.

but the OP didnt write 2^(p-1) = 1 mod p

occording to the OP : 2^p = 1 mod p !?!?
( follows from n is prime in 2^n = 1 mod n !! )

regards

tommy1729
[/quote]
btw :

2^15 = 8 (mod 15) not 1 (mod 15)

still not convinced ?!?!?!?

tommy1729

Achava Nakhash, the Loving Snake...

Posted: Thu Nov 05, 2009 4:30 pm

Guest

On Nov 5, 4:24 pm, Gerry Myerson <ge... at (no spam) maths.mq.edi.ai.i2u4email>
wrote:
[quote]In article
c471b166-ee82-4c7c-96bb-ad30d11de... at (no spam) b36g2000prf.googlegroups.com>,
"Achava Nakhash, the Loving Snake" <ach... at (no spam) hotmail.com> wrote:

There is nothing sacred about 2 here. The same argument clearly works
for any integer r in place of 2.

I hope you're not suggesting that if r is an integer then there's no
integer n > 1 such that n divides r^n - 1.

First of all, you're in big trouble if r = 1.

But somewhat less trivially, 2 divides 3^2 - 1, 4 divides 3^4 - 1,
8 divides 3^8 - 1, ....

--
Gerry Myerson (ge... at (no spam) maths.mq.edi.ai) (i -> u for email)
[/quote]
Yes, of course. I realized the key flaw at work. I wrote in a hurry
on my lunch break.

First of all, 2^1 - 1 is divisible by 1. This is of course a trivial
problem, but my proof relies on the order of 2 mod the least prime p
being larger than 1 but less than p-1. Unfortunately 1 has order 1
modulo more or less anything, so my proof fails for r = 1 and it also
fails for r > 2 if and only if r = 1 (mod p) where p is the least
prime dividing n.

Thus a statement is proved that is still pretty strong:

If r is an integer other than 1 and n > 1 is an integer, then 2^n - 1
is not divisible by n unless r = 1(mod p) where p is the least prime
dividing n.

Note that this takes care of Gerry's examples as p = 2 in all his
examples and p = 1(mod 2).
There are other counterexamples as well. For instance if n = p and r
= p + 1 then r to any power is 1 mod p.

I am a little too tired to keep my head straight about this at the
moment, so I will ask the obvious question:

How do we characterize the r and n such that r^n = 1 (mod n)?

I leave it to the group.

Regards,
Achava

Bill Dubuque...

Posted: Thu Nov 05, 2009 6:09 pm

Guest

Bill Dubuque <wgd at (no spam) nestle.csail.mit.edu> writes:

[quote]Christopher Kolago <krzysztof.kolago at (no spam) uj.edu.pl> wrote:

Why does: 2^n != 1 (mod n) for every n > 1?
Is there any "simple" proof of this fact?

HINT the least prime p|n cannot also divide 2^n - 1 since

THEOREM prime p|(n, 2^n - 1) => (n,p-1) > 1 => prime q|n for q<p

PROOF 1 = 2^n = 2^(p-1) => 1 = 2^(n,p-1) (mod p)

The theorem generalizes to a^n - 1 for (a-1,n) = 1.
[/quote]
Or: p := least prime p|n, e := order of a (mod p)

mod p: a^n = 1 => e|n => e>=p =><= a^(p-1) = 1 QED

Ie. in a monoid: a^n = 1 => ord(a) >= least prime p|n

--Bill Dubuque

Bill Dubuque...

Posted: Thu Nov 05, 2009 6:45 pm

Guest

"Achava Nakhash, the Loving Snake" <achava at (no spam) hotmail.com> writes:
[quote]On Nov 5, 7:08 am, Bill Dubuque <w... at (no spam) nestle.csail.mit.edu> wrote:
"Achava Nakhash, the Loving Snake" <ach... at (no spam) hotmail.com> writes:
On Nov 4, 7:44 am, Bill Dubuque <w... at (no spam) nestle.csail.mit.edu> wrote:
Christopher Kolago <krzysztof.kol... at (no spam) uj.edu.pl> wrote:

Why does: 2^n != 1 (mod n) for every n > 1?
Is there any "simple" proof of this fact?

HINT the least prime p|n cannot also divide 2^n - 1 since

THEOREM prime p|(n, 2^n - 1) => (n,p-1) > 1 => prime q|n for q<p

PROOF 1 = 2^n = 2^(p-1) => 1 = 2^(n,p-1) (mod p)

The theorem generalizes to a^n - 1 for (a-1,n) = 1.

Nice proof, Bill. I always enjoy it when there is a non-algebraic
side to a number theory proof. My own proof, perhpas not coincidentally,
also involves a least prime dividing n argument. The> key step that I
left for the OP above was to show that phi(n) cannot divide n.

Precisely how do you conclude the proof from that?
Are you presuming that 2 has order phi(n) (mod n)?

[...] it can't be done. The argument is wrong, so here
[/quote]
As I suspected. I'm surprised by the number of erroneous proof
attempts employing phi(n).

[quote]is one that appears to be quicker than anything else posted, and it
also uses a least prime dividing n argument. First of all, as a
general statement, if a divides b, and r is an integer prime to b,
then the order of r mod a must divide the order of r mod b. Now let p
be the smallest prime dividing n. If n is odd, then the order of 2
mod p must divide p-1 and so be relatively prime to n. Hence 2^n
cannot be 1 mod n. If n is even, since no power of 2 is congruent 1
mod any power of 2, no power of 2 is congruent to 1 mod n.
[/quote]
Simpler: 2|n|2^n-1 => 2|1. That's essentially the same as my proof.
Compare my followup where I highlighted the essence as follows:

in monoid M: a^n = 1 => ord(a) >= least p|n => #M >= p

--Bill Dubuque

Gerry Myerson...

Posted: Thu Nov 05, 2009 7:24 pm

Guest

In article
<c471b166-ee82-4c7c-96bb-ad30d11de97a at (no spam) b36g2000prf.googlegroups.com>,
"Achava Nakhash, the Loving Snake" <achava at (no spam) hotmail.com> wrote:

[quote]There is nothing sacred about 2 here. The same argument clearly works
for any integer r in place of 2.
[/quote]
I hope you're not suggesting that if r is an integer then there's no
integer n > 1 such that n divides r^n - 1.

First of all, you're in big trouble if r = 1.

But somewhat less trivially, 2 divides 3^2 - 1, 4 divides 3^4 - 1,
8 divides 3^8 - 1, ....

--
Gerry Myerson (gerry at (no spam) maths.mq.edi.ai) (i -> u for email)

master1729...

Posted: Sat Nov 07, 2009 10:21 am

Guest

Bill Dubuque wrote :

[quote]"Achava Nakhash, the Loving Snake"
achava at (no spam) hotmail.com> writes:
On Nov 5, 7:08Â am, Bill Dubuque
w... at (no spam) nestle.csail.mit.edu> wrote:
"Achava Nakhash, the Loving Snake"
ach... at (no spam) hotmail.com> writes:
On Nov 4, 7:44Â am, Bill Dubuque
w... at (no spam) nestle.csail.mit.edu> wrote:
Christopher Kolago <krzysztof.kol... at (no spam) uj.edu.pl
wrote:

Why does: 2^n != 1 (mod n) for every n > 1?
Is there any "simple" proof of this fact?

HINT the least prime p|n cannot also divide
2^n - 1 since

THEOREM prime p|(n, 2^n - 1) => (n,p-1) > 1
=> prime q|n for q<p

PROOF 1 = 2^n = 2^(p-1) => 1 = 2^(n,p-1)
(mod p)

The theorem generalizes to a^n - 1 for
(a-1,n) = 1.

Nice proof, Bill. I always enjoy it when there
is a non-algebraic
side to a number theory proof. My own proof,
perhpas not coincidentally,
also involves a least prime dividing n argument.
The> key step that I
left for the OP above was to show that phi(n)
cannot divide n.

Precisely how do you conclude the proof from that?

Are you presuming that 2 has order phi(n) (mod n)?

[...] it can't be done. The argument is wrong, so
here

As I suspected. I'm surprised by the number of
erroneous proof
attempts employing phi(n).
[/quote]
hahaha me too.

they didnt fool me a second !!

[quote]
is one that appears to be quicker than anything
else posted, and it
also uses a least prime dividing n argument. First
of all, as a
general statement, if a divides b, and r is an
integer prime to b,
then the order of r mod a must divide the order of
r mod b. Now let p
be the smallest prime dividing n. If n is odd,
then the order of 2
mod p must divide p-1 and so be relatively prime to
n. Hence 2^n
cannot be 1 mod n. If n is even, since no power of
2 is congruent 1
mod any power of 2, no power of 2 is congruent to 1
mod n.

Simpler: 2|n|2^n-1 => 2|1. That's essentially the
same as my proof.
Compare my followup where I highlighted the essence
as follows:

in monoid M: a^n = 1 => ord(a) >= least p|n =
#M >= p

--Bill Dubuque[/quote]

Page 2 of 2 Goto page Previous 1, 2

All times are GMT - 5 Hours The time now is Mon Dec 07, 2009 4:11 am Science Forum Index