Klasyk podzielnosci

[mol_ksiazkowy]

Dane jest \(\displaystyle{ n}\) różnych liczb całkowitych \(\displaystyle{ a_1,...,a_n}\). Udowodnić, że istnieje \(\displaystyle{ n}\) liczb \(\displaystyle{ e_j \in \{ -1, 0, 1 \}}\) nie wszystkie równe zero, takie, że \(\displaystyle{ e_1a_1+ ...+ e_na_n}\) jest podzielne przez \(\displaystyle{ 2^n-1}\)

[Premislav]

Patrzymy najpierw na takie układy ze współczynnikami
\(\displaystyle{ b_j\in\left\{ 0,1\right\}}\), tj. układy postaci \(\displaystyle{ b_1 a_1+\ldots +b_n a_n}\) dla \(\displaystyle{ b_j\in \left\{ 0,1\right\}}\). Jest \(\displaystyle{ 2^n}\) takich układów, a reszt z dzielenia przez \(\displaystyle{ 2^n-1}\) jest \(\displaystyle{ 2^n-1}\), toteż z Dirichleta któraś reszta się powtórzy. Niech dla ustalonych całkowitych \(\displaystyle{ a_1, \ldots a_n}\) będzie
\(\displaystyle{ b_1^{(1)}a_1+\ldots+b_n^{(1)}a_n\equiv b_1^{(2)}a_1+\ldots+b_n^{(2)}a_n\pmod{2^n-1}}\). Wówczas bierzemy
\(\displaystyle{ e_j=b_j^{(1)}-b_j^{(2)}}\) dla \(\displaystyle{ j=1\ldots n}\) i śmiga, c.k.d.