Prev: Automorphism group of symmetric groups
Next: Reverse Look and Say Sequence
From: Achava Nakhash, the Loving Snake on 4 Nov 2009 23:29
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 (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.


Regards,
Achava
From: William Elliot on 5 Nov 2009 04:30
On Wed, 4 Nov 2009, Bill Dubuque wrote:

> 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.
>
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)

From: Bill Dubuque on 5 Nov 2009 09:21
William Elliot <marsh(a)rdrop.remove.com> wrote:
> On Wed, 4 Nov 2009, Bill Dubuque wrote:
>> 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.
>>
> Why is (a-1, n) = 1 needed?
> I see that a /= 1 (mod p) is needed instead. [...]

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
From: Bill Dubuque on 5 Nov 2009 10:08
"Achava Nakhash, the Loving Snake" <achava(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 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.
From: master1729 on 5 Nov 2009 04:25
> 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)

or maybe factorial 2^n (mod n) is intended ?

or something else ?
First  |  Prev  |  Next  |  Last
Pages: 1 2 3 4 5
Prev: Automorphism group of symmetric groups
Next: Reverse Look and Say Sequence