Aritmetika modulare

Nga Wikipedia, enciklopedia e lirë
Jump to navigation Jump to search
Disambig.svg

Aritmetika modulare, apo "matematika me mbetje" është një sistem i aritmetikës për numrat e plotë. Karakterizohet për atë se, rangu i numrave përsëritet sa herë që të arrihet një vlerë e caktuar e quajtur modulo (mod), dhe asnjëhere nuk e tejkalon këtë vlerë.

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.

Qasja moderne në aritmetikën modulare është zhvilluar nga Carl Friedrich Gauss në librin e tij Disquisitiones Arithmeticae, të plublikuar në vitin 1801.

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[Redakto | Redakto nëpërmjet kodit]

Le të jenë dhënë numrat e plotë a, b dhe n, dhe le të jetë n > 1. Dy numra të plotë a dhe b themi të jenë kongruentë mod n, atëhere dhe vetëm atëhere kur n është plotëpjestues i ndryshimit të tyre (pra, atëhre dhe vetëm atëhere kur ekziston një numër i plotë k, ashtu që ab = kn).

Kongruenca modulo n paraqet një relacion të ekuivalencës që zbaton veprimet si mbledhja, zbritja dhe shumëzimi. 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 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 ≤ a < n dhe (pra, mbetja e kur pjestohet me )

Relacioni i kongruencës mund të shkruhet edhe kështu

ku mund të vërehet ndërlidhja me pjesëtimin me mbetje, megjithëse në këtë rast b-ja nuk është domosdo mbetja nga pjesëtimi i a me n. Në të vërtetë ajo qka shprehja ab (mod n) tregon, është se a dhe b kanë mbetjen e njëjtë në rastin kur pjesëtohen me n. Pra, si më poshtë:

ku 0 ≤ r < n është mbetja e njëjtë. Nëse i zbresim këto d< shprehje anë për anë, fitojmë:

duke e caktuar k = pq.

Shembuj[Redakto | Redakto nëpërmjet kodit]

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

sepse 38 − 14 = 24, dhe 24 është shumëfish i 12. Një mënyrë tjetër e shprehjes së kësaj kongruence është 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[Redakto | Redakto nëpërmjet kodit]

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

  • Vetia refleksive: aa (mod n)
  • Vetia e simetrisë: ab (mod n) nëse ba (mod n) për çdo a, b, dhe n.
  • Vetia transitive: Nëse ab (mod n) dhe bc (mod n), atëhere ac (mod n)

Nëse a1b1 (mod n) dhe a2b2 (mod n), ose nëse ab (mod n), atëhere:

  • a + kb + k (mod n) për çdo (compatibility with translation)
  • k ak b (mod n) për çdo (compatibility with scaling)
  • a1 + a2b1 + b2 (mod n) (compatibility with addition)
  • a1a2b1b2 (mod n) (compatibility with subtraction)
  • a1 a2b1 b2 (mod n) (compatibility with multiplication)
  • akbk (mod n) për çdo dhe (compatibility with exponentiation)
  • p(a) ≡ p(b) (mod n), për çdo polinom p(x) me koeficientët (compatibility with polynomial evaluation)

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

  • Nëse a + kb + k (mod n), për çdo , atëhere ab (mod n)
  • Nëse k ak b (mod n) dhe k është relativisht e thjeshtë me n, atëhere ab (mod n)
  • Nëse k ak b (mod kn) , atëhere ab (mod n)

Klasat e kongruencës [Redakto | Redakto nëpërmjet kodit]

Zbatimet[Redakto | Redakto nëpërmjet kodit]

Shënime[Redakto | Redakto nëpërmjet kodit]

Referencat[Redakto | Redakto nëpërmjet kodit]

Lidhje të jashtme[Redakto | Redakto nëpërmjet kodit]