Kongruencie¶

Čo je kongruencia (intuícia)¶

Kongruencia je spôsob, ako povedať:

„Dve čísla sa správajú rovnako, keď ich delíme číslom $m$.“

Presnejšie: majú rovnaký zvyšok po delení $m$.

Príklad (modulo 5): - $7$ má zvyšok $2$, - $2$ má zvyšok $2$,

takže „sú rovnaké modulo 5“.

Definícia¶

Kongruencia modulo m

Nech $m \in \mathbb{N}$, $m \ge 2$ a nech $a, b \in \mathbb{Z}$. Hovoríme, že $a$ a $b$ sú kongruentné modulo m, ak majú rovnaký zvyšok po delení $m$.

Zapisujeme:

\[ a \equiv b \; (mod\ m) \]

Najdôležitejšia ekvivalencia¶

Toto je „motor“ celej modulárnej aritmetiky.

Ekvivalentný zápis kongruencie

Pre $a,b \in \mathbb{Z}$ a $m \ge 2$ platí:

\[ a \equiv b \; (mod\ m) \iff m \mid (a-b) \]

Teda: $m$ delí rozdiel $a-b$.

Poznámka

Táto veta je praktická, lebo „rovnaký zvyšok“ sa ťažšie dokazuje priamo, ale „$m$ delí rozdiel“ sa dokazuje ľahko.

Prečo to platí (veľmi pomaly)¶

Ak $a$ a $b$ majú rovnaký zvyšok po delení $m$, tak existujú celé čísla $q_1,q_2$ a zvyšok $r$ také, že:

\[ a = q_1 m + r \]

\[ b = q_2 m + r \]

Odčítame:

\[ a-b = (q_1 m + r) - (q_2 m + r) = (q_1-q_2)m \]

A to znamená, že $a-b$ je násobok $m$, čiže:

\[ m \mid (a-b) \]

Naopak, ak $m \mid (a-b)$, tak $a-b = km$ pre nejaké $k \in \mathbb{Z}$. To znamená, že $a$ a $b$ sa líšia o násobok $m$, takže pri delení $m$ musí byť zvyšok rovnaký.

Príklady¶

7 a 2 modulo 5

Overme:

\[ 7 \equiv 2 \; (mod\ 5) \]

Stačí ukázať, že $5$ delí $7-2$:

\[ 7-2 = 5 \]

\[ 5 \mid 5 \]

Teda kongruencia platí.

29 a 12 modulo 17

Overme:

\[ 29 \equiv 12 \; (mod\ 17) \]

Skontrolujeme rozdiel:

\[ 29-12 = 17 \]

\[ 17 \mid 17 \]

Kongruencia ako „rovnosť v zvyškových triedach“¶

Kongruencia sa správa ako rovnosť, ale nie na celej $\mathbb{Z}$. Skôr hovorí:

„Pozeráme sa len na triedy zvyškov.“

Napríklad modulo 5 sú všetky čísla:

trieda $0$: $\dots,-10,-5,0,5,10,\dots$
trieda $1$: $\dots,-9,-4,1,6,11,\dots$
trieda $2$: $\dots,-8,-3,2,7,12,\dots$

a podobne.

Čísla sú kongruentné práve vtedy, keď ležia v tej istej triede.

Základné vlastnosti kongruencie¶

1) Reflexivita, symetria, tranzitivita¶

Kongruencia je ekvivalencia

Pre každé $a,b,c \in \mathbb{Z}$ platí:

Reflexivita:

$$ a \equiv a \; (mod\ m) $$

Symetria: ak

$$ a \equiv b \; (mod\ m), $$

tak aj

$$ b \equiv a \; (mod\ m) $$

Tranzitivita: ak

$$ a \equiv b \; (mod\ m) $$

a zároveň

$$ b \equiv c \; (mod\ m), $$

tak

$$ a \equiv c \; (mod\ m) $$

Poznámka

Toto znamená, že kongruencia rozdeľuje celé čísla na „triedy“, presne ako sme videli pri $\mathbb{Z}_m$.

Kongruencia a operácie¶

Toto je to, čo si mal v zošite ako vetu + dôkaz.

Zachovanie kongruencie pri sčítaní a násobení

Nech $a_1 \equiv b_1 \; (mod\ m)$ a $a_2 \equiv b_2 \; (mod\ m)$. Potom platí:

\[ a_1 + a_2 \equiv b_1 + b_2 \; (mod\ m) \]

a

\[ a_1 a_2 \equiv b_1 b_2 \; (mod\ m) \]

Dôkaz (sčítanie)¶

Dôkaz

Z predpokladov platí:

\[ m \mid (a_1-b_1) \]

a

\[ m \mid (a_2-b_2) \]

Potom $m$ delí aj súčet:

\[ (a_1-b_1) + (a_2-b_2) = (a_1+a_2) - (b_1+b_2) \]

Teda:

\[ m \mid \big((a_1+a_2)-(b_1+b_2)\big) \]

a preto:

\[ a_1+a_2 \equiv b_1+b_2 \; (mod\ m) \]

Dôkaz (násobenie)¶

Dôkaz

Opäť vieme, že:

\[ m \mid (a_1-b_1) \]

\[ m \mid (a_2-b_2) \]

Uvažujme rozdiel:

\[ a_1a_2 - b_1b_2 \]

Upravíme ho (trik „pridám a odčítam ten istý člen“):

\[ a_1a_2 - b_1a_2 + b_1a_2 - b_1b_2 \]

Zoskupíme:

\[ a_2(a_1-b_1) + b_1(a_2-b_2) \]

Oba členy sú deliteľné $m$, preto aj ich súčet je deliteľný $m$:

\[ m \mid (a_1a_2 - b_1b_2) \]

Teda:

\[ a_1a_2 \equiv b_1b_2 \; (mod\ m) \]

Praktická aplikácia: ciferný súčet a deliteľnosť 9¶

Kľúčový fakt:

\[ 10 \equiv 1 \; (mod\ 9) \]

Z toho automaticky vyplýva:

\[ 10^n \equiv 1 \; (mod\ 9) \]

Prečo z toho vznikne pravidlo ciferného súčtu¶

Nech číslo $a$ má desiatkový zápis:

\[ a = a_0 + a_1 \cdot 10 + a_2 \cdot 10^2 + \dots + a_n \cdot 10^n \]

Keďže $10^k \equiv 1\ (mod\ 9)$, môžeme nahradiť $10^k$ jednotkou:

\[ a \equiv a_0 + a_1 + a_2 + \dots + a_n \; (mod\ 9) \]

Ciferný súčet

Číslo a jeho ciferný súčet majú rovnaký zvyšok po delení 9.

Príklad

Uvažujme číslo:

\[ 873915367423 \]

Ciferný súčet:

\[ 8+7+3+9+1+5+3+6+7+4+2+3 = 58 \]

Opäť ciferný súčet:

\[ 5+8 = 13 \]

Zvyšok po delení 9:

\[ 13 \equiv 4 \; (mod\ 9) \]

Preto:

\[ 873915367423 \equiv 4 \; (mod\ 9) \]

Najčastejšie chyby¶

Krátenie v kongruencii

Z kongruencie

\[ a\cdot c \equiv b\cdot c \; (mod\ m) \]

nemôžeš automaticky „skrátiť“ $c$.

Krátenie je bezpečné len vtedy, keď $c$ má inverz modulo $m$, teda keď

\[ \gcd(c,m)=1. \]

Zhrnutie¶

Kongruencia znamená rovnaký zvyšok po delení.
Platí ekvivalencia:

$$ a \equiv b \; (mod\ m) \iff m \mid (a-b) $$

Kongruencia sa zachováva pri sčítaní a násobení.
Ciferný súčet je aplikácia kongruencií modulo 9.