|
||
|
Title: Prove a Congruence Without Group Theory Post by ecoist on Dec 31st, 2006, 7:16pm 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? |
||
|
Title: Re: Prove a Congruence Without Group Theory Post by Barukh on Jan 2nd, 2007, 5:46am [hide]Lucas's theorem?[/hide] |
||
|
Title: Re: Prove a Congruence Without Group Theory Post by Barukh on Jan 3rd, 2007, 3:45am More specifically: use this identity (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_putnam;action=display;num=1139008533;start=2#2), which may be derived from this (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_putnam;action=display;num=1135363189;start=6#6). |
||
|
Title: Re: Prove a Congruence Without Group Theory Post by Eigenray on Jan 3rd, 2007, 4:55pm 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. |
||
|
Powered by YaBB 1 Gold - SP 1.4! Forum software copyright © 2000-2004 Yet another Bulletin Board |