Prev: Automorphism group of symmetric groups
Next: Reverse Look and Say Sequence
From: Pubkeybreaker on 5 Nov 2009 15:45
On Nov 5, 2:25 pm, master1729 <tommy1...(a)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.
From: master1729 on 5 Nov 2009 06:30
Pubkeybreaker wrote :

> On Nov 5, 2:25 pm, master1729 <tommy1...(a)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
From: Achava Nakhash, the Loving Snake on 5 Nov 2009 17:05
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 conclu the proof from that?  
> Are you presuming that 2 has order phi(n) (mod n)?

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
From: master1729 on 5 Nov 2009 07:15
i master1729 wrote :

> Pubkeybreaker wrote :
>
> > On Nov 5, 2:25 pm, master1729
> <tommy1...(a)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

btw :

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

still not convinced ?!?!?!?


tommy1729
From: Bill Dubuque on 5 Nov 2009 18:09
Bill Dubuque <wgd(a)nestle.csail.mit.edu> writes:

> Christopher Kolago <krzysztof.kolago(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.

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