Қытайдың қалдықтар туралы теоремасы

Қытайдың қалдықтар туралы теоремасы атымен бірнеше ұқсас тұжырымдар белгілі. Бұл теорема арифметикалық түрде қытай математигі Сунь Цзыдың «Сунь Цзы Суань Цзин» трактатында шамамен б.з. үшінші ғасырда сипатталған.

Егер

a_{1},a_{2},\dots ,a_{n}

натурал сандары өзара жай болса, онда барлық

i=1,2,\dots ,n

үшін

0\leq r_{i}<a_{i}

болатындай кез келген

r_{1},r_{2},\dots ,r_{n}

үшін кез келген

i=1,2,\dots ,n

үшін

\,a_{i}

санына бөлгенде

\,r_{i}

қалдық беретіндей

\,N

саны табылады. Тіпті егер осындай екі

\,N_{1}

мен

\,N_{2}

сандары табылса, онда

N_{1}\equiv N_{2}(\mathrm {mod} \,a_{1}\cdot \ldots \cdot a_{n})

.

Дәлелдеу

$n$ бойынша индукцияны пайдаланайық. $n=1$ үшін тұжырымдама ақиқаттығы айқын. $n=k-1$ үшін теорема орындалсын, яғни $i=1,2,\dots ,k-1$ үшін $a_{i}$ -ге бөлгенде $r_{i}$ қалдық беретіндей $M$ саны табылады. Келесідей белгілейік

d=a_{1}a_{2}\cdots a_{k-1}

сосын $M,M+d,M+2d,\dots ,M+(a_{k}-1)d$ сандарын қарастырайық. Осы сандардың кем дегенде біреуі $a_{k}$ санына бөлгенде $r_{k}$ қалдық беретінін көрсетейік. Қарсы жориық, ондай сан табылмасын. Сандар саны $a_{k}$ , ал $a_{k}$ санына бөлгендегі барлық әр түрлі қалдықтар саны $a_{k}-1$ санынан аспағандықтан (себебі еш сан $r_{k}$ қалдық бере алмайды), онда олардық арасында бірдей қалдық беретін екеуі табылады(Дирихле принципі). Бұл сына $M+sd$ және $M+td$ сандары болсын, мұндағы $0\leq s\leq a_{k}-1$ , $0\leq t\leq a_{k}-1$ және $s\neq t$ . Онда олардың $(M+sd)-(M+td)=(s-t)d$ айырмасы $a_{k}$ санына бөлінеді, бұл $0<|s-t|<a_{k}$ және $d=a_{1}a_{2}\cdots a_{k-1}$ өзара $a_{k}$ санымен жай болғандықтан мүмкін емес, себебі $a_{1},a_{2},\dots ,a_{k}$ жұп жұбымен өзара жай сандар (есеп шарты бойынша). Қарама қайшылық.

Сонымен берілген сандар арасында N саны a_k санына бөлгенде _{r_k} қалдық беретіндей табылады. Оның үстіне

a_{1},a_{2},\dots ,a_{k-1}

сандарына N санын бөлгенде сәйкесінше :

r_{1},r_{2},\dots ,r_{k-1}

қалдықтарын береді.

Енді $N_{1}\equiv N_{2}(\mathrm {mod} \,N)$ екендігін дәлелдейік. Шыныменде $N_{1}\equiv N_{2}\equiv r_{i}(\mathrm {mod} \,a_{i})$ , демек $N_{1}-N_{2}\equiv 0(\mathrm {mod} \,a_{i})$ . Барлық $a_{i}$ өзара жай болғандықтан $N_{1}-N_{2}$ олардың көбейтіндісіне бөлінеді. Дәлелдеу керектігі осы.