Školjka

%V0 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$ [i]kongruentan[/i] $r$ [i]modulo[/i] $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) [b]Dokaz tvrdnje 1[/b]: 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. [b]Dokaz tvrdnje[/b] 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'$ [b]Dokaz tvrdnje 3[/b]: 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$ [b]Dokaz tvrdnje 4[/b]: \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'$ [b]Dokaz tvrdnje 5[/b]: Ova tvrdnja trivijalno slijedi iz tvrdnje 4 primjenjene $k$ puta.