On Nov 3, 6:22 pm, 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:
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......
> 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
On Nov 3, 3:39 pm, Pubkeybreaker <pubkeybrea...@aol.com> wrote:
> On Nov 3, 6:22 pm, 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:
> 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.
On Nov 3, 9:08 pm, Christopher Kolago <krzysztof.kol...@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).
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 (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
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.
>> 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)?
>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.
> >> 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?
> 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
>>>> 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
> -- > Gerry Myerson (ge...@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)?
> >>>> 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
