FANDOM


Multiplii unui număr faţă de un modul dat Edit

Teorema 1. Fie $ a, m \in \mathbb N^*, \; (a, m) =1 \! $ şi $ r_k \! $ restul împărţirii lui $ ka \! $ la m, $ k \in \mathbb N^*. \! $ Atunci șirul $ (r_k)_{k \in \mathbb N^*} \! $ este periodic; o perioadă are m termeni diferiţi între ei.

Demonstraţie. $ r_{k+m} \! $ este restul împărţirii lui $ (k+m)a \! $ la m. Dar $ \frac{(k+m)a}{m} = \frac{ka}{m} + a \! $ şi cum $ a \in \mathbb N, \! $ restul $ r_{k+m} \! $ este cel al împărţirii lui k la m adică $ r_k. \! $ Deci $ r_{k+m} = r_k \! $ adică şirul este periodic cu perioada m.


Acum să presupunem că există $ i, j \in \mathbb N^*, \; 1 \le i < j \le m \! $ astfel că $ r_i = r_j. \! $ Deci numerele $ ia, ja \! $ dau acelaşi rest la împărţirea cu m adică $ m | ja-ia \; \Leftrightarrow \; m | a(j-i). \! $ Cum însă a şi m sunt prime între ele (ipoteză), rezultă că $ m | j-i \! $ ceea ce este imposibil deoarece $ 0<j-i <m. \! $ Aşadar, numerele $ r_1, r_2, \cdots , r_m \! $ sunt distincte două câte două şi ţinând cont că şirul este periodic, rezultă că toate perioadele au termenii diferiţi între ei.


Observaţii.

1) Numerele $ r_1, r_2, \cdots , r_m \! $ nu pot avea decât valorile $ 0, 1, 2, \cdots , m \! $ (eventual într-o altă ordine) şi avem $ r_m=0. \! $

2) Orice m termeni consecutivi ai şirului $ (r_k)_{k \in \mathbb N^*} \! $ nu pot avea decât valorile $ 0, 1, 2, \cdots , m \! $ (eventual într-o altă ordine).

3) Dacă $ a_1 \in \mathbb N^* \! $ astfel că $ m| a_1 - a, \! $ atunci şirul de resturi dat de multiplii lui $ a_1 \! $ este acelaşi cu şirul de resturi dat de multiplii lui a.

4) Avem:

$ r_{i+1} \equiv r_i + a \; (mod \; m). \! $

5) Teorema rămâne valabilă dacă vom considera $ r_k \! $ ca fiind restul împărţirii lui $ ka+b \! $ la m, $ k \in \mathbb N^* \! $ unde b este un număr dat.

6) Teorema este valabilă şi pentru şirul $ (r_k)_{k \in \mathbb Z}. \! $


Aplicaţii Edit

1) Rezolvarea congruenţei $ ax \equiv b \; (mod \; m) \! $ în cazul (a, m) = 1.

Să presupunem mai întâi că $ b<m. \! $ Conform teoremei 1, există un singur număr din şirul $ a, 2a, 3a, \cdots , ma \! $ care prin împărţire la m să dea restul b şi fie acesta $ ax_0. \! $ Deoarece şirul resturilor este periodic, rezultă că soluţiile sunt de tip $ x=x_0 + km, \; k \in \mathbb N. \! $

Cazul $ b >m \! $ se reduce imediat la cazul $ b<m. \! $ Dacă se dă $ ax \equiv b_1 \; (mod \; m) \! $ cu $ b_1 >m, \! $ împărţim întâi pe $ b_1 \! $ la m; fie $ b_1 = mq+ b, \! $ cu $ b<m. \! $ Avem $ ax \equiv b_1 \; \Leftrightarrow \; ax \equiv b \! $ şi obţinem cazul precedent. Conform observaţiei 3), cazul a>m este reductibil la cazul $ a<m. \! $


2) Rezolvarea ecuaţiei $ ax+by = c \! $ în numere întregi $ \left ( a, b, c \in \mathbb Z \right ). \! $

Dacă $ (a, b) = 1 \! $ ecuaţia are soluţii. Dând lui x un număr de $ |b| \! $ valori consecutive, una din aceste valori, $ x_0, \! $ satisface relaţia $ ax_0 \equiv c \; (mod \; b). \! $ Înlocuind în această ecuaţie obţinem: $ y_0 = \frac{c-ax_0}{b}. \! $ (Avem $ y_0 \in \mathbb Z \! $ căci $ b| c-ax_0 \! $). Soluţia generală va fi:

$ x=x_0 + kb, \; \; y=y_0 -ka, \; \; k \in \mathbb Z \! $   (1)

Într-adevăr, aceste valori verifică ecuaţia pentru orice $ k \in \mathbb Z. \! $

Să arătăm că în afară de soluţiile date de (1) nu mai sunt altele. Dacă $ x, y \! $ este o soluţie a ecuaţiei, să arătăm ca există $ k \in \mathbb Z \! $ astfel încât să fie satisfăcute relaţiile (1). Într-adevăr, avem $ ax+ by = c = ax_0 + by_0 \! $ adică $ a(x-x_0) = -b (y-y_0). \! $ Cum b este prim cu a, avem $ b| x-x_0 \! $ deci există un $ k \in \mathbb Z \! $ astfel ca $ x-x_0 = kb \! $ sau $ x=x_0 + kb. \! $ De asemenea, avem $ y=y_0-ka. \! $

Vezi şi Edit


Resurse Edit