 |
|
| Science Forum Index » Mathematics Forum » Why does 2^n != 1 (mod n) is true for every n > 1?... |
|
Page 1 of 2 Goto page 1, 2 Next |
|
| Author |
Message |
| Christopher Kolago... |
 Posted: Tue Nov 03, 2009 1:22 pm |
|
|
|
Guest
|
Why does:
2^n != 1 (mod n)
for every n > 1? Is there any "simple" proof of this fact?
Chris |
|
|
| Back to top |
|
|
|
| master1729... |
| Posted: Tue Nov 03, 2009 1:30 pm |
|
|
|
Guest
|
[quote]Why does:
2^n != 1 (mod n)
for every n > 1? Is there any "simple" proof of this
fact?
Chris
[/quote]
lol
how is 2^2n ! = 1 mod 2n ? |
|
|
| Back to top |
|
|
|
| Pubkeybreaker... |
| Posted: Tue Nov 03, 2009 1:39 pm |
|
|
|
Guest
|
On Nov 3, 6:22�pm, Christopher Kolago <krzysztof.kol... at (no spam) uj.edu.pl>
wrote:
[quote]Why does:
2^n != 1 (mod n)
for every n > 1? Is there any "simple" proof of this fact?
[/quote]
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...... |
|
|
| Back to top |
|
|
|
| Christopher Kolago... |
| Posted: Tue Nov 03, 2009 4:08 pm |
|
|
|
Guest
|
[quote]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......
[/quote]
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 |
|
|
| Back to top |
|
|
|
| Christopher Kolago... |
| Posted: Tue Nov 03, 2009 4:14 pm |
|
|
|
Guest
|
[quote]Why does:
2^n != 1 (mod n)
for every n > 1? Is there any "simple" proof of
this
fact?
Chris
lol
how is 2^2n ! = 1 mod 2n ?
[/quote]
Is wish it was so easy, but it's not. ;P
In the meantime I managed to prove that 2^n != 1 (mod n) using the Euler's theorem.
Chris |
|
|
| Back to top |
|
|
|
| Achava Nakhash, the Loving Snake... |
| Posted: Tue Nov 03, 2009 6:54 pm |
|
|
|
Guest
|
On Nov 3, 3:39 pm, Pubkeybreaker <pubkeybrea... at (no spam) aol.com> wrote:
[quote]On Nov 3, 6:22 pm, 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:
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......
[/quote]
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 |
|
|
| Back to top |
|
|
|
| Gerry Myerson... |
| Posted: Tue Nov 03, 2009 9:22 pm |
|
|
|
Guest
|
In article
<1147769809.5653.1257290602852.JavaMail.root at (no spam) gallium.mathforum.org>,
Christopher Kolago <krzysztof.kolago at (no spam) uj.edu.pl> wrote:
[quote]Why does:
2^n != 1 (mod n)
for every n > 1? Is there any "simple" proof of this fact?
[/quote]
1972 Putnam Exam, problem A-5.
See discussion in this newsgroup, under the heading
"Divisibility problem," 27 to 30 May 2005.
--
Gerry Myerson (gerry at (no spam) maths.mq.edi.ai) (i -> u for email) |
|
|
| Back to top |
|
|
|
| Pubkeybreaker... |
| Posted: Wed Nov 04, 2009 2:24 am |
|
|
|
Guest
|
On Nov 3, 9:08 pm, Christopher Kolago <krzysztof.kol... at (no spam) uj.edu.pl>
wrote:
[quote]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
[/quote]
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). |
|
|
| Back to top |
|
|
|
| William Elliot... |
| Posted: Wed Nov 04, 2009 5:30 am |
|
|
|
Guest
|
On Tue, 3 Nov 2009, Christopher Kolago wrote:
[quote]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.
[/quote]
Then show us. |
|
|
| Back to top |
|
|
|
| Bill Dubuque... |
| Posted: Wed Nov 04, 2009 10:44 am |
|
|
|
Guest
|
Christopher Kolago <krzysztof.kolago at (no spam) uj.edu.pl> wrote:
[quote]
Why does: 2^n != 1 (mod n) for every n > 1?
Is there any "simple" proof of this fact?
[/quote]
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 |
|
|
| Back to top |
|
|
|
| Achava Nakhash, the Loving Snake... |
| Posted: Wed Nov 04, 2009 6:29 pm |
|
|
|
Guest
|
On Nov 4, 7:44 am, Bill Dubuque <w... at (no spam) nestle.csail.mit.edu> wrote:
[quote]Christopher Kolago <krzysztof.kol... at (no spam) uj.edu.pl> wrote:
Why does: 2^n!= 1 (modn) for everyn> 1?
Is there any "simple" proof of this fact?
HINT the least prime p|ncannot also divide 2^n- 1 since
THEOREM prime p|(n, 2^n- 1) => (n,p-1) > 1 => prime q|nfor q<p
PROOF 1 = 2^n= 2^(p-1) => 1 = 2^(n,p-1) (modp)
The theorem generalizes to a^n- 1 for (a-1,n) = 1.
--Bill Dubuque
[/quote]
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. If p is the smallest prime dividing p, then (p-1) is a
factor of phi(n) - trivial observation from well-known properties of
the phi function, and so it can be neither a factor of p nor of any
primes larger than p, and hence not of n.
Regards,
Achava |
|
|
| Back to top |
|
|
|
| William Elliot... |
| Posted: Thu Nov 05, 2009 4:30 am |
|
|
|
Guest
|
On Wed, 4 Nov 2009, Bill Dubuque wrote:
[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.
Why is (a-1, n) = 1 needed?[/quote]
I see that a /= 1 (mod p) is needed instead.
Propostion. a,n in N, prime p | (n, a^n - 1)
==> 1 < (n, p-1)
==> some prime q < p with q | n
Proof.
a,p coprime. Otherwise: p | a; 1 = a^n = 0 (mod p).
1 = a^n = a^(p-1) (mod p)
some r,s in Z with rn + s(p-1) = (n, p-1)
1 = a^rn a^s(p-1) = a^(n, p-1) (mod p)
If (n, p-1) = 1, then a = 1 (mod p).
Thus to conclude 1 < (n, p-1), a /= 1 (mod p) is required.
Why is (n, a-1) needed?
Propostion. a,n in N, prime p | (n, a^n - 1), a /= 1 (mod p)
==> 1 < (n, p-1)
==> some prime q < p with q | n
Lemma. n,m in N, prime p, a^n = a^m = 1 (mod p) ==> a^(n,m) = 1 (mod p) |
|
|
| Back to top |
|
|
|
| Bill Dubuque... |
| Posted: Thu Nov 05, 2009 9:21 am |
|
|
|
Guest
|
William Elliot <marsh at (no spam) rdrop.remove.com> wrote:
[quote]On Wed, 4 Nov 2009, Bill Dubuque wrote:
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.
Why is (a-1, n) = 1 needed?
I see that a /= 1 (mod p) is needed instead. [...]
[/quote]
Because (n,a-1) = 1 => (p,a-1) = 1 for ALL p|n.
Thus it provides a criterion independent of p.
There is no need to give a separate proof.
Simply proceed as above and instead conclude
(n,p-1) = 1 => p | a^(n,p-1)-1 = a-1 =><=
--Bill Dubuque |
|
|
| Back to top |
|
|
|
| master1729... |
| Posted: Thu Nov 05, 2009 9:25 am |
|
|
|
Guest
|
[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.
[/quote]
2^5 = 2 (mod 5)
2^7 = 2 (mod 7)
or maybe factorial 2^n (mod n) is intended ?
or something else ? |
|
|
| Back to top |
|
|
|
| Bill Dubuque... |
| Posted: Thu Nov 05, 2009 10:08 am |
|
|
|
Guest
|
"Achava Nakhash, the Loving Snake" <achava at (no spam) hotmail.com> writes:
[quote]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.
[/quote]
Precisely how do you conclude the proof from that?
Are you presuming that 2 has order phi(n) (mod n)?
[quote]If p is the smallest prime dividing p, then (p-1) is a
factor of phi(n) - trivial observation from well-known properties of
the phi function, and so it can be neither a factor of p nor of any
primes larger than p, and hence not of n.[/quote] |
|
|
| Back to top |
|
|
|
|
|
All times are GMT - 5 Hours
The time now is Fri Nov 27, 2009 6:14 pm
|
|