Modularna aritmetika

desno|250px
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 i a = q_2 \times n+r_2, pri čemu vrijedi 0 \le r_1, r_2 \le 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 \le r_1 - r_2 \le 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 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
#a+b  \equiv a'+b' (mod  \ n)
#a-b  \equiv a'-b' (mod  \ n)
#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_ia^i dobijamo

a^i   \equiv b^ i (mod  \ n) te

c_ia^i   \equiv c_ib^ i (mod  \ n)

saberemo li dobijene kongruencije dobijamo

p(a)=\sum_{i=0}^k c_ia^i \equiv  \sum_{i=0}^k c_ib^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) za i= 1, 2, ... k 

a   \equiv b (mod  [ n_1, n_2,... n_k 

;Primjer

odrediti x \in  \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) za i= 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 
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 \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 
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 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 
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
# UVOD U TEORIJU BROJEVA / 2014
# Modular Arithmetic
# Modular arithmetic
## Reference

Kategorija:Teorija grupa
Kategorija:Konačni prstenovi