Tübitak Lise 2. Aşama 1995 Soru 1

[Lokman Gökçe]

$m_{1},m_{2}, \ldots ,m_{k}$, $2\le m_{1}$ ve $2m_{i}\le m_{i+1}$ $(i=1,2,\ldots ,k-1)$ koşullarını sağlayan tamsayılar olsun. Bu durumda, $a_{1},a_{2},\ldots ,a_{k}$ tamsayılar olmak üzere $$\begin{array}{rcl} x &\equiv& a_{1} \pmod {m_{1}}\\ x &\equiv& a_{2} \pmod {m_{2}}\\ &\vdots& \\ x &\equiv& a_{k} \pmod {m_{k}} \end{array}$$ bağıntılarından hiçbirini gerçeklemeyen sonsuz sayıda $x$ tamsayısının bulunduğunu gösteriniz.

[geo]

$M = m_1m_2 \cdots m_k$ olsun. $1,2,\dots, M$ kümesinin elemanlarından
$\dfrac {M}{m_1}$ tanesi $x \equiv a_1 \pmod {m_1}$ denkliğini sağlar.

$\dfrac {M}{m_2}$ tanesi $x \equiv a_2 \pmod {m_2}$ denkliğini sağlar.

$\vdots$

$\dfrac {M}{m_k}$ tanesi $x \equiv a_k \pmod {m_k}$ denkliğini sağlar.

$1,2,\dots, M$ kümesinin elemanlarından en az bir denkliği sağlayanların sayısı $S$ olsun.

$$S \leq \sum\limits_{i=1}^k \dfrac M{m_i} \leq M \cdot \sum\limits_{i=1}^k \dfrac 1{m_1 \cdot 2^{i-1}} = \dfrac {M}{m_1}\left (1 + \dfrac 12 + \dfrac 14 + \dots + \dfrac 1{2^{k-1}}\right) < \dfrac {2M}{m_1} \leq M$$ Bu durumda $S<M$ elde edildiği için $1,2,\dots, M$ kümesinden en az bir eleman denkliklerin hiçbirini sağlamaz. Bu elemana $x_0$ dersek, $i=0,1,2,\dots$ için $x_i = M\cdot i + x_0$ sayılarından hiçbiri denklikleri sağlamayacak. $\blacksquare$