Kineska teorema o ostacima

Kineska teorema o ostacima precizno glasi ovako:

Neka su $m_1,\dots,m_k$ prirodni brojevi koji su u parovima uzajamno prosti i neka su $b_1,\dots,b_k$ celi brojevi za koje je $0\leq b_i<a_i$ za sve $i\in\{1,\dots,k\}$ . Tada postoji tačno jedan ceo broj $0\leq a<m=m_1\cdots m_k$ takav da je $a\equiv_{m_i}b_i$ za sve $i\in\{1,\dots,k\}$ , pr čemu simbol $\equiv_n$ predstavlja kongruenciju po modulu $n$ .

Neka je $\displaystyle m_i^*=\prod_{j\neq i}m_j$ . Budući da je $m_i$ uzajamno prost sa $m_j$ za svako $j\neq i$ , $m_i$ je uzajamno prost i sa njihovim proizvodom $m_i^*$ , pa postoje celi nenegativni brojevi $u_i$ i $v_i$ za koje je $u_im_i+v_im_i^*=1$ . To, tačno znači da je $v_im_i^*\equiv_{m_i}1$ , a samim tim i da za broj $\displaystyle c=\sum_{i=1}^kb_iv_im_i^*$ važi $c\equiv_{m_i}b_i$ za sve $i\in\{1,\dots,k\}$ . Ako sada uzmemo da je $a$ nenegativan ostatak pri delenju broja $c$ sa $m$ , broj $a$ će ispuniti tražene uslove. Time je dokazana egzistencija.

Ako bi još neki element $a'$ ispunio tra\ene uslove, onda bi broj $|a-a'|$ bio deljiv sa $m_i$ za svako $i\in\{1,\dots,k\}$ , a samim tim i sa njihovim proizvodom $m$ budući da su brojevi $m_i$ u parovima uzajamno prosti. No, iz $0\leq a,a'<m$ sledi da je $|a-a'|<m$ , odakle najzad mora biti $|a-a'|=0$ čime je dokazana jedinstvenost.

Ova teorema se primenjuje u Algebri u teoriji konačnih Abelovih grupa, kao i u Logici u dokazu Gedelovih teorema nepotpunosti.

Potpis

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

Forum kao aplikacija na telefonu

Srodne teme