UNIVERZITET U NOVOM SADU
PRIRODNO-MATEMATI
Č
KI FAKULTET
DEPARTMAN ZA
MATEMATIKU I INFORMATIKU
Vojko Nestorovi
ć
BROJEVNE KONGRUENCIJE
- MASTER RAD -
Mentor, dr Siniša Crvenkovi
ć
Novi Sad, 2011.
i
Sadržaj
Predgovor
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii
1 Deljivost celih brojeva
. . . . . . . . . . . . . . . . . . . . . 1
1.1
Osnovne osobine . . . . . . . . . . . . . . . . . . . . .1
1.2
Najve
ć
i zajedni
č
ki delilac . . . . . . . . . . . . . . . . . . 4
1.3
Osnovna teorema aritmetike . . . . . . . . . . . . . . . 7
1.4
Linearna Diofantova jedna
č
ina . . . . . . . . . . . . . 10
2 Prosti brojevi
. . . . . . . . . . . . . . . . . . . . . . . . .14
2.1 Eratostenovo sito . . . . . . . . . . . . . . . . . . . . 14
2.2 Beskona
č
an skup prostih brojeva . . . . . . . . . . . .15
2.3 Mersenovi brojevi . . . . . . . . . . . . . . . . . . . 17
3 Kongruencije brojeva
. . . . . . . . . . . . . . . . . . . . 19
3.1 Definicija relacije kongruencije . . . . . . . . . . . . 19
3.2 Osobine relacije kongruencije . . . . . . . . . . . . . 20
4 Klase i sistemi ostataka
. . . . . . . . . . . . . . . . . . . 27
4.1 Klase ostataka po datom modulu . . . . . . . . . . . .27
4.2 Klase ostataka relativno proste sa modulom
m
. . . . 29
4.3 Potpun sistem ostataka . . . . . . . . . . . . . . . . . 30
4.4 Redukovan sistem ostataka . . . . . . . . . . . . . . .34
5 Ojlerova teorema
. . . . . . . . . . . . . . . . . . . . . . 37
5.1 Ojlerova funkcija . . . . . . . . . . . . . . . . . . . . 37
5.2 Ojlerova teorema . . . . . . . . . . . . . . . . . . . . 39
6 Kongruencije s jednom nepoznatom
. . . . . . . . . . . . 46
6.1 Linearne kongruencije
≡ (
)
. . . . . 46
6.2 Sistemi linearnih kongruencija . . . . . . . . . . . . . 50
6.3 Kvadratne kongruencije . . . . . . . . . . . . . . . . 55
6.4 Kongruencije višeg reda . . . . . . . . . . . . . . . . 64
Zaklju
č
ak
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .78
Literatura
. . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
Biografija
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .80
Klju
č
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
1
1 Deljivost celih brojeva
1.1 Osnovne osobine
Definicija 1.1
Neka su a i b celi brojevi. Ako postoji ceo broj m
takav da je b = ma, tada kažemo da je a
delitelj
ili
faktor
broja b i
da je b
sadržilac
ili
višekratnik
broja a. To zapisujemo ovako a
|
b.
Na primer: 3
|
9, 6
|
30, 5
|
0.
Ako
a
|
b
, o
č
igledno je i
a
|
(-b)
,
(-a)
|
b
i
(-a)
|
(-b)
. Zato se, pri
prou
č
avanju deljivosti, naj
č
eš
ć
e ograni
č
avamo na nenegativne cele
brojeve.
Definicija 1.2
Broj a nazivamo
pravi delitelj
od b, ako je a
|
b i
a
≠
b.
U slede
ć
oj teoremi date su neke od najvažnijih osobina relacije deljivosti.
Teorema 1.1
Neka su a, b, c proizvoljni nenegativni celi brojevi.
Tada važi:
a)
ako je a
|
b i b
|
c, tada je a
|
c;
b) ako je a
|
b i b
≠
0, tada je 0 < a
≤
b;
b)
ako je a
|
b i a
|
c, tada je, za proizvoljne cele brojeve x i y,
a
|
(bx + cy);
d) ako a
|
b i b
|
a, tada je a = b.
Dokaz.
a) Ako je
a
|
b
i
b
|
c
, tada postoje celi brojevi
m
i
n
takvi da je
b = ma
i
c = nb
. Tada je,
c = nma
, a kako je
mn
ceo
broj, sledi da je
a
|
c
.
b) Ako je
a
|
b
, tada postoji nenegativan ceo broj
m
takav da je
b = ma
. Kako je
b > 0
, tada su i
a
i
m
pozitivni brojevi, tj.
1
≤
a
i
1
≤
m
. Sledi da je
b = am
≥
a·1 = a > 0
.
3
Broj
q
naziva se koli
č
nik, a broj
r
ostatak pri deljenju
a
sa
b
.
Algoritam deljenja se koristi u klasifikaciji brojeva. Na primer za
b = 2
,
ako je
r = 1
(a = 2q + 1)
tada kažemo da je
a
neparan broj, a ako je
r = 0 (a = 2q)
, tada je
a
paran broj. Sli
č
na klasifikacija se uspostavlja
za
b = 3, 4, ...
Pozitivan ceo broj
p
ve
ć
i od
1
je prost ako su mu jedini pozitivni
delitelji brojevi
1
i
p
. Za pozitivan ceo broj ve
ć
i od
1
koji nije prost,
kažemo da je
složen
. Svaki složen broj
n
, ima delitelje razli
č
ite od
1
i
n
.
1.2 Najve
ć
i zajedni
č
ki delilac
Definicija 1.3
Neka su a i b nenegativni celi brojevi takvi da je
bar jedan ve
ć
i od 0. Za broj k kažemo da je
zajedni
č
ki delitelj
brojeva
a i b, ako je k
|
a i k
|
b.
Definicija 1.4
Najve
ć
i pozitivan ceo broj koji je delitelj i od a i od
b, naziva se
najve
ć
i zajedni
č
ki delitelj
brojeva a i b. Ozna
č
avamo ga
sa NZD (a, b) ili samo (a, b). On uvek postoji, što se lako dokazuje,
polaze
ć
i od principa dobrog ure
đ
enja.
Na primer:
NZD (4, 16) = 4, NZD (0, 5) = 5, NZD (30, 50) = 10,
NZD (8, 15) = 1.
Da bismo dokazali da je
d = NZD (a, b)
, treba dokazati ta
č
nost
slede
ć
eg tvr
đ
enja:
(i)
d
|
a
i
d
|
b
(ii) ako
k
|
a
i
k
|
b
, tada je
k
|
d
.
Teorema 1.3
Najve
ć
i zajedni
č
ki delitelj dva cela broja, od kojih je
bar jedan razli
č
it od 0, je jedinstven.
Dokaz.
Ako je
d = NZD (a, b)
i
d' = NZD (a, b)
, tada je
d | d'
i
d' | d
, ako primenimo teoremu 1.1 (d) sledi da je
d = d'
.
■
