13/09/01 05:07:42.87
>>351
〔補題〕1≦k≦n-1 とする。
{y_1、y_2、･････、y_k} の部分集合（φも含める）について、要素の和をｎで割ったときの余りを求めると、
(k+1) 種類以上ある。
(略証)
kについての帰納法による。
k=1 のときは φおよび{y_1} の２種があり、成立つ。
k-1 について成立つと仮定する。
{y_1､ ････、y_(k-1)} の部分集合について、要素の和をnで割った余りを求め、
その集合を S_(k-1) とする。つまり、余りは #S_(k-1) 種類ある。
#S_(k-1) = n ならば命題は成立する。
#S_(k-1) < n ならば、上記の部分集合に y_k を加えたものを考える。
nで割った余りは同数｛#S_(k-1) 種類｝だが、
Sum{S_(k-1)~} = Sum{S_(k-1)} + y_k･#S_(k-1),
y_k ≠ 0 (mod n)、 #S_(k-1) ≠ 0 (mod n)、nは素数だから、
y_k･#S_(k-1) ≠ 0 (mod n)
S_(k-1) と S_(k-1)~ は要素の数は同じだが、内容は異なる。
∴ S_(k-1)~ には S_(k-1) にない要素がある。
S_k = S_(k-1) ∪ S_(k-1)~ ⊃ S_(k-1),
#S_k ≧ #S_(k-1) + 1, （略証終）