Osztási algoritmus

Osztás

• Egy $a$ egész szám osztása egy nem nulla $b$ egész számmal azt jelenti, hogy olyan $q$ és $r$ egész számokat keresünk, amelyekre $a = bq + r$, ahol $0 \leq r < |b|$.
• $a$ az osztandó, $b$ az osztó, $q$ a hányados, $r$ a maradék.

Osztási algoritmus

• Bármely $a$ és $b$ egész számra, ahol $b \neq 0$, léteznek egyértelmű $q$ és $r$ egész számok, amelyekre $a = bq + r$, ahol $0 \leq r < |b|$.
• $S = {a - bk \geq 0 \mid k \in \mathbb{Z}}$ halmaz nem üres.
• A rendezési elv szerint $S$-nek van egy legkisebb eleme $r = a - bq \geq 0$.
• Ha $r \geq |b|$, akkor $r - |b| \geq 0$, és $r - |b| = a - b(q \pm 1) \geq 0$, ami azt jelenti, hogy $r - |b| \in S$.
• Mivel $r - |b| < r$, ez ellentmond annak a ténynek, hogy $r$ az $S$ legkisebb eleme. Ezért $0 \leq r < |b|$.
• Ha léteznek $q_1$, $q_2$, $r_1$, $r_2$ úgy, hogy $a = bq_1 + r_1 = bq_2 + r_2$, ahol $0 \leq r_1, r_2 < |b|$, akkor $b(q_1 - q_2) = r_2 - r_1$.
• Ekkor $b \mid (r_2 - r_1)$, és mivel $0 \leq r_1, r_2 < |b|$, ezért $|r_2 - r_1| < |b|$.
• Az egyenlőtlenséget kielégítő egyetlen $b$ többszöröse a 0. Ezért $r_2 - r_1 = 0$, ami azt jelenti, hogy $r_1 = r_2$, tehát $q_1 = q_2$.

Példák

• Ha $a = 10$ és $b = 3$, akkor $10 = 3 \cdot 3 + 1$, tehát $q = 3$ és $r = 1$.
• Ha $a = -10$ és $b = 3$, akkor $-10 = 3 \cdot (-4) + 2$, tehát $q = -4$ és $r = 2$.
• Ha $a = 10$ és $b = -3$, akkor $10 = (-3) \cdot (-3) + 1$, tehát $q = -3$ és $r = 1$.
• Ha $a = -10$ és $b = -3$, akkor $-10 = (-3) \cdot 4 + 2$, tehát $q = 4$ és $r = 2$.

Kongruencia

Definició

• Ha $a$ és $b$ egész számok és $m$ egy pozitív egész szám, akkor $a$ kongruens $b$-vel modulo $m$, ha $m$ osztja $a - b$-t.
• Az $a \equiv b \pmod{m}$ jelölést használjuk annak jelzésére, hogy $a$ kongruens $b$-vel modulo $m$.
• Ha $a$ nem kongruens $b$-vel modulo $m$, akkor $a \not\equiv b \pmod{m}$.

Kongruencia reláció

• Ha $a$ és $b$ egész számok és $m$ egy pozitív egész szám, akkor $a \equiv b \pmod{m}$ akkor és csak akkor, ha $a \operatorname{mod} m = b \operatorname{mod} m$.
• Ha $a \equiv b \pmod{m}$, akkor $m \mid (a - b)$, így $a - b = km$ valamilyen $k$ egész számra.
• Az osztási algoritmusból következik, hogy $a = q_1m + r_1$, ahol $0 \leq r_1 < m$ és $b = q_2m + r_2$, ahol $0 \leq r_2 < m$.
• Ezért $a \operatorname{mod} m = r_1$ és $b \operatorname{mod} m = r_2$.
• Mivel $a - b = km$, ezért $q_1m + r_1 - (q_2m + r_2) = km$, amiből következik, hogy $r_1 - r_2 = (k - q_1 + q_2)m$.
• Tehát $m \mid (r_1 - r_2)$. Mivel $|r_1 - r_2| < m$, ezért $r_1 - r_2 = 0$, így $r_1 = r_2$.
• Fordítva, ha $a \operatorname{mod} m = b \operatorname{mod} m$, akkor $r_1 = r_2$. Így $a - b = (q_1m + r_1) - (q_2m + r_2) = (q_1 - q_2)m$.
• Ezért $m \mid (a - b)$, tehát $a \equiv b \pmod{m}$.

Példák

• $17 \equiv 5 \pmod{6}$, mert $17 - 5 = 12$ és $6 \mid 12$.
• $24 \not\equiv 10 \pmod{6}$, mert $24 - 10 = 14$ és $6 \nmid 14$.

Kongruenciák tulajdonságai

• Legyen $m$ egy pozitív egész szám. Ha $a \equiv b \pmod{m}$ és $c \equiv d \pmod{m}$, akkor $a + c \equiv b + d \pmod{m}$ és $a \cdot c \equiv b \cdot d \pmod{m}$.
• Mivel $a \equiv b \pmod{m}$ és $c \equiv d \pmod{m}$, ezért $m \mid (a - b)$ és $m \mid (c - d)$. Ezért léteznek $k_1$ és $k_2$ egész számok úgy, hogy $a - b = k_1m$ és $c - d = k_2m$.
• Ekkor $(a + c) - (b + d) = (a - b) + (c - d) = k_1m + k_2m = (k_1 + k_2)m$.
• Tehát $m \mid [(a + c) - (b + d)]$, így $a + c \equiv b + d \pmod{m}$.
• Valamint $ac - bd = ac - bc + bc - bd = c(a - b) + b(c - d) = ck_1m + bk_2m = (ck_1 + bk_2)m$.
• Tehát $m \mid (ac - bd)$, így $ac \equiv bd \pmod{m}$.
• Legyen $m$ egy pozitív egész szám és legyenek $a$ és $b$ egész számok. Ekkor $(a + b) \operatorname{mod} m = [(a \operatorname{mod} m) + (b \operatorname{mod} m)] \operatorname{mod} m$ és $a \cdot b \operatorname{mod} m = [(a \operatorname{mod} m) \cdot (b \operatorname{mod} m)] \operatorname{mod} m$.
• Az osztási algoritmusból következik, hogy $a = q_1m + (a \operatorname{mod} m)$ és $b = q_2m + (b \operatorname{mod} m)$.
• Ekkor $a + b = (q_1 + q_2)m + (a \operatorname{mod} m) + (b \operatorname{mod} m)$ és $a \cdot b = (q_1m + (a \operatorname{mod} m))(q_2m + (b \operatorname{mod} m)) = (q_1q_2m + q_1(b \operatorname{mod} m) + q_2(a \operatorname{mod} m))m + (a \operatorname{mod} m)(b \operatorname{mod} m)$.
• Ezért $(a + b) \operatorname{mod} m = [(a \operatorname{mod} m) + (b \operatorname{mod} m)] \operatorname{mod} m$ és $a \cdot b \operatorname{mod} m = [(a \operatorname{mod} m) \cdot (b \operatorname{mod} m)] \operatorname{mod} m$.

Kongruenciák alkalmazásai

Hash függvények

• A $h$ hash függvény hozzárendeli a $h(k)$ memóriacímet ahhoz a rekordhoz, amelynek kulcsa $k$.
• A legelterjedtebb hash függvények a $h(k) = k \operatorname{mod} m$ formájúak, ahol $m$ az elérhető memóriacímek száma.
• Ha $h(k) = k \operatorname{mod} 111$, akkor a $k = 3214$ kulcsú rekord a $h(3214) = 3214 \operatorname{mod} 111 = 10$ memóriacímre lesz hozzárendelve.

Ellenőrző számjegyek

• Az ellenőrző számjegy egy számhoz hozzáadott számjegy a hibák észlelésére.

Példa

• UPC (Universal Product Code). Az Egyesült Államokban és Kanadában minden kiskereskedelmi terméken kötelező UPC-kód található. Ez 12 decimális számjegyből áll, $x_1 x_2 \dots x_{12}$, ahol az utolsó számjegy $x_{12}$ az ellenőrző számjegy. Az ellenőrző számjegyet úgy választják meg, hogy $3x_1 + x_2 + 3x_3 + x_4 + 3x_5 + x_6 + 3x_7 + x_8 + 3x_9 + x_{10} + 3x_{11} + x_{12} \equiv 0 \pmod{10}$.
• Ha a UPC $03600029145x_{12}$, akkor $3 \cdot 0 + 3 + 3 \cdot 6 + 0 + 3 \cdot 0 + 0 + 3 \cdot 2 + 9 + 3 \cdot 1 + 4 + 3 \cdot 5 + x_{12} \equiv 0 \pmod{10}$, azaz $49 + x_{12} \equiv 0 \pmod{10}$.
• Tehát $x_{12} = 1$. Az ellenőrző számjegy 1.
• ISBN (International Standard Book Number) Minden könyvet egy ISBN azonosít. Az ISBN-10 10 számjegyből áll $x_1 x_2 \dots x_{10}$, ahol az utolsó számjegy $x_{10}$ az ellenőrző számjegy. Az ellenőrző számjegyet úgy választják meg, hogy $x_1 + 2x_2 + 3x_3 + \dots + 9x_9 + 10x_{10} \equiv 0 \pmod{11}$.
• Az utolsó számjegy lehet X betű, ami a 10-es számot jelöli.