Ako imamo cijeli broj
i prirodni broj
, te brojeve mozemo cjelobrojno podjeliti (podjeliti tako da dobijemo cijeli broj i ostatak), to jest
mozemo zapisati kao
za neke cijele brojeve
i
, take da je
. (Tvrdnja 1)
Taj zapis
je jedinstven, odnosno postoji tocno jedan
i tocno jedan
takvi da je
. (Tvrdnja 2)
Tako, mozemo reci da je
kongruentan
modulo
, a to zapisujemo ![a \equiv r \pmod b](/media/m/e/a/c/eac59d1d6a2c89abf79ed022124a6263.png)
Ovaj zapis je lijep jer sa njime mozemo lagano baratati, neka od njegovih svojstava su:
Ako je
i
onda je
(Tvrdnja 3)
Ako je
i
onda je
(Tvrdnja 4)
Dijeljenje je definirano ako su broj kojim djelimo i borj ciji modul gledamo relativno prosti, no za sada cemo ga izbjegavati
Ako je
onda je
(Tvrdnja 5)
Dokaz tvrdnje 1:
Neka je
najveci cijeli broj takav da je
. Tada je
. Oznacimo sada izraz (
) sa
(to jest neka je
). Primjetimo da je
pa ako je
i
, tada je ![b \cdot m + r=a](/media/m/3/4/5/3454cf0745957cf5a15c17b79f1b50d3.png)
Dakle takvi brojevi postoje.
Dokaz tvrdnje 2:
Pretpostavimo da postoje 2 para takvih brojeva. Dakle
i
. Postoje tri moguca slucaja:
Prvi slucaj:
, ![r \neq r'](/media/m/b/0/7/b079ac69f0f376fb4b147ff2d12a2deb.png)
A kako
![0=r' - r](/media/m/2/2/2/222546bf6643c7b5d6f1163fd7ff7b87.png)
Kontradikcija
Drugi slucaj:
, ![r = r'](/media/m/4/8/f/48f8154d7155e6c6efc5955b8b81d160.png)
![b \cdot n + r = b \cdot n' + r'](/media/m/1/4/7/1478ace8b5c554ba4f5b3f4484b1f350.png)
A kako
Kako je
zakljucujemo
Kontradikcija
Treci slucaj:
,
![b \cdot n + r = b \cdot n' + r](/media/m/7/d/b/7db77b7450e57db0f57057080c524f53.png)
Kako je
i
Znamo da
no
pa je
Dakle
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
i ![r=r'](/media/m/b/a/9/ba9cbb79d9addd966b6a22d1ab5a5bf0.png)
Dokaz tvrdnje 3:
Iz definicije kongruencija vidimo da je
i
za neke
i
. Broj
tada mozemo prikazati kao
I sada, ponovnim koristenjem definicije dobivamo da je newline ![a + a' \equiv r + r' \pmod b](/media/m/0/3/a/03aaa2ac68325b7c2b7d7fae7daa1e6b.png)
Dokaz tvrdnje 4: newline Iz definicije kongruencija vidimo da je
i
za neke
i
. Broj
tada mozemo prikazati kao
Mnozenjem i sredivanjem ovog izraza dobivamo newline
Ponovnim koristenjem definicije dobivamo ![a\cdot a' \equiv r\cdot r'](/media/m/d/1/a/d1a9069dfb2acdbd6fa8ce1fe3552741.png)
Dokaz tvrdnje 5:
Ova tvrdnja trivijalno slijedi iz tvrdnje 4 primjenjene
puta.
![a](/media/m/6/d/2/6d2832265560bb67cf117009608524f6.png)
![b](/media/m/e/e/c/eec0d7323095a1f2101fc1a74d069df6.png)
![a](/media/m/6/d/2/6d2832265560bb67cf117009608524f6.png)
![b \cdot n + r](/media/m/c/c/2/cc2f8a552716a6870fe6604dac7e2964.png)
![n](/media/m/a/e/5/ae594d7d1e46f4b979494cf8a815232b.png)
![r](/media/m/3/d/f/3df7cc5bbfb7b3948b16db0d40571068.png)
![0 \leqslant r < b](/media/m/2/8/c/28caec690454933cdb18bdeb8136281c.png)
Taj zapis
![a=b \cdot n + r](/media/m/3/5/8/35859d503054200c39218978f569c121.png)
![n](/media/m/a/e/5/ae594d7d1e46f4b979494cf8a815232b.png)
![r](/media/m/3/d/f/3df7cc5bbfb7b3948b16db0d40571068.png)
![b \cdot n + r=a](/media/m/f/6/7/f6757ed12565a3dbfd9affc05290e694.png)
Tako, mozemo reci da je
![a](/media/m/6/d/2/6d2832265560bb67cf117009608524f6.png)
![r](/media/m/3/d/f/3df7cc5bbfb7b3948b16db0d40571068.png)
![b](/media/m/e/e/c/eec0d7323095a1f2101fc1a74d069df6.png)
![a \equiv r \pmod b](/media/m/e/a/c/eac59d1d6a2c89abf79ed022124a6263.png)
Ovaj zapis je lijep jer sa njime mozemo lagano baratati, neka od njegovih svojstava su:
![\bullet](/media/m/8/a/4/8a4484c88ed14d788182c562df19e96a.png)
![a \equiv r \pmod b](/media/m/e/a/c/eac59d1d6a2c89abf79ed022124a6263.png)
![a' \equiv r' \pmod b](/media/m/9/2/2/9221a2885a748924c488af003442cd47.png)
![a+a' \equiv r +r' \pmod b](/media/m/3/1/b/31bfee7f79016906b4c01349e23a06c2.png)
![\bullet](/media/m/8/a/4/8a4484c88ed14d788182c562df19e96a.png)
![a \equiv r \pmod b](/media/m/e/a/c/eac59d1d6a2c89abf79ed022124a6263.png)
![a' \equiv r' \pmod b](/media/m/9/2/2/9221a2885a748924c488af003442cd47.png)
![a \cdot a' \equiv r \cdot r' \pmod b](/media/m/6/b/e/6be4d61b4fd4d16ac1d4b1b63e3220df.png)
![\bullet](/media/m/8/a/4/8a4484c88ed14d788182c562df19e96a.png)
![\bullet](/media/m/8/a/4/8a4484c88ed14d788182c562df19e96a.png)
![a \equiv r \pmod b](/media/m/e/a/c/eac59d1d6a2c89abf79ed022124a6263.png)
![a^k \equiv r^k \pmod b](/media/m/5/8/e/58e444e4ff18a878ba549ccd47cc6ff9.png)
Dokaz tvrdnje 1:
Neka je
![m](/media/m/1/3/6/1361d4850444c055a8a322281f279b39.png)
![b \cdot m \leqslant a](/media/m/c/c/7/cc790216565c8678f1bd79199f65887b.png)
![<0a - b \cdot m < n](/media/m/f/9/e/f9e04334c55db73672aae5e38a42e351.png)
![a - b \cdot m](/media/m/e/5/c/e5cded3e31ac6b03ca1d8810181f4a69.png)
![x](/media/m/f/1/8/f185adeed9bd346bc960bca0147d7aae.png)
![x=a - b \cdot m](/media/m/8/7/e/87e69d1d5e7cc47452d106e81b6dbd41.png)
![b \cdot m + x = a](/media/m/6/5/d/65d198589f51611032e6266cdaffcea8.png)
![n=m](/media/m/b/5/8/b58a9f0e6fcada7900fafaa6449be8d3.png)
![r=x](/media/m/5/4/7/547ddce1912407a8f7c31b1efe572447.png)
![b \cdot m + r=a](/media/m/3/4/5/3454cf0745957cf5a15c17b79f1b50d3.png)
Dakle takvi brojevi postoje.
Dokaz tvrdnje 2:
Pretpostavimo da postoje 2 para takvih brojeva. Dakle
![b \cdot n + r =a](/media/m/d/1/d/d1d02fcc300685bfe31377994f65023d.png)
![b \cdot n' + r'=a](/media/m/9/c/8/9c8d1016919fac63acddd01a25f0ae13.png)
![\bullet](/media/m/8/a/4/8a4484c88ed14d788182c562df19e96a.png)
![n=n'](/media/m/3/e/b/3eb0de6a1340b423a906572cf26a4952.png)
![r \neq r'](/media/m/b/0/7/b079ac69f0f376fb4b147ff2d12a2deb.png)
![b \cdot n + r = b \cdot n' + r' \newline b \cdot n - b \cdot n' = r' - r](/media/m/7/c/7/7c7a324b94396015fbaf7cdd6d355860.png)
A kako
![n=n'](/media/m/3/e/b/3eb0de6a1340b423a906572cf26a4952.png)
![0=r' - r](/media/m/2/2/2/222546bf6643c7b5d6f1163fd7ff7b87.png)
![r=r'](/media/m/b/a/9/ba9cbb79d9addd966b6a22d1ab5a5bf0.png)
![\bullet](/media/m/8/a/4/8a4484c88ed14d788182c562df19e96a.png)
![n \neq n'](/media/m/0/4/1/04133532a7db71ad5230b5c39e115c99.png)
![r = r'](/media/m/4/8/f/48f8154d7155e6c6efc5955b8b81d160.png)
![b \cdot n + r = b \cdot n' + r'](/media/m/1/4/7/1478ace8b5c554ba4f5b3f4484b1f350.png)
![b \cdot n - b \cdot n' = r - r'](/media/m/4/5/0/4505b590bfb790677a5a7d32c7b52789.png)
![r=r'](/media/m/b/a/9/ba9cbb79d9addd966b6a22d1ab5a5bf0.png)
![b \cdot (n-n')=0](/media/m/a/f/2/af28cad9fdd56be41f8d9eb563f17ecf.png)
Kako je
![b\neq 0](/media/m/5/d/2/5d20df15f7781e31d908af6ec7e7b4d9.png)
![n=n'](/media/m/3/e/b/3eb0de6a1340b423a906572cf26a4952.png)
![\bullet](/media/m/8/a/4/8a4484c88ed14d788182c562df19e96a.png)
![n \neq n'](/media/m/0/4/1/04133532a7db71ad5230b5c39e115c99.png)
![r\neq r'](/media/m/6/6/4/66467e5fd97f45c9f6b0017b064b07f4.png)
![b \cdot n + r = b \cdot n' + r](/media/m/7/d/b/7db77b7450e57db0f57057080c524f53.png)
![b \cdot (n-n')=r-r'](/media/m/f/0/4/f043dbc4bccec75c9edba2d55d11f080.png)
Kako je
![0\leqslant r<b](/media/m/0/4/f/04fd85793e6fbea9dddf1ade9a6e1dc3.png)
![0 \leqslant r' < b](/media/m/2/8/b/28b4f14521dfdb459b32b68ac8a4948b.png)
![|r-r'|<b](/media/m/7/e/2/7e2c995caabbc11a20b3bb61b3d877ac.png)
![|n-n'|\geqslant 1](/media/m/3/a/4/3a4ed2a65d8cbb643a34b5b47d174f6f.png)
![|b \cdot (n-n')>b](/media/m/b/3/3/b33c2a65dd68693e37c8dcad768e53b6.png)
Dakle
![|b \cdot (n-n')|>|r-r'|](/media/m/2/3/c/23ccda9fccc94da7c6eaebf1c6e2b0fd.png)
Kako smo isprobali sve slucajeve kada su ti brojevi razliciti, i u svakome dosli do kontradikcije, ocito mora vrijediti
![n=n'](/media/m/3/e/b/3eb0de6a1340b423a906572cf26a4952.png)
![r=r'](/media/m/b/a/9/ba9cbb79d9addd966b6a22d1ab5a5bf0.png)
Dokaz tvrdnje 3:
Iz definicije kongruencija vidimo da je
![a=b \cdot n + r](/media/m/3/5/8/35859d503054200c39218978f569c121.png)
![a'= b\cdot n' + r'](/media/m/9/8/3/98322fb98628ec598e998bfc9df8d2e6.png)
![n](/media/m/a/e/5/ae594d7d1e46f4b979494cf8a815232b.png)
![n'](/media/m/e/9/d/e9d235e94d9b66d988e0015a59043b95.png)
![a+a'](/media/m/0/2/e/02ebed2f7f4338026c9d54ae80bdb7e8.png)
![(a+a')=b \cdot (n+n') + r + r'](/media/m/4/8/b/48bd8eb521245cd8a70f6554ca96e1e8.png)
![a + a' \equiv r + r' \pmod b](/media/m/0/3/a/03aaa2ac68325b7c2b7d7fae7daa1e6b.png)
Dokaz tvrdnje 4: newline Iz definicije kongruencija vidimo da je
![a=b \cdot n + r](/media/m/3/5/8/35859d503054200c39218978f569c121.png)
![a'= b\cdot n' + r'](/media/m/9/8/3/98322fb98628ec598e998bfc9df8d2e6.png)
![n](/media/m/a/e/5/ae594d7d1e46f4b979494cf8a815232b.png)
![n'](/media/m/e/9/d/e9d235e94d9b66d988e0015a59043b95.png)
![a\cdot a'](/media/m/c/2/f/c2f50d9df612314fe03c972af2b3016e.png)
![a \cdot a' = (b\cdot n + r)(b\cdot n' + r')](/media/m/2/f/9/2f92ddc241b091056a3a250b4a98d12c.png)
![a\cdot a'= b\cdot (2b\cdot n\cdot n' + n\cdot r' + n' \cdot r) + r\cdot r'](/media/m/a/1/f/a1fc913f1d928e7ea850d0b23377d718.png)
![a\cdot a' \equiv r\cdot r'](/media/m/d/1/a/d1a9069dfb2acdbd6fa8ce1fe3552741.png)
Dokaz tvrdnje 5:
Ova tvrdnja trivijalno slijedi iz tvrdnje 4 primjenjene
![k](/media/m/f/1/3/f135be660b73381aa6bec048f0f79afc.png)