Prev: Automorphism group of symmetric groups
Next: Reverse Look and Say Sequence
From: Bill Dubuque on 5 Nov 2009 18:45
"Achava Nakhash, the Loving Snake" <achava(a)hotmail.com> writes:
> On Nov 5, 7:08�am, Bill Dubuque <w...(a)nestle.csail.mit.edu> wrote:
>> "Achava Nakhash, the Loving Snake" <ach...(a)hotmail.com> writes:
>>> On Nov 4, 7:44�am, Bill Dubuque <w...(a)nestle.csail.mit.edu> wrote:
>>>> Christopher Kolago <krzysztof.kol...(a)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).

> 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
From: Gerry Myerson on 5 Nov 2009 19:24
In article
<c471b166-ee82-4c7c-96bb-ad30d11de97a(a)b36g2000prf.googlegroups.com>,
"Achava Nakhash, the Loving Snake" <achava(a)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 (gerry(a)maths.mq.edi.ai) (i -> u for email)
From: Achava Nakhash, the Loving Snake on 5 Nov 2009 21:30
On Nov 5, 4:24 pm, Gerry Myerson <ge...(a)maths.mq.edi.ai.i2u4email>
wrote:
> In article
> <c471b166-ee82-4c7c-96bb-ad30d11de...(a)b36g2000prf.googlegroups.com>,
>  "Achava Nakhash, the Loving Snake" <ach...(a)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...(a)maths.mq.edi.ai) (i -> u for email)

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
From: master1729 on 7 Nov 2009 05:21
Bill Dubuque wrote :

> "Achava Nakhash, the Loving Snake"
> <achava(a)hotmail.com> writes:
> > On Nov 5, 7:08 am, Bill Dubuque
> <w...(a)nestle.csail.mit.edu> wrote:
> >> "Achava Nakhash, the Loving Snake"
> <ach...(a)hotmail.com> writes:
> >>> On Nov 4, 7:44 am, Bill Dubuque
> <w...(a)nestle.csail.mit.edu> wrote:
> >>>> Christopher Kolago <krzysztof.kol...(a)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).

hahaha me too.

they didnt fool me a second !!


>
> > 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
First  |  Prev  | 
Pages: 1 2 3 4 5
Prev: Automorphism group of symmetric groups
Next: Reverse Look and Say Sequence