Aritmetika modulare

Në matematikë dhe më konkretisht në teorinë e numrave algjebrikë, aritmetika modulare është një grup metodash për zgjidhjen e problemeve që përfshijnë numra të plotë. Këto metoda rrjedhin nga studimi i pjesës së mbetur të marrë nga një ndarje Euklidiane. Ideja themelore e aritmetikës modulare është të punohet jo në vetë numrat, por në pjesën e mbetur të ndarjes së tyre me diçka.

Megjithëse origjina e tij shkon prapa në antikitet, historianët në përgjithësi e lidhin lindjen e tij me vitin 1801, datën e botimit të librit Disquisitiones arithmeticae nga Carl Friedrich Gauss. Qasja e tij e re bën të mundur sqarimin e hamendjeve të famshme, si ligjin e reciprocitetit kuadratik, dhe thjeshton provat e rezultateve të rëndësishme me një abstraksion më të madh, si në rastin e teoremës së vogël të Fermat-it. Edhe pse fusha natyrore e këtyre metodave është teoria e numrave, aplikimet e ideve të Gausit mund të gjenden edhe në fusha të tjera të matematikës, si algjebra ose gjeometria.

Shekulli i XX-të e ndryshon statusin e aritmetikës modulare. Nga njëra anë, nevojiten metoda të tjera për të përparuar në teorinë e numrave. Nga ana tjetër, zhvillimi i shumë aplikacioneve industriale kërkon zhvillimin e algoritmeve nga teknikat modulare pasi që ato zgjidhin në thelb pyetjet që kanë lindur në teorinë e informacionit, një degë që aktualisht konsiderohet, mbi të gjitha, si matematikë e aplikuar.

Një përdorim i njohur i aritmetikës modulare për të gjithë ne është ora analoge (ora 12-orëshe). Në orën analoge nëse krahu i orës në një çast të caktuar tregon orën 7:00, atëhere pas 8 orëve krahu do t'a tregojë orën 3:00. Ne dijmë se shuma e 7 dhe 8 rezulton në 15, por pasi që ora analoge është një shembull i aritmetikës me modulo 12, (pra, rangu i numrave është i përcaktuar nga 1 deri në 12) atëhere nëse vlera tejkalon modulin, siç u cek mësipër, shifrat përsëriten. Në këtë rast, themi se 15 është kongruent me 3 mod 12, apo ndryshe, ora "15:00" në një orë digjitale (24-orëshe) është e njëjtë me orën 3:00 në një orë analoge.

Kongruenca dhe numrat e plotë

Definicion

Numrat a dhe b themi se kanë të njëjtën "klasë kongruence", me modul n, apo janë kongruentë, nëse të dy lënë të njëjtën mbetje kur pjestohen me n, ose, në mënyrë ekuivalente, nëse ndryshimi i a dhe b është shumëfish i n.

Kongruenca modulo n paraqet një relacion të ekuivalencës që zbaton veprimet si mbledhja, zbritja dhe shumëzimi dhe shënohet si më poshtë:

a\equiv b{\pmod {n}.

Kllapat nënkuptojnë se (mod n) vlen për të gjithë ekuacionin, dhe jo vetëm për njërën anë të ekuacionit. Duhet të dallojmë notacionin $b mod n$ (pa kllapa), e cila paraqet veprimin modulo që në të vërtetë tregon një numër të veçantë $a$ të atillë që $0 \leq a < n$ dhe $a\equiv b\;({\text{mod}\;n)$ (pra, mbetja e $b$ kur pjestohet me $n$ )

Shembuj

Shembulli 1.

$63\equiv 83{\pmod {10$

pasi që edhe 63 edhe 83 lënë të njëjtën mbetje (3) kur pjesëtohen me 10, ose, në mënyrë ekuivalente, 63 − 83 është shumëfish i 10. Lexohet:

« 63 është kongruentë me 83, në modul 10 »,

« në modulin 10, 63 dhe 83 janë kongruentë », ose

« 63 dhe 83 janë kongruentë me njëri-tjetrin, në modul 10 ».

Shembull 2.

Në modulo 12, mund të vërtetojmë se:

38\equiv 14{\pmod {12

sepse $38 - 14 = 24$ , dhe 24 është shumëfish i 12. Një mënyrë tjetër e shprehjes së kësaj kongruence do të ishte që të thuhet se secila, pra, edhe 38, edhe 24, kur pjesëtohen me 12, kanë mbetjen 2.

Definicioni i kongruencës ka vlevshmëri edhe për vlerat negative. Si për shembull:

{\begin{aligned}2&\equiv -3{\pmod {5}\\-8&\equiv 7{\pmod {5}\\-3&\equiv -8{\pmod {5}.\end{aligned

Disa veti

Relacioni i kongruencës kënaq të tria kushtet e relacionit të ekuivalencës

Vetia refleksive: $a \equiv a (mod n)$
Vetia e simetrisë: $a \equiv b (mod n)$ nëse $b \equiv a (mod n)$ për çdo $a$ , $b$ , dhe $n$ .
Vetia transitive: Nëse $a \equiv b (mod n)$ dhe $b \equiv c (mod n)$ , atëhere $a \equiv c (mod n)$

Nëse $a 1 \equiv b 1 (mod n)$ dhe $a 2 \equiv b 2 (mod n),$ ose nëse $a \equiv b (mod n),$ atëhere:^[1]

$a + k \equiv b + k (mod n)$ për çdo $k\in \mathbb {Z}$ (përputhshmëria me përkthimin)
$k a \equiv k b (mod n)$ për çdo $k\in \mathbb {Z}$ (përputhshmëria me shkallëzimin)
$a 1 + a 2 \equiv b 1 + b 2 (mod n)$ (përputhshmëria me mbledhjen)
$a 1 - a 2 \equiv b 1 - b 2 (mod n)$ (përputhshmëria me zbritjen)
$a 1 a 2 \equiv b 1 b 2 (mod n)$ (përputhshmëria me shumëzimin)
$a k \equiv b k (mod n)$ për çdo $k\in \mathbb {Z}$ dhe $k>0$ (përputhshmëria me fuqizimin)
$p (a) \equiv p (b) (mod n)$ , për çdo polinom $p (x)$ me koeficientët $k_{n}\in \mathbb {Z}$ (përputhshmëria me vlerësimin polinomial)

Për eliminimin e gjymtyrëve të përbashkëta, përdorim rregullat e mëposhtme:

Nëse $a + k \equiv b + k (mod n)$ , për çdo $k\in \mathbb {Z}$ , atëhere $a \equiv b (mod n)$
Nëse $k a \equiv k b (mod n)$ dhe $k$ është relativisht e thjeshtë me $n$ , atëhere $a \equiv b (mod n)$
Nëse $k a \equiv k b (mod kn)$ , atëhere $a \equiv b (mod n)$

Klasat e kongruencës

Ashtu si çdo relacion i kongruencës, modulo $n$ i kongruencës është një relacion i ekuivalencës, dhe klasa e ekuivalencës së numrit të plotë $a$ , e shënuar me ${\bar {a}_{n$ , është bashkësia ${\dots , a - 2 n, a - n, a, a + n, a + 2 n, \dots}$ . Ky grup, i përbërë nga të gjithë numrat e plotë kongruentë me një modul $n$ , quhet klasa e kongruencës, klasa e mbetjes ose thjesht mbetje e numrit të plotë $a$ modulo $n$ . Kur moduli $n$ njihet nga konteksti, ajo mbetje mund të shënohet gjithashtu si $[a]$ .

Zbatimet

Në matematikën teorike, aritmetika modulare është një nga themelet e teorisë së numrave, duke prekur pothuajse çdo aspekt të studimit të saj, dhe përdoret gjithashtu gjerësisht në teorinë e grupeve, teorinë e unazave, teorinë e nyjeve dhe algjebrën abstrakte. Në matematikën e aplikuar, përdoret në algjebër kompjuterike, kriptografi, shkenca kompjuterike, kimi dhe artet pamore dhe muzikore.^[2]

Një aplikim shumë praktik është llogaritja e shumave kontrolluese brenda identifikuesve të numrave serialë. Për shembull, Numri Standard Ndërkombëtar i Librit (ISBN) përdor aritmetikën e modulit 11 (për ISBN me 10 shifra) ose modulin 10 (për ISBN me 13 shifra) për zbulimin e gabimeve. Po kështu, Numrat Ndërkombëtarë të Llogarisë Bankare (IBAN), për shembull, përdorin aritmetikën modul 97 për të dalluar gabimet e hyrjes së përdoruesit në numrat e llogarive bankare. Në kimi, shifra e fundit e numrit të regjistrit CAS (një numër unik identifikues për çdo përbërje kimike) është një shifër kontrolluese, e cila llogaritet duke marrë shifrën e fundit të dy pjesëve të para të numrit të regjistrit CAS shumëfish 1, shifra e mëparshme. herë 2, shifra e mëparshme 3, etj., duke i mbledhur të gjitha këto dhe duke llogaritur modulin e shumës 10.

Në algjebrën kompjuterike, aritmetika modulare përdoret zakonisht për të kufizuar madhësinë e koeficientëve të numrave të plotë në llogaritjet dhe të dhënat e ndërmjetme. Përdoret në faktorizimin polinomial, një problem për të cilin të gjitha algoritmet e njohura efikase përdorin aritmetikë modulare. Përdoret nga zbatimet më efikase të pjesëtuesit më të madh të përbashkët polinom, algjebër lineare ekzakte dhe algoritme bazë Gröbner mbi numrat e plotë dhe numrat racionalë. Siç u postua në Fidonet në vitet 1980 dhe u arkivua në Rosetta Code, aritmetika modulare u përdor për të hedhur poshtë hamendjen e shumës së fuqive të Euler-it në një mikrokompjuter QL Sinclair duke përdorur vetëm një të katërtën e saktësisë së numrit të plotë të përdorur nga një superkompjuter CDC 6600 për ta hedhur poshtë atë dy dekada më parë. nëpërmjet një kërkimi me "brute force".^[3]

Në kriptografi, aritmetika modulare mbështet drejtpërdrejt sistemet e çelësave publikë si RSA dhe Diffie-Hellman, dhe ofron fusha të fundme që qëndrojnë në themel të kthesave eliptike dhe përdoret në një sërë algoritmesh kyçe simetrike duke përfshirë Standardin e Enkriptimit të Avancuar (AES), Algoritmin Ndërkombëtar të Kriptimit të të Dhënave (IDEA), dhe RC4. RSA dhe Diffie-Hellman përdorin fuqizimin modular.

Në shkencën kompjuterike, aritmetika modulare shpesh aplikohet në operacione bitwise dhe operacione të tjera që përfshijnë struktura ciklike të të dhënave me gjerësi fikse. Veprimi modulo, siç zbatohet në shumë gjuhë programimi dhe kalkulatorë, është një aplikim i aritmetikës modulare që përdoret shpesh në këtë kontekst. Operatori logjik XOR mbledh 2 bit, moduli 2.

Aritmetika me modulo 7 përdoret në algoritme që përcaktojnë ditën e javës për një datë të caktuar. Në veçanti, kongruenca e Zeller-it dhe algoritmi i Doomsday përdorin shumë aritmetikën modulo-7.

Në përgjithësi, aritmetika modulare ka aplikim edhe në disiplina të tilla si ligji (p.sh., ndarja), ekonomia (p.sh., teoria e lojës) dhe fusha të tjera të shkencave sociale, ku ndarja proporcionale dhe shpërndarja e burimeve luan një pjesë qendrore të analizës.

Referime

Preview of references

^ Lehoczky, Sandor; Rusczky, Richard (1 janar 1995). The Art of Problem Solving vol. 1 (në anglisht). Greater Testing Concepts. fq. 44. ISBN 0977304566.
^ Lynch, Peter (2 nëntor 2017). "Modular arithmetic: you may not know it but you use it every day". The Irish Times (në anglisht).{cite web}: Mirëmbajtja CS1: Gjendja e adresës (lidhja)
^ "Euler's sum of powers conjecture". rosettacode.org (në anglisht). Marrë më 2022-01-30.{cite web}: Mirëmbajtja CS1: Gjendja e adresës (lidhja)

[1] Lehoczky, Sandor; Rusczky, Richard (1 janar 1995). The Art of Problem Solving vol. 1 (në anglisht). Greater Testing Concepts. fq. 44. ISBN 0977304566.

[2] Lynch, Peter (2 nëntor 2017). "Modular arithmetic: you may not know it but you use it every day". The Irish Times (në anglisht).{cite web}: Mirëmbajtja CS1: Gjendja e adresës (lidhja)

[3] "Euler's sum of powers conjecture". rosettacode.org (në anglisht). Marrë më 2022-01-30.{cite web}: Mirëmbajtja CS1: Gjendja e adresës (lidhja)

[1]

[2]

[3]