Algebra

Kongruencije

Čitajući ovu stranicu dobićete odgovore na pitanja šta su kongruencije, šta su sistemi ostataka, red brojeva po datom modulu?

Pre svega ćemo definisati kongruencije.

DEFINICIJA Neka je dat prirodan broj m, veći od 1. Celi brojevi a i b su kongruentni po modulu m ako daju isti ostatak pri deljenju sa m. Piše se a ≡ b (mod m).

TEOREMA

1. a ≡ b (mod m) ako i samo ako je a = mt + b za neki ceo broj t.

2. a ≡ b (mod m) ako i samo ako je razlika brojeva a i b deljiva sa m.

3. Biti kongruentan po datom modulu je relacija ekvivalencije u skupu celih brojeva.

TEOREMA

1. Ako je a ≡ b (mod m) i c ≡ d (mod m), onda za svaka dva cela broja x, y važi ax + cy ≡ bx + dy (mod m).

2. Ako je a ≡ b (mod m) i c ≡ d (mod m), onda je ac ≡ bd (mod m).

3. Ako je a ≡ b (mod m) i m = αd, d > 1, onda je a ≡ b (mod d).

4. Ako je P(x) polinom po x sa celobrojnim koeficijentima, onda iz a ≡ b (mod m) sledi da je P(a) ≡ P(b) (mod m).

TEOREMA

1. Ako su a i m uzajamno prosti i ax ≡ ay (mod m), onda je x ≡ y (mod m).

2. ax ≡ ay (mod m) ako i samo ako x ≡ y (mod m /(a,m) ).

3. x ≡ y (mod a) i x ≡ y (mod b) ako i samo ako x ≡ y (mod [a, b]).

Kongruencije -sistemi ostataka

DEFINICIJA:Skup od m celih brojeva u kome ne postoji ni jedan par brojeva kongruentnih po modulu m zove se potpuni sistem ostataka po modulu m.

TEOREMA:

1. Skup {0,1,2,…,m−1} je potpuni sistem ostataka po modulu m.

2. Ako je m neparan broj, skup {−(m–1)/2,…,−1,0,1,…,(m–1)/2 }je potpuni sistem ostataka po modulu m.

Ako je m paran svaki od skupova {−m/2+1,…,-1,0,1,…,m/2} i {−m/2,…,−1,0,1,…,m/2−1} predstavlja potpuni sistem ostataka po modulu m.

3. Ako je {x₁, x₂,…, x_m} potpuni sistem ostataka po modulu m i (a,m) = 1, tada je i {ax₁+b,ax₂+b,…, ax_m+b} potpuni sistem ostataka po modulu m, za svaki ceo broj b.

PRIMER:Skupovi {0,1,2,3,4,5,6,7} i {16,9,−6,11,44,5,14,31} su potpuni sistemi ostataka po modulu 8.

DEFINICIJA: Skup svih elemenata potpunog sistema ostataka po modulu m koji su relativno prosti sa m naziva se svedeni (redukovani) sistem ostataka po modulu m.

PRIMER:{1,3,5,7} i {9,11,5,31} su svedeni sistemi ostataka po modulu 8.

DEFINICIJA:Broj prirodnih brojeva koji nisu veći od datog prirodnog broja m i relativno su prosti sa njim, tj. broj elemenata proizvoljnog svedenog sistema ostataka po modulu m označava se sa φ(m). φ je Ojlerova funkcija.

Ako je p prost broj, tada je φ(p) = p − 1.

φ(1)=φ(2)=1,φ(3)=φ(4)=φ(6)=2 itd.

TEOREMA:Ako je {x1,x2,…,xφ(m)} svedeni sistem ostataka po modulumi (a,m)=1, tada je i {ax1,ax2,…, axφ(m)} svedeni sistem ostataka po modulu m.

TEOREMA:Ako je n=p^α¹ p^α²··· p^α^k kanonska faktorizacija broja n, sledi

φ(n)=n(1–1/p1)(1–1/p2)···(1–/pk)=p^α¹⁻¹p^α²⁻¹··· p^α^k⁻¹(p1−1)(p2−1)···(pk−1).

Kongruencije -Poredak broja po datom modulu

DEFINICIJA: Poredak broja a po modulu m je najmanji prirodan broj t, ako postoji, za koji važi a^t ≡ 1 (mod m).

PRIMER:Poredak broja 3 po modulu 11 je 5, jer 3¹, 3², 3³, 3⁴ ̸≡ 1 (mod 11), a 3⁵ ≡ 1 (mod 11).

TEOREMA: Poredak broja a po modulu m postoji ako i samo ako su a i m uzajamno prosti.

TEOREMA: Ako je t poredak broja a po modulu mi a^s ≡ 1 (mod m), tada t | s. Specijalno, t | φ(m).

POSLEDICA:Ako je t poredak broja a po modulu m, tada je ax ≡ ay (mod m) ako i samo ako x ≡ y (mod t).

DEFINICIJA Ako je poredak broja a po modulu m jednak φ(m), broj a se naziva primitivnim korenom po modulu m.

TEOREMA

Ako je a primitivan koren po modulu m, brojevi 1 = a⁰, a¹, a², . . . , a^φ⁽^m⁾⁻¹

obrazuju svedeni sistem ostataka po modulu m.

POSLEDICA:Ako je p prost broj i a primitivan koren po modulu p, tada brojevi 1, a, a², . . . , a^p⁻²obrazuju svedeni sistem ostataka po modulu p.

PRIMER:2 je primitivan koren po modulu 11, pa brojevi 1, 2, 22 =4, 23 = 8, 24 ≡ 5, 25 ≡ 10, 26 ≡ 9, 27 ≡ 7, 28 ≡ 3, 29 ≡ 6 (mod 11) obrazuju svedeni sistem ostataka po modulu 11.

TEOREMA (Vilson) Ako je p prost broj, tada važi: (p − 1)! ≡ −1 (mod p).

TEOREMA Kongruencija kx ≡ 1 (mod m) ima bar jedno rešenje (po x) ako i samo ako je broj k uzajamno prost sa m, i tada svaka od kongruencija kx ≡ n (mod m) ima rešenje po x.

Kineska teorema o ostacima

TEOREMA Neka su a₁, a₂, . . . , a_r proizvoljni celi brojevi i neka su m₁,m₂, . . . ,m_r po parovima uzajamno prosti prirodni brojevi, tj. (m_i,m_j) = 1 za i ̸= j. Tada postoji rešenje sistema kongruencija:

(1) x ≡ a₁ (mod m₁), x ≡ a₂ (mod m₂), . . . , x ≡ a_r (mod m_r).

Ako je x₀ jedno rešenje sistema jednašina (1), tada je x rešenje sistema

ako i samo ako je oblika x₀ + km, gde je k proizvoljan ceo broj, a m = m₁m₂ · ·mr.

Sledeći aplet sadrži rešene zadatke na temu kongruencije.

Povratak na stranu Algebra