Aritmetika modulare

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

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

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ë $a - b = kn$ ).

Kongruenca modulo n paraqet një relacion të ekuivalencës që zbaton veprimet si mbledhja, zbritja dhe shumëzimi. 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$ )

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

$a=kn+b,$

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 $a \equiv b (mod n)$ tregon, është se $a$ dhe $b$ kanë mbetjen e njëjtë në rastin kur pjesëtohen me $n$ . Pra, si më poshtë:

$a=pn+r,$

$b=qn+r,$

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

$a-b=kn,$

duke e caktuar $k = p - q .$

Shembuj

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

{\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:

$a + k \equiv b + k (mod n)$ për çdo $k\in \mathbb {Z}$ (compatibility with translation)
$k a \equiv k b (mod n)$ për çdo $k\in \mathbb {Z}$ (compatibility with scaling)
$a 1 + a 2 \equiv b 1 + b 2 (mod n)$ (compatibility with addition)
$a 1 - a 2 \equiv b 1 - b 2 (mod n)$ (compatibility with subtraction)
$a 1 a 2 \equiv b 1 b 2 (mod n)$ (compatibility with multiplication)
$a k \equiv b k (mod n)$ për çdo $k\in \mathbb {Z}$ dhe $k>0$ (compatibility with exponentiation)
$p (a) \equiv p (b) (mod n)$ , për çdo polinom $p (x)$ me koeficientët $k_{n}\in \mathbb {Z}$ (compatibility with polynomial evaluation)

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)$

Aritmetika modulare

Lëndë

Kongruenca

Shembuj

Disa veti

Klasat e kongruencës

Zbatimet

Shënime

Referencat

Lidhje të jashtme