Modulární sčítání a odčítání

Nechť A=14, B=17, C=5

Ověřme: (A + B) mod C = (A mod C + B mod C) mod C
LSR = Levá strana rovnice
PSR = Pravá strana rovnice

LSR = (A + B) mod C
LSR = (14 + 17) mod 5
LSR = 31 mod 5
LSR = 1

PSR = (A mod C + B mod C) mod C
PSR = (14 mod 5 + 17 mod 5) mod 5
PSR = (4 + 2) mod 5
PSR = 1

Prohlédni si obrázek níže. Chceme-li spočítat 12+9 mod 7, můžeme snadno jít kolem modulárního kruhu po sérii 12+9 kroků ve směru hodinových ručiček (jak je ukázáno na levém dolním kruhu).

Můžeme si to zkrátit uvědoměním si, že po každých 7 krocích skončíme na stejném místě modulárního kruhu. Tyto kompletní oběhy kolem modulárního kruhu nepřispívají k výsledné pozici. Ignorujeme tyto oběhy spočítáním „každé z čísel mod 7“ (ukázáno na horních dvou kruzích). To nám dá počet kroků ve směru hodinových ručiček, relativně k 0, které přispěly ke každé z finálních pozic na modulárním kruhu.

Nyní musíme jít na kruhu o tolik kroků ve směru hodinových ručiček, kolik jich celkem přispělo k jednotlivým finálním pozicím (ukázáno na kruhu vpravo dole). Tato metoda obecně platí pro libovolná dvě celá čísla na libovolném modulárním kruhu.

Dokážeme (A + B) mod C = (A mod C + B mod C) mod C.
Musíme ukázat, že LSR=PSR.

Z věty o dělení se zbytkem lze psát A a B takto:

A = C * Q1 + R1, kde 0 ≤ R1 < C a Q1 je celé číslo. A mod C = R1
B = C * Q2 + R2, kde 0 ≤ R2 < C a Q2 je celé číslo. B mod C = R2
(A + B) = C * (Q1 + Q2) + R1+R2

LSR = (A + B) mod C
LSR = (C * (Q1 + Q2) + R1+ R2) mod C
Násobků C se zbavíme působením mod C.
LSR = (R1 + R2) mod C

PSR = (A mod C + B mod C) mod C
PSR = (R1 + R2) mod C

Velmi podobný důkaz platí i pro modulární odečítání.