Teorema kineze mbi mbetjen

Teorema kineze mbi mbetjen

Teorema kineze mbi mbetjen , e quajtur sipas trashëgimisë kineze të problemeve që përfshijnë sistemet e kongruencave lineare, thotë se kur moduli i një sistemi kongruencash lineare janë çifte relativisht të thjeshta, ekziston një zgjidhje unike e sistemit modulo të produktit të modulit. Teorema e ka origjinën në kohën e matematikanit kinez të shekullit të III-të pas Krishtit Sun Zi, megjithëse teorema e plotë u dha për herë të parë në 1247 nga Qin Jiushao. Në shekullin e parë, matematikani kinez Sun-Tsu pyeti: Ka disa gjëra, numri i të cilave nuk dihet. Nje numer i plote kur pjestohet me 3 mbetja është 2, kur pjesëtohet me 5 mbetja është 3, dhe kur pjesëtohet me 7 mbetja është 2. Çfarë do të jetë numri i gjërave? Kjo enigmë mund të përkthehet në pyetjen e mëposhtme: Cilat janë zgjidhjet e sistemit të kongruencave ? ${\begin{aligned}x&\equiv 2{\pmod {3}}\end{aligned}}$

${\begin{aligned}x&\equiv 3{\pmod {5}}\end{aligned}}$

${\begin{aligned}x&\equiv 2{\pmod {7}}\end{aligned}}$

Këtë sistem të kongruencave do ta zgjidhim me teoremën kineze.

Teorema 1-Teorema kineze mbi mbetjen: Le të jenë $m_{1}$,$m_{2}$, ..., $m_{n}$ numra të plotë pozitivë dy nga dy relativisht të thjeshtë më të mëdhenj se një dhe $a_{1}$,$a_{2}$,...,$a_{n}$ numra të plotë arbitrar.Atëherë sistemi:

${\begin{aligned}x&\equiv a_{1}{\pmod {m_{1}}}\end{aligned}}$

${\begin{aligned}x&\equiv a_{2}{\pmod {m_{2}}}\end{aligned}}$

${\begin{aligned}x&\equiv a_{n}{\pmod {m_{n}}}\end{aligned}}$

ka një zgjidhje unike modul m = m1×m2×...×mn ;d.m.th., ekziston një zgjidhje x,0 ≤ x<m, dhe të gjitha zgjidhjet e tjera janë kongruente modul m me këtë zgjidhje.

Prova e Teoremes 1 Për të vendosur këtë teoremë, duhet të tregojmë se ekziston një zgjidhje dhe se ajo është unike modul m. Ne do të tregojmë se ekziston një zgjidhje duke përshkruar një mënyrë për të ndërtuar këtë zgjidhje; Për të ndërtuar një zgjidhje të njëkohshme, fillimisht le të jetë: $M_{k}=m/m_{k}$ për k=1,2,...n. Domethënë,$M_{k}$ është prodhimi i modulit përveç $m_{k}$. Sepse $m_{i}$ dhe $m_{k}$ nuk kanë faktorë të përbashkët më të mëdhenj se 1 kur i ≠ k, rrjedh se gcd($m_{k}$,$M_{k}$) = 1. Rrjedhimisht, nga teorema 1, ne e dimë se ekziston një numër i plotë $y_{k}$, një invers i $M_{k}$ modul $m_{k}$, si p.sh. M_ky_k&\equiv 1 \pmod {m_k} Për të ndërtuar një zgjidhje të njëkohshme, formojme shumën: $x=a_{1}M_{1}y_{1}+a_{2}M_{2}y_{2}+...+a_{k}M_{k}y_{k}$ Shohim qe : x ≡ $a_{k}M_{k}y_{k}=a_{k}{\pmod {m_{k}}}$ Për k=1,2,...,n. Ne kemi treguar që x është një zgjidhje e vetme e n kongurencave .

Shembulli 1. Do të zgjidhim sistemin e kongruencave të dhëna më lartë.

${\begin{aligned}x&\equiv 2{\pmod {3}}\\x&\equiv 3{\pmod {5}}\\x&\equiv 2{\pmod {7}}.\end{aligned}}$

Fillimisht le të jetë m=3×5×7=105 Atehere: $M_{1}$=m/3 kështu që $M_{1}$=35 ; $M_{2}$=m/5 kështu që $M_{2}$=21 dhe $M_{3}$=m/7 kështu që $M_{3}$=15 Ne shohim që 2 është një invers i $M_{1}$ = 35 modul 3,sepse 35 · 2 ≡ 2 · 2 ≡ 1 (mod 3); 1 është një invers i $M_{2}$ = 21 modul 5, sepse 21 ≡1 (mod 5); dhe 1 është një invers i $M_{3}$ = 15 (mod 7), sepse 15 ≡ 1 (mod 7). Zgjidhjet për ketë sistem janë ato x të tillë që:

${\begin{aligned}x=a_{1}M_{1}y_{k}+a_{2}M_{2}y_{2}+a_{3}M_{3}y_{3}=140+63+30=233\end{aligned}}$

${\begin{aligned}x&\equiv 23{\pmod {105}}.\end{aligned}}$

https://www.britannica.com/science/Chinese-remainder-theorem