« Vrati se
Ako imamo cijeli broj a i prirodni broj b, te brojeve mozemo cjelobrojno podjeliti (podjeliti tako da dobijemo cijeli broj i ostatak), to jest a mozemo zapisati kao b \cdot n + r za neke cijele brojeve n i r, take da je 0 \leqslant r < b. (Tvrdnja 1)
Taj zapis a=b \cdot n + r je jedinstven, odnosno postoji tocno jedan n i tocno jedan r takvi da je b \cdot n + r=a. (Tvrdnja 2)
Tako, mozemo reci da je a kongruentan r modulo b, a to zapisujemo a \equiv r \pmod b
Ovaj zapis je lijep jer sa njime mozemo lagano baratati, neka od njegovih svojstava su:

\bullet Ako je a \equiv r \pmod b i a' \equiv r' \pmod b onda je a+a' \equiv r +r' \pmod b (Tvrdnja 3)
\bullet Ako je a \equiv r \pmod b i a' \equiv r' \pmod b onda je a \cdot a' \equiv r \cdot r' \pmod b (Tvrdnja 4)
\bullet Dijeljenje je definirano ako su broj kojim djelimo i borj ciji modul gledamo relativno prosti, no za sada cemo ga izbjegavati
\bullet Ako je a \equiv r \pmod b onda je a^k \equiv r^k \pmod b (Tvrdnja 5)



Dokaz tvrdnje 1:
Neka je m najveci cijeli broj takav da je b \cdot m \leqslant a. Tada je <0a - b \cdot m < n. Oznacimo sada izraz (a - b \cdot m) sa x (to jest neka je x=a - b \cdot m). Primjetimo da je b \cdot m + x = a pa ako je n=m i r=x, tada je b \cdot m + r=a
Dakle takvi brojevi postoje.


Dokaz tvrdnje 2:
Pretpostavimo da postoje 2 para takvih brojeva. Dakle b \cdot n + r =a i b \cdot n' + r'=a. Postoje tri moguca slucaja:
\bullet Prvi slucaj:
n=n', r \neq r'
 b \cdot n + r = b \cdot n' + r' \newline b \cdot n - b \cdot n' = r' - r
A kako  n=n'  0=r' - r
r=r' Kontradikcija

\bullet Drugi slucaj:
n \neq n', r = r'
 b \cdot n + r = b \cdot n' + r'
 b \cdot n - b \cdot n' = r - r' A kako r=r'
b \cdot (n-n')=0
Kako je b\neq 0 zakljucujemo n=n' Kontradikcija

\bullet Treci slucaj:
n \neq n', r\neq r'
b \cdot n + r = b \cdot n' + r
b \cdot  (n-n')=r-r'
Kako je 0\leqslant r<b i 0 \leqslant r' < b Znamo da |r-r'|<b no |n-n'|\geqslant 1 pa je |b \cdot (n-n')>b
Dakle |b \cdot (n-n')|>|r-r'| Sto je nemoguce ako su ti brojevi jednaki. Kontradikcija.

Kako smo isprobali sve slucajeve kada su ti brojevi razliciti, i u svakome dosli do kontradikcije, ocito mora vrijediti n=n' i r=r'


Dokaz tvrdnje 3:
Iz definicije kongruencija vidimo da je a=b \cdot n + r i a'= b\cdot n' + r' za neke n i n'. Broj a+a' tada mozemo prikazati kao (a+a')=b \cdot (n+n') + r + r' I sada, ponovnim koristenjem definicije dobivamo da je newline a + a' \equiv r + r' \pmod b


Dokaz tvrdnje 4: newline Iz definicije kongruencija vidimo da je a=b \cdot n + r i a'= b\cdot n' + r' za neke n i n'. Broj a\cdot a' tada mozemo prikazati kao a \cdot a' = (b\cdot n + r)(b\cdot n' + r') Mnozenjem i sredivanjem ovog izraza dobivamo newline a\cdot a'= b\cdot (2b\cdot n\cdot n' + n\cdot r' + n' \cdot r) + r\cdot r' Ponovnim koristenjem definicije dobivamo a\cdot a' \equiv r\cdot r'


Dokaz tvrdnje 5:
Ova tvrdnja trivijalno slijedi iz tvrdnje 4 primjenjene k puta.

Slični zadaci