3204.

78

TEKST ZADATKA

U skupu N \mathbb{N} definisana je relacija xρy⇔3∣x+2y. x \rho y \Leftrightarrow 3 \mid x + 2y . Dokazati da je ρ \rho relacija ekvivalencije i odrediti klase ekvivalencije.

REŠENJE ZADATKA

Da bi relacija bila relacija ekvivalencije, mora biti refleksivna, simetrična i tranzitivna. Ispitaćemo svako od ovih svojstava.

Proveravamo refleksivnost. Za svako x∈N x \in \mathbb{N} mora važiti xρx, x \rho x , odnosno 3∣x+2x. 3 \mid x + 2x .

x+2x=3xx + 2x = 3x

Kako je 3x 3x očigledno deljivo sa 3 za svaki prirodan broj x, x , zaključujemo da je relacija refleksivna.

3∣3x  ⟹  xρx3 \mid 3x \implies x \rho x

Proveravamo simetričnost. Pretpostavimo da važi xρy, x \rho y , što znači da 3∣x+2y. 3 \mid x + 2y . Treba dokazati da važi yρx, y \rho x , odnosno 3∣y+2x. 3 \mid y + 2x .

x+2y=3k,k∈Zx + 2y = 3k, \quad k \in \mathbb{Z}

Posmatrajmo zbir izraza x+2y x + 2y i y+2x: y + 2x :

(x+2y)+(y+2x)=3x+3y=3(x+y)(x + 2y) + (y + 2x) = 3x + 3y = 3(x + y)

Izrazimo y+2x y + 2x preko poznatih vrednosti:

y+2x=3(x+y)−(x+2y)=3(x+y)−3k=3(x+y−k)y + 2x = 3(x + y) - (x + 2y) = 3(x + y) - 3k = 3(x + y - k)

Pošto je x+y−k x + y - k ceo broj, sledi da je y+2x y + 2x deljivo sa 3, pa je relacija simetrična.

3∣y+2x  ⟹  yρx3 \mid y + 2x \implies y \rho x

Proveravamo tranzitivnost. Pretpostavimo da važi xρy x \rho y i yρz. y \rho z . To znači da 3∣x+2y 3 \mid x + 2y i 3∣y+2z. 3 \mid y + 2z . Treba dokazati da 3∣x+2z. 3 \mid x + 2z .

x+2y=3k1iy+2z=3k2x + 2y = 3k_1 \quad \text{i} \quad y + 2z = 3k_2

Sabiranjem ove dve jednakosti dobijamo:

(x+2y)+(y+2z)=3k1+3k2(x + 2y) + (y + 2z) = 3k_1 + 3k_2

Sređivanjem leve strane izdvajamo izraz x+2z: x + 2z :

x+3y+2z=3(k1+k2)  ⟹  x+2z=3(k1+k2−y)x + 3y + 2z = 3(k_1 + k_2) \implies x + 2z = 3(k_1 + k_2 - y)

Pošto je k1+k2−y k_1 + k_2 - y ceo broj, sledi da je x+2z x + 2z deljivo sa 3, pa je relacija tranzitivna.

3∣x+2z  ⟹  xρz3 \mid x + 2z \implies x \rho z

Pošto je relacija ρ \rho refleksivna, simetrična i tranzitivna, ona je relacija ekvivalencije.

Sada određujemo klase ekvivalencije. Primetimo da se uslov 3∣x+2y 3 \mid x + 2y može zapisati drugačije. Kako je 2y=3y−y, 2y = 3y - y , imamo:

x+2y=x+3y−y=(x−y)+3yx + 2y = x + 3y - y = (x - y) + 3y

Pošto je 3y 3y uvek deljivo sa 3, uslov 3∣x+2y 3 \mid x + 2y je ekvivalentan sa 3∣x−y, 3 \mid x - y , što znači da x x i y y daju isti ostatak pri deljenju sa 3.

x≡y(mod3)x \equiv y \pmod{3}

Dakle, skup prirodnih brojeva se razbija na tri klase ekvivalencije, u zavisnosti od ostatka pri deljenju sa 3 (ostatak 1, 2 ili 0):

C1={3k−2∣k∈N}={1,4,7,10,… }C2={3k−1∣k∈N}={2,5,8,11,… }C3={3k∣k∈N}={3,6,9,12,… }\begin{aligned} C_1 &= \{3k - 2 \mid k \in \mathbb{N}\} = \{1, 4, 7, 10, \dots\} \\ C_2 &= \{3k - 1 \mid k \in \mathbb{N}\} = \{2, 5, 8, 11, \dots\} \\ C_3 &= \{3k \mid k \in \mathbb{N}\} = \{3, 6, 9, 12, \dots\} \end{aligned}