Why does 2^n != 1 (mod n) is true for every n > 1?
Christopher Kolago
2^n != 1 (mod n)
for every n > 1? Is there any "simple" proof of this fact?
Chris
Pubkeybreaker
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......
master1729
lol
how is 2^2n ! = 1 mod 2n ?
Christopher Kolago
>
> 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
Christopher Kolago
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
Gerry Myerson
<1147769809.5653.12572...@gallium.mathforum.org>,
Christopher Kolago <krzyszto...@uj.edu.pl> wrote:
1972 Putnam Exam, problem A-5.
See discussion in this newsgroup, under the heading
"Divisibility problem," 27 to 30 May 2005.
--
Gerry Myerson (ge...@maths.mq.edi.ai) (i -> u for email)
Achava Nakhash, the Loving Snake
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
William Elliot
>>> 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.
Pubkeybreaker
wrote:
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).
Bill Dubuque
>
> 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
Achava Nakhash, the Loving Snake
> Christopher Kolago <krzysztof.kol...@uj.edu.pl> wrote:
>
> > Is there any "simple" proof of this fact?
>
>
> 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
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
William Elliot
Why is (a-1, n) = 1 needed?
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)
Bill Dubuque
> On Wed, 4 Nov 2009, Bill Dubuque wrote:
>> Christopher Kolago <krzyszto...@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?
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
Bill Dubuque
> On Nov 4, 7:44�am, Bill Dubuque <w...@nestle.csail.mit.edu> wrote:
>> Christopher Kolago <krzysztof.kol...@uj.edu.pl> wrote:
>>>
>>
>>
>> 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)
>>
>
> 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)?
master1729
2^5 = 2 (mod 5)
2^7 = 2 (mod 7)
or maybe factorial 2^n (mod n) is intended ?
or something else ?
Pubkeybreaker
> > 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.
master1729
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
> "Achava Nakhash, the Loving Snake" <ach...@hotmail.com> writes:
>
>
>
>
>
> > On Nov 4, 7:44 am, Bill Dubuque <w...@nestle.csail.mit.edu> wrote:
> >> Christopher Kolago <krzysztof.kol...@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.
>
> 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
master1729
btw :
2^15 = 8 (mod 15) not 1 (mod 15)
still not convinced ?!?!?!?
tommy1729
Bill Dubuque
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
> On Nov 5, 7:08�am, Bill Dubuque <w...@nestle.csail.mit.edu> wrote:
>> "Achava Nakhash, the Loving Snake" <ach...@hotmail.com> writes:
>>> On Nov 4, 7:44�am, Bill Dubuque <w...@nestle.csail.mit.edu> wrote:
>>>> Christopher Kolago <krzysztof.kol...@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.
>>
>
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
Gerry Myerson
<c471b166-ee82-4c7c...@b36g2000prf.googlegroups.com>,
"Achava Nakhash, the Loving Snake" <ach...@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, ....
Achava Nakhash, the Loving Snake
wrote:
> In article
> <c471b166-ee82-4c7c-96bb-ad30d11de...@b36g2000prf.googlegroups.com>,
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
master1729
hahaha me too.
they didnt fool me a second !!