Modularna aritmetika

Teorija kongruencija predstavlja još jedno naslijeđe Carla Friedricha Gaußa, koji je ovu tehniku, poznatu i pod nazivom modularna aritmetika, zasnovao u svom djelu Disquisitiones Arithmeticae, objavljenom 1801 . Spomenuta knjiga se sastojala od sedam poglavlja, od kojih je prvih šest bilo posvećeno teoriji brojeva. Svakodnevni primjer ove teorije srećemo pri mjerenju vremena, gdje koristimo takozvanu aritmetiku modulo 12 dijeleći dan na dva perioda u trajanju od 12 sati.

Relacija ekvivalencije

Relacija biti kongruentan modulo n je relacija ekvivalencije

• refleksivna a / a ( mod n)
• simetrija a / b ( mod n) =>b / a ( mod n)
• tranzitivnost ( a / b ( mod n) & b /c( mod n) ) => a /c ( mod n)

Dokaz

Pokažimo najprije da je a kongruentno b modulo n ako i samo ako a i b daju isti ostatak pri dijeljenju s n.

Pretpostavimo da je a kongruentno b modulo n te, korištenjem teorema o dijeljenju s ostatkom, napišimo

$a=q_{1}\times n+r_{1}ia=q_{2}\times n+r_{2}$, pri čemu vrijedi $0\leq r_{1},r_{2}\leq n-1$

Sada je $a-b=(q_{1}-q_{2})n+r_{1}-r_{2}$.

Kako n dijeli $a-b$, dobijamo da n dijeli i $r_{1}-r_{2}$ te iz $-n+1\leq r_{1}-r_{2}\leq n-1=>r_{1}-r_{2}=0=>r_{1}=r_{2}$.

Ako a i b daju isti ostatak pri dijeljenju sa n, na analogan način slijedi da n dijeli $a-b$, tj. $a\equiv b(mod\ n)$

Iz dokazanog slijedi $a\equiv a(mod\ n)$

Iz $n|a-b$ ako i samo ako $n|b-a$ vrrijedi i $a\equiv b(mod\ n)$ ako i samo ako $b\equiv a(mod\ n)$

Neka su sada a, b, c cijeli brojevi te neka vrijedi

$a\equiv b(mod\ n)$ i $b\equiv c(mod\ n)$(a i b te b i c daju isti ostatak prije dijeljenju sa n) $=>a\equiv c(mod\ n)$

Definicija

Definicija 1

Neka su a i b cijeli brojevi i m prirodan broj. Za brojeve a i b kažemo da su kongruentni po modulu m ako vrijedi $m|a-b.$

Definicija 2

Skup koji dobijamo ako svaki član skupa Z pomnožimo sa n različitim od 0 označavamo sa _nZ tj. _nZ = (....,-3n, -2n, -n, 0, n, 2n. ....) Skup koji dobijamo ako svakom članu skupa _nZ dodamo r (0 ≤ r < │n│ označavamo _nZ +r

Primjer

• $17\equiv 5(mod\ 12)$
• $5\equiv 5(mod\ 12)$
• $24\equiv 0(mod\ 12)$
• $6\equiv -34(mod\ 40)$
• $-8\equiv 7{\pmod {5}}$
• $2\equiv -3{\pmod {5}}$
• $-3\equiv -8{\pmod {5}}$,

Napomena

Budući da $n|a-b$ ako i samo ako $-n|a-b$, gdje je $n\in \ Z\diagdown {0}$, dovoljno je posmatrati samo pozitivne brojeve n.

Osobine kongruencije

Propozicija 1

• Neka su $a,a',b,b'$ cijeli brojevi te $n$ prirodan broj. Neka je

$a\equiv a'(mod\ n)$ i $b\equiv b'(mod\ n)$ tada vrijedi

1. $a+b\equiv a'+b'(mod\ n)$
2. $a-b\equiv a'-b'(mod\ n)$
3. $a\times b\equiv a'\times b'(mod\ n)$

Dokaz

Neka je $a-a'=mn$ i $b-b'=m'n$.

$ab-a'b'=ab-ab'+ab'-a'b'=a(b-b')+(a-a')b'=am'n+b'mn$

$n$ dijeli $ab-a'b'$ pa je $ab\equiv a'b'(mod\ n)$

• Neka su $a,b,c$ cijeli brojevi i $n$ prirodan broj. Neka su brojevi $a$ i $n$ relativno prosti.

Tada vrijedi $ab\equiv ac(mod\ n)=>b\equiv c(mod\ n)$

Dokaz

Kako su $a$ i $n$ relativno prosti, postoje cijeli brojevi $x$ i $y$ takvi da je $ax+ny=1$. Iz kongruencije $ab\equiv ac(mod\ n)$ => postoji cijeli broj $k$ takav da je $a(b-c)=nk$. Množenjem prethodne jednakosti sa $x$, iz $ax=1-ny$ dobijamo $(b-c)-ny(b-c)=nkx$. Očito $n$ dijeli $b-c$ pa je $b\equiv c(mod\ n)$

Ova tvrdnja ( ne vrijedi opčenito, tj. ako $a$ i $n$ nisu relativno prosti.

Primjer

• $60\equiv 20(mod\ 5)$ tačno
• $6\equiv 2(mod\ 5)$ nije tačno

Propozicija 2

Neka je $ax\equiv ay(mod\ n)$ Tada vrijedi i $x\equiv y(mod\ n/d)$, gdje je $d=(a,n)$.

Dokaz.

$ax\equiv ay(mod\ n)=>$ postoji cijeli broj $k$ takav da vrijedi $ax-ay=kn.$ Odatle je ${\frac {a}{d}}(x-y)={\frac {nk}{d}}$ pa ${\frac {n}{d}}|{\frac {a}{d}}(x-y)$

Kako su ${\frac {n}{d}}$ i ${\frac {a}{d}}$ relativno prosti, jer nemaju zajedničkih prostih faktora, dobijamo n $d|(x-y)$ čime je tvrdnja dokazana.

Propozicija 3

Neka je $n$ prirodan broj te $a$ i $b$ cijeli brojevi takvi da je $a\equiv b(mod\ n)=>$ Tada za polinom $p(x)$ s cjelobrojnim koeficijentima vrijedi $p(a)\equiv p(b)(mod\ n)=>$

Dokaz primjenom predhodnih propozicija na $p(a)=\sum _{i=0}^{k}c_{i}a^{i}$ dobijamo

$a^{i}\equiv b^{i}(mod\ n)$ te

$c_{i}a^{i}\equiv c_{i}b^{i}(mod\ n)$

saberemo li dobijene kongruencije dobijamo

$p(a)=\sum _{i=0}^{k}c_{i}a^{i}\equiv \sum _{i=0}^{k}c_{i}b^{i}=p(b)$

Propozicija 4

Neka su $n_{1},n_{2},...n_{k}$ prirodni brojevi. Tada su sljedeće tvrdnje ekvivalentne:

$a\equiv b(mod\ n_{i})zai=1,2,...k$

$a\equiv b(mod[n_{1},n_{2},...n_{k}$

Primjer

odrediti $x\in \mathbb {Z}$ za koji vrijedi

$341x\equiv 1(mod\ 17)$

$340:17=2$ (340 je djeljivo sa17)tj

$340x\equiv 0(mod\ 17)$

Kako je $341x=340x+x$ imamo

$341x\equiv x(mod\ 17)$

Datu kongruenciju zadovoljava svaki cijeli broj $x$ koji je kongruentan $1$ modulo $17$, tj. $x\in {\begin{Bmatrix}...,-33,-16,1,18,35,...\end{Bmatrix}}$.

Potpuni i reducirani sistem ostataka

Neka je $n$ prirodan broj veći od $1$. Skup $S={\begin{Bmatrix}a_{1},a_{2},...,a_{n}\end{Bmatrix}}$ se naziva potpuni sistem ostataka modulo $n$ ako za svaki cijeli broj $b$ postoji jedinstveni $a_{i}\in S$ za koji vrijedi $b\equiv a_{i}(mod\ n)$.

Svaki potpuni sistem ostataka modulo $n$ ima tačno $n$ elemenata. Također, svaki n-člani skup koji se sastoji od cijelih brojeva međusobno nekongruentnih modulo $n$ predstavlja jedan potpuni sustem ostataka modulo $n$.

Najčešće korišten potpun sistem ostataka modulo $n$ je skup ${\begin{Bmatrix}0,1,2,...,n-1\end{Bmatrix}}$

Navedimo i nekoliko potpunih sistema ostataka modulo 5: ${\begin{Bmatrix}{0,1,2,3,4}\end{Bmatrix}}$, ${\begin{Bmatrix}{-2,-1,0,1,2}\end{Bmatrix}}$, ${\begin{Bmatrix}{1,2,3,4,5}\end{Bmatrix}}$, ${\begin{Bmatrix}{-10,-8,-4,13,39}\end{Bmatrix}}$

Postoji ih beskonačno mnogo.

Lema 1

Neka je ${\begin{Bmatrix}{a_{1},a_{2},...,a_{n}}\end{Bmatrix}}$ potpuni sistem ostataka modulo $n$. Tada je i ${\begin{Bmatrix}{b\times a_{1},b\times a_{2},...,b\times a_{n}}\end{Bmatrix}}$ potpuni sistem ostataka modulo $n$, za svaki cijeli broj $b$ za koji vrijedi $(b,n)=1$.

Lema 2

Neka su $a$ i $n$ prirodni brojevi. Kongruencija $ax\equiv b(mod\ n_{i})zai=1,2,...k$ ima rješenja ako i samo ako $d=(a,n)$ dijeli $b$. Ako je $x_{0}$ rjšenje kongruencije ${\frac {a}{d}}x\equiv {\frac {b}{d}}(mod{\frac {n}{d}}$ tada su sva međusobno nekongruentna rješenja modulo $n$ polazne kongruencije data s $x_{0},x_{0}+{\frac {n}{d}},x_{0}+{\frac {2n}{d}},...x_{0}+{\frac {(d-1)n}{d}}$

Primjer

Skupovi {1, 2, 3, 4} i {-2,-6, 6, 7} su reducirani sistemi ostataka modulo $5$, dok je {1, 5} reducirani sistem ostataka modulo $6$.

Eulerova funkcija

Glavni članak: Eulerova funkcija

Neka je n prirodan broj. Broj prirodnih brojeva u nizu 1, 2, . . . , n koji su relativno prosti sa n se označava s $\varphi (n)$ ovim je definisana funkcija $\varphi :N\to N$ koja se naziva Eulerova funkcija.

$\varphi (n)$ je broj elemenata reduciranog sistema ostataka modulo n.

Wilsonova i Lagrangeova teorema

Neka je p prost broj i a < p prirodan broj. Tada postoji prirodan broj b za koji vrijedi a · b ≡ 1 (mod p) i takav broj b se naziva multiplikativni inverz od a modulo p.

Kako su a i p relativno prosti, postoje cijeli brojevi x, y za koje vrijedi ax+py = 1, odakle slijedi ax ≡ 1 (mod p) te možemo uzeti b = x.

Svaka dva multiplikativna inverza od a modulo p međusobno su kongruentni modulo p, pa postoji jedinstveni multiplikativni inverz od a modulo p koji je prirodan broj manji od p. Općenito, ako je a ∈ N te $p\nmid a$, tada postoji multiplikativni inverz od a modulo p.

Jedna od najistaknutijih primjena nultiplikativnih inverza se pojavljuje prilikom evaluacije proizvoda (p − 1)! = 1 · 2 · 3 · · · (p − 1) modulo p, gdje je p prost broj. Sljedeća teorema se pripisuju engleskom matematićaru iz XVIII vijeka Johnu Wilsonu, iako je vjerojatno otkrivena od strane Ibn al-Hayhama u X vijeku, a prvi poznati dokaz je Lagrangeov i datira iz 1770.

Wilsonova teorema

Glavni članak: Wilsonova teorema

Ako je p prost broj tada je (p−1)! ≡ −1 (mod p).

Dokaz

Za svaki od brojeva 1, 2, . . . , p−1 postoji multiplikativni inverz modulo p. Dakle, svaki od faktora u (p−1)! = 1·2 · · · (p−1) daje 1 modulo p uproizvodu sa svojim multiplikativnim inverzom, osim faktora koji su sami sebi inverzni.

Odredimo takve faktore.

Neka je x ∈ {1, 2, . . . , p − 1} takav da vrijedi $x^{2}$ ≡ 1 (mod p). Tada p | $x^{2}-1=(x-1)(x+1)$. Kako je p prost broj i 1 ≤ x ≤ p − 1, slijedi da je ili x − 1 = 0 ili x+1 = p. Prema tome, jedini faktori u (p−1)! koji su sami sebi inverzni su 1 i p-1. Odatle dobijamo (p − 1)! ≡ 1 · (p - 1) (mod p) te (p − 1)! ≡ −1 (mod p).

Prethodni teorem ustvari daje interesantnu karakterizaciju prostih brojeva, jer vrijedi i obrat:

Propozicija

Ako prirodan broj n zadovoljava kongruenciju (n − 1)! ≡ −1(mod n), tada je n prost. Dokaz.

(n−1)! ≡ −1 (mod n) => (n−1)! ≡ −1 (mod m) za svaki m koji dijeli n. Ako je m < n, tada se m pojavljuje kao faktor od (n−1)! pa je (n−1)! ≡ 0 (mod m)

−1 ≡ 0 (mod m). Odavde je m = 1 te n nema pozitivnih djelitelja različitih od 1 i n pa je n prost.

Primjer

100! ≡ −1 (mod 101), tj. 101 | 100! + 1.

Korolar 1

Neka je p neparan prost broj. Kongruencija $x^{2}$ + 1 ≡ 0 (mod p) ima rješenja ako i samo ako je p ≡ 1 (mod 4).

Dokaz

Neka je p neparan prost broj te neka je $k={\frac {p-1}{2}}$ Korištenjem kongruencije p − i ≡ −i (mod p) u proizvodu (p − 1)! = 1 · 2 · · · k · (k + 1) · · · (p − 2) · (p − 1) za i = 1, 2, . . . , k, dobijamo (p − 1)! ≡ $(-1)^{k}(k!)^{2}$ (mod p).

Wilsonova teorema daje (p - 1)! ≡ −1 (mod p) te slijedi $(-1)^{k}(k!)^{2}$ ≡ −1 (mod p) odakle dobijamo i

$(k!)^{2}$ ≡ $(-1)^{k+1}$ (mod p).

Kako je k paran za p ≡ 1 (mod 4) slijedi $(k!)^{2}$ ≡ −1 (mod p) te je

$x=k!$ rješenje kongruencije $x^{2}$ + 1 ≡ 0 (mod p).

Neka je sada $p\equiv 3(mod\ 4)$, $=>{\frac {p-1}{2}}$ neparan. Ako je x rješenje kongruencije

$x^{2}+1\equiv 0(mod\ p)$, tada su x i p relativno prosti te je, prema Malom Fermatovom teoremu, $x^{p-1}\equiv 1(mod\ p)$. Prema tome, $1\equiv (x^{2})^{k}\equiv (-1)^{k}\equiv -1$ $(mod\ p)$ nije moguće jer je p neparan te u ovom slučaju polazna kongruencija nema rješenja.

Činjenica da kongruencija $x^{2}-1\equiv 0(mod\ p)$ ima najviše dva rješenja (nekongruentna modulo p) ima važnu generalizaciju

Lagrangeova teorema

Glavni članak: Lagrangeova teorema

Ako je p prost broj i P(x) polinom stepana n sa cjelobrojnim koeficijentima, koji nisu svi djeljivi sa p, tada kongruencija $P(x)\equiv 0(mod\ p)$ ima najviše n rješenja modulo p

Izvori

1. UVOD U TEORIJU BROJEVA / 2014
2. Modular Arithmetic
3. Modular arithmetic