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.djathtas|parapamje|Kohë matja në këtë orë përdor aritmetikën me modulo 12. Nëse nga ora 9, kalojnë 4 orë, pra 9 + 4, atëhere dora e orës do e tregojë orën 1, pasi që 13 është kongruent me 1 mod 12.

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ë:



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  (pa kllapa), e cila paraqet veprimin modulo që në të vërtetë tregon një numër të veçantë  të atillë që  dhe  (pra, mbetja e  kur pjestohet me )

 Shembuj 
Shembulli 1.

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:



sepse , 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:



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

 Vetia refleksive: 
 Vetia e simetrisë:  nëse  për çdo , , dhe .
 Vetia transitive: Nëse  dhe , atëhere 

Nëse  dhe  ose nëse  atëhere:

  për çdo  (përputhshmëria me përkthimin)
  për çdo  (përputhshmëria me shkallëzimin)
  (përputhshmëria me mbledhjen)
  (përputhshmëria me zbritjen)
  (përputhshmëria me shumëzimin)
  për çdo  dhe  (përputhshmëria me fuqizimin)
 , për çdo polinom  me koeficientët  (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 , për çdo , atëhere 
 Nëse  dhe  është relativisht e thjeshtë me , atëhere 
 Nëse  , atëhere 

 Klasat e kongruencës 
Ashtu si çdo relacion i kongruencës, modulo  i kongruencës është një relacion i ekuivalencës, dhe klasa e ekuivalencës së numrit të plotë , e shënuar me , është bashkësia . Ky grup, i përbërë nga të gjithë numrat e plotë kongruentë me një modul , quhet klasa e kongruencës, klasa e mbetjes ose thjesht mbetje e numrit të plotë  modulo . Kur moduli  njihet nga konteksti, ajo mbetje mund të shënohet gjithashtu si .

 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.

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".

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 
Kategoria:Matematikë diskrete
Kategoria:Teoria e numrave