Author |
Topic: Prove a Congruence Without Group Theory (Read 537 times) |
|
ecoist
Senior Riddler
Gender: 
Posts: 405
|
 |
Prove a Congruence Without Group Theory
« on: Dec 31st, 2006, 7:16pm » |
 Quote  Modify
|
Many years ago I read a remarkable proof of the Sylow theorems that had these interesting byproducts:
(G) Let G be a group of order n divisible by pk, for some prime p. Then the number of subgroups of G of order pk (conjugate or not) is congruent to 1 modulo p.
(C) Let C(x,y) be the number of y-subsets of an x-set. let p be a prime and n a positive integer such that pk divides n. Then C(n-1,pk-1) is congruent to 1 modulo p.
(G) was proved by showing that, modulo p, every group of order n has the same number of subgroups of order pk as the cyclic group of order n, which number is, of course, 1. Hence both (G) and (C) follow. What's a proof of (C) without using group theory?
|
|
 IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Prove a Congruence Without Group Theory
« Reply #1 on: Jan 2nd, 2007, 5:46am » |
Quote Modify
|
Lucas's theorem?
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Prove a Congruence Without Group Theory
« Reply #2 on: Jan 3rd, 2007, 3:45am » |
Quote Modify
|
More specifically: use this identity, which may be derived from this.
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Prove a Congruence Without Group Theory
« Reply #3 on: Jan 3rd, 2007, 4:55pm » |
Quote Modify
|
Writing n=qm for some m, where q=pk, we have, mod p,
(1+x)n-1 = (1+x)q-1(1+x)q(m-1) = (1+x)q-1(1+xq)m-1,
and the coefficient of xq-1 on the right is just 1. (The proof of the more general Lucas's theorem is similar.)
Alternatively, C(n-1, q-1) is the product, for 0<i<q, of (n-i)/(q-i). But i = prj, where r<k, so mod p, we have
(n-i)/(q-i) = (mpk-r-j)/(pk-r-j) = (-j)/(-j) = 1.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print