Fandom

Math Wiki

Teoria numerelor

1.029pages on
this wiki
Add New Page
Comments0 Share

Ad blocker interference detected!


Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.

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

Also on Fandom

Random Wiki