Prev: Automorphism group of symmetric groups
Next: Reverse Look and Say Sequence
From: Gerry Myerson on 3 Nov 2009 21:22
In article
<1147769809.5653.1257290602852.JavaMail.root(a)gallium.mathforum.org>,
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?

1972 Putnam Exam, problem A-5.

See discussion in this newsgroup, under the heading
"Divisibility problem," 27 to 30 May 2005.

--
Gerry Myerson (gerry(a)maths.mq.edi.ai) (i -> u for email)
From: Achava Nakhash, the Loving Snake on 3 Nov 2009 23:54
On Nov 3, 3:39 pm, Pubkeybreaker <pubkeybrea...(a)aol.com> wrote:
> On Nov 3, 6:22 pm, 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:
>
> Lagrange's Theorem.  The order of any element must
> divide the order of the group.  The group is Z/nZ*.
> I assume you know how to compute its order?
> Now ask if n divides its order......

This is actually inadequate as a proof. Obviously n does not divide
phi(n), but the actualy issue is whether or not phi(n) divides n. In
fact, the lack of divisibity of phi(n) by n is not merely inadequate,
it is irrelevant. For instance 6^4 = 1 (mod 7) and yet 4 does not
divide 6. Of course it is not so hard to see that n cannot divide phi
(n). unless n = 2.


Regards,
Achava
From: William Elliot on 4 Nov 2009 05:30
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.
From: Pubkeybreaker on 4 Nov 2009 07:24
On Nov 3, 9:08 pm, Christopher Kolago <krzysztof.kol...(a)uj.edu.pl>
wrote:
> > Hint:
>
> > Lagrange's Theorem.  The order of any element must
> > divide the order of the group.  The group is Z/nZ*.
> > I assume you know how to compute its order?
> > Now ask if n divides its order......
>
> I know that order(Z/pZ*)=p-1, but it is a group only if p is a prime number. I can't see how this leads to solutions of my problem. Thanks anyway! :)
>
> By the meantime I proved that 2^n != 1 (mod n) using Euler's theorem. :D
>
> Chris

The units of Z/nZ form a group as well. i.e. the elements of Z/nZ
that are coprime to n.

However, it was (correctly!) pointed out that one needs a bit more
than what I wrote.

It is not just whether n | phi(n). It is whether (n mod phi(n))
divides phi(n).
From: Bill Dubuque on 4 Nov 2009 10:44
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.

--Bill Dubuque
First  |  Prev  |  Next  |  Last
Pages: 1 2 3 4 5
Prev: Automorphism group of symmetric groups
Next: Reverse Look and Say Sequence