n個の数をa_1,a_2,...,a_nとする。鳩の巣原理より,
　S_0=0
　S_1=a_1
　S_2=a_1+a_2
　S_3=a_1+a_2+a_3
　　　：
　S_n=a_1+a_2+a_3+…+a_n
の(n+1)個の中にnで割ったあまりが同じ2つ, S_iとS_j(i<j)が存在する。よって,
　S_j-S_i=a_(i+1)+a_(i+2)+…+a_j
はnの倍数。

この証明を見ると、「順番が連続するものを選ばなければならない」という条件を付してもいけることがわかりますね。

鳩の巣論理を使う。
仮に、n個の自然数(A1..An)を選んだときに、どの組み合わせの和もnの倍数にならないと仮定したときに、A1,A1+A2,A1+A2+A3,...,A1+A2+A3+...+Anのnに対する剰余は全て異なる値となる。しかし、nには0以外の相異なる剰余はn-1個しかないので矛盾する。

n個の数それぞれについて、nで割った余りの数をx1,x2, ... ,xn と表記する。

・xa=0 となるような数aが含まれている場合、aはnの倍数。
・xa=xb となるような二数a,bが含まれている場合、a-b と b-a はnの倍数。

x1,x2, ... ,xn の値としてあり得る数は、0 から n-1 のn種類である。
これらの数の中には必ず0か同じ数の少なくとも一方が含まれているので、
任意のn個の自然数に対して、そのうちの何個かを選んで和を求めると、
その中にnの倍数となるものが必ず存在する。


この考え方で行けば、選ぶ数字は2個もあればじゅうぶん。

n個の自然数をa1,a2,,,anとし、S1=a1,S2=a1+a2,,,Sn=a1+a2+...+anとする。
S1,S2,,,Snの中にnの倍数があれば成り立つ。
そうでない場合、nで割った余りが同じものが
少なくとも1組あるので、それをSk,Sl(k<l)とする。このときa(k+1)+a(k+2)+...+alはnの倍数である。

・最初の1個
・最初から2個の和
・最初から3個の和
（中略）
・全部の和
のn個の数で
nで割り切れるものがあれば終了
全部nで割り切れない場合、余りは 1,2,…,n-1 のどれか
鳩を虐待する（十分な巣を用意しない）
同じ余りのもの2つの差分を取れば、nで割り切れる和が得られる