Aritmetica.

1 Multimea numerelor naturale

Calitatea unei propozitii matematice de a fi adevarata (sau falsa) se demonstreaza(numim atunci propozitia respectiva teorema, lema, propozitie, corolar, etc) sau esteacceptata ca atare (ın acest caz propozitia respectiva se numeste axioma). De micistim ca 1 + 1 = 2 este o propozitie matematica adevarata. Poate fi demonstrataaceasta propozitie sau trebuie sa o consideram ca pe o axioma? Alte cateva propozitiimatematice adevarate cu referinta la numerele naturale: proprietatile adunarii,respectiv ınmultirii numerelor naturale, inductia matematica. Putem demonstraaceste propozitii?

In cadrul acestui curs vom ıncerca sa raspundem la aceste ıntrebari. Pentruaceasta este necesara o introducere riguroasa, axiomatica a notiunii de numar nat-ural.

Necesitatea si utilitatea introducerii axiomatice a multimii numerelor naturaleapare evidenta abia in secolul XIX. La ınceputul secolului XIX, Carl Friedrich Gausspropune o abordare filozofica numerelor, considerand ca numerele sunt concepte dis-tincte de spatiu si timp, ın sensul ca sunt o creatie pura a mintii umane. In 1858,Julius Wilhelm Richard Dedekind propune o metoda de constructie a numerelorreale plecand de la cele rationale, metoda cunoscuta astazi ca metoda taieturilor alui Dedekind. Numerele rationale la randul lor pot fi construite plecand de la celeıntregi, iar acestea folosind numerele naturale. In acest mod ajungem la ıntrebariprecum: ce este un numar natural? cum poate fi introdusa multimea numerelornaturale? In 1860, Hermann Grassmann evidentiaza rolul notiunii de succesor sia inductiei ın introducerea notiunii de numar natural si ın demonstrarea unor pro-prietati ale acestora. In 1888, Richard Dedekind propune o colectie de axiome pen-tru numerele naturale, iar ın 1889 Giuseppe Peano publica o versiune mai riguroasaacestor axiome ın “Arithmetices principia, nova methodo exposita”.

1

In cadrul acestui curs vom introduce notiune de numar natural cu ajutorul sis-temului axiomatic al lui Peano (cunscut si ca Peano-Dedekind). Pentru acest sistemaxiomatic notiunile primare sunt: notiunea de numar natural (un element al uneimultimi N) si numarul natural zero (un element fixat al multimii N) iar relatia pri-mara este cea de succesor. In continuare presupunem cunoscute elemente de teoriamultimilor, notiunile de functie, functie injectiva, surjectiva, bijectiva.

Fie N o multime nevida, 0 ∈ N un element fixat al sau si o functie σ : N −→ N,pentru care sunt satisfacute urmatoarele axiome (Axiomele lui Peano):

P1: 0 /∈ σ(N) (0 nu este succesorul unui numar natural);

P2: σ este aplicatie injectiva (la elemente distincte ale multimii N corespund suc-cesori distincti);

P3: (Axioma inductiei) daca M ⊂ N astfel ıncat 0 ∈M si ∀m ∈M =⇒ σ(m) ∈Matunci M = N.

Convenim sa numim tripleta (N, 0, σ) un sistem Peano. In acest context, N senumeste multime a numerelor naturale, elementul fixat 0 ∈ N se numeste elementulzero (sau nul), iar functia σ se numeste functie de succesiune.Principiul I al inductiei matematice. (PI) Fie P (n) o propozitie ce poate fiasociata cu orice numar natural n. Daca P (0) este adevarata si pentru un numarnatural arbitrar m avem ca P (m) adevarata implica P (σ(m)) adevarata, atunciP (n) este adevarata pentru orice numar natural n.

PI al inductiei matematice este o consecinta imediata a axiomei inductiei matem-atice (P3).

Propozitia 1 Fie (N, 0, σ) un sistem Peano. Orice numar natural nenul este suc-cesorul unui numar natural.

Demonstratie. Notam M := {0} ∪ σ(N). Vom demonstra, folosind axiomainductie, P3, ca M = N. Avem ca 0 ∈ M . Pentru ∀m ∈ M , m 6= 0 se obtineca m ∈ σ(N) ⊂ N. In consecinta σ(m) ∈ σ(N) ⊂M . Conform P3 se obtine M = Nsi deci orice numar natural nenul este succesorul unui numar natural.

In continuare demonstram ca oricare doua sisteme Peano sunt ”echivalente”, ceeace implica ”unicitatea” (modulo aceasta echivalenta) multimii numerelor naturale.

Teorema 1 (Teorema recursiei) Fie (N, 0, σ) un sistem Peano. Pentru orice tripleta(A, θ, λ), exista o unica functie f : N −→ A astfel ıncat f(0) = θ si urmatoarea di-agrama este comutativa:

N σ−→ Nf ↓ ↓ fA λ−→ A

(1)

2

Demonstratie. Existenta functiei f: Vom construi functia f ca fiind o relatieparticulara, deci o submultime a produsului cartezian N × A. Pentru aceasta vomconsidera o familie F de submultimi ale produsuli cartezian N × A care satisfaccerintele teoremei. Functia f cautata va fi un element minimal al lui F . Consideram

F = {U ⊂ N× A, (0, θ) ∈ U si (n, a) ∈ U =⇒ (σ(n), λ(a)) ∈ U}.

Deoarece N×A ∈ F se obtine ca familia F este nevida. In plus, pentru orice familie{Ui, i ∈ I}, Ui ∈ F ,∀i ∈ I implica ∩i∈IUi ∈ F . Vom nota f = ∩U∈FU si deci f ∈ F .

Vom arata mai ıntai ca f este functie, ceea ce ınseamna ca satisface urmatoareledoua conditii:

i) ∀n ∈ N, ∃a ∈ A astfel ıncat (n, a) ∈ f ;

ii) daca (n, a) ∈ f si (n, a′) ∈ f atunci a = a′.

Vom demonstra conditia i) folosind axioma inductiei. Vom nota

M = {n ∈ N,∃a ∈ A, a.i.(n, a) ∈ f}.

Deoarece f ∈ F avem ca (0, θ) ∈ f si deci 0 ∈ M . In plus pentru n ∈ M avemca exista a ∈ A, astfel ıncat (n, a) ∈ f . Folosind din nou conditia f ∈ F se obtine(σ(n), λ(a)) ∈ f si deci σ(n) ∈M . Folosind axioma inductiei rezulta ca M = N.

Vom demonstra conditia ii) folosind din nou axioma inductiei. Vom nota

M ′ = {n ∈ N, (n, a) ∈ f si (n, a′) ∈ f =⇒ a = a′}.

Prin reducere la absurd presupunem ca 0 /∈ M ′. Cum (0, θ) ∈ f obtinem ca∃a 6= θ a.ı. (0, a) ∈ f . Consideram f1 = f \ {(0, a)}, deci f1 ⊂ f , f1 6= f . Aratamacum ca f1 ∈ F . Deoarece (0, θ) ∈ f si θ 6= a rezulta (0, θ) ∈ f1. In plus pentru(n, b) ∈ f1 ⊂ f , deoarece σ(n) 6= 0, se obtine (σ(n), λ(b)) ∈ f1. In consecinta f1 ∈ F ,ceea ce contrazice minimalitatea lui f . Am demonstrat astfel ca (0, θ) ∈ f cu θ unic,ceea ce ınseamna ca 0 ∈M ′.

Fie n ∈ M ′, deci exista un unic b ∈ A a.ı. (n, b) ∈∈ f . Obtinem mai ıntai ca(σ(n), λ(b)) ∈ f . Prin reducere la absurd vom presupune ca σ(n) /∈ M ′. Existadeci c 6= λ(b) a.ı. (σ(n), c) ∈ f . Vom considera f2 = f \ {(σ(n), c)}, deci f2 ⊂ f ,f2 6= f . Aratam acum ca f2 ∈ F . Deoarece (0, θ) ∈ f si σ(n) 6= 0 rezulta (0, θ) ∈ f2.Fie acum (m, s) ∈ f2 ⊂ f , de unde rezulta ca (σ(m), λ(s)) ∈ f . Avem douaposibilitati. Daca σ(m) 6= σ(n), se obtine ca m 6= n si deci (σ(m), λ(s)) ∈ f2. Dacaσ(m) = σ(n) atunci m = n, adica (m, s) = (n, s) ∈ f si din unicitatea lui b avem s =b. Prin urmare (σ(m), λ(s)) = (σ(n), λ(b) 6= (σ(n), c) si deci (σ(m), λ(s)) ∈ f2. Inconsecinta f2 ∈ F , ceea ce contrazice minimalitatea lui f . Prin urmare presupunerea

3

facuta este falsa si deci σ(n) ∈M ′. Folosind axioma inductiei matematice se obtineM ′ = N si ın acest mod am demonstrat ca f este o functie.

Folosind notatiile uzuale pentru functii, conditia (0, θ) ∈ f se scrie f(0) = θ, iarconditia (n, a) ∈ f =⇒ (σ(n), λ(a)) ∈ f se scrie f(σ(n)) = λ(f(n)) si deci diagrama(1) este comutativa. Aceasta inseamna ca functia f satisface conditiile Teoremei.Unicitatea functie f: Fie g : N −→ A astfel ıncat g(0) = θ si diagrama (1) estecomutativa. Vom nota M = {n ∈ N, f(n) = g(n)}. Prin definitie 0 ∈M . Daca m ∈M atunci f(m) = g(m) ceea ce implica λ(f(m)) = λ(g(m)). Din comutativitateadiagramei (1) pentru ambele functii f si g avem f(σ(m)) = g(σ(m)) si deci σ(m) ∈M . Conform cu P3 obtinem M = N ceea ce implica g = f .

Teorema 2 Fie (N, 0, σ) un sistem Peano. Pentru orice sistem Peano (A, θ, λ),exista o unica bijectie f : N −→ A astfel ıncat f(0) = θ si diagrama (1) estecomutativa.

Demonstratie. Existenta si unicitatea functiei f a fost demonstrata ın Teoremarecursiei. Vom demonstra acum bijectivitatea acestei functii. Demontram mai ıntaisurjectivitatea. Notam B := {a ∈ A, ∃n ∈ N a.i. a = f(n)}. Deoarece f(0) = θavem ca θ ∈ B. Pentru ∀a ∈ B exista n ∈ N astfel ıncat a = f(n). Obtinem caλ(a) = λ(f(n)) = f(σ(n)) ceea ce ınseamna ca λ(a) ∈ B. Conform P3, pentrusistemul (A, θ, λ), obtinem B = A ceea ce ınseamna ca f este surjectiva.

Pentru a demonstra injectivitatea functiei f vom nota B = {a ∈ A,∃ unic n ∈N a.i. a = f(n)}. Mai ıntai aratam ca θ ∈ B. Stim ca θ = f(0). Prin reducere laabsurd presupunem ca exista n 6= 0, n ∈ N astfel ıncat θ = f(n). Deoarece n 6= 0,conform Propozitiei 1, ∃m ∈ N astfel ıncat n = σ(m) si deci θ = f(σ(m)) = λ(f(m))ceea ce contrazice P1 pentru sistemul (A, θ, λ).

Consideram a ∈ B ceea ce ınseamna ca exista un unic n ∈ N astfel ıncat a = f(n).Se obtine imediat ca λ(a) = λ(f(n)) = f(σ(n)). Vrem sa demostram ca λ(a) ∈ B,ceea ce se reduce la a arata unicitatea lui σ(n). Fie u ∈ N astfel ca λ(a) = f(u). Dacau = 0 atunci λ(a) = f(0) = θ si se contrazice P1. In consecinta u 6= 0 si conformPropozitiei (1), u = σ(m). Avem deci λ(a) = f(σ(m) = λ(f(m)) = λ(f(n)) sifolosind injectivitatea aplicatiei λ se obtine a = f(m) = f(n). Folosind unicitatealui n astfel ıncat a = f(n) se obtine m = n si σ(n) = σ(m) = u, deci σ(n) este uniccu proprietatea λ(a) = f(σ(n)).

Observatie. Teorema precedenta afirma ca orice doua sisteme Peano suntechivalente modulo o bijectie. In consecinta, pana la o bijectie, multimea numerelornaturale este unica.

Pentru un sistem Peano (N, 0, σ) vom nota 1 = σ(0), 2 = σ(1), 3 = σ(2), ..., ceeace ınseamna ca putem scrie N = {0, 1, 2, 3, 4, ...}. Pentru moment 2 este un simbolpentru a desemna succesorul lui 1, care la randul sa este succesorul lui 0, numarul

4

natural fixat initial. Vom arata (demonstra) ca putem defini o operatie + pe N, fatade care are loc 1 + 1 = 2.

Vom nota N∗ := N\{0} = σ(N) multimea numerelor naturale nenule.

Exercitiul 1 Sa se demonstreze ca daca A este o multime finita si f : A −→ Aeste o functie, atunci urmatoarele afirmatii sunt echivalente:

1) f este injectiva;

2) f este surjectiva;

3) f este bijectiva.

Propozitia 2 Daca (N, 0, σ) este un sistem Peano, atunci N este o multime infinita.

Demonstratie. Sa presupunem prin reducere la absurd ca multimea numerelor nat-urale este finita. Deoarece functia σ : N −→ N este injectiva, conform Exercitiului1 se obtine ca σ este surjectiva, ceea ce contrazice P1: 0 /∈ σ(N).

Exercitiul 2 Fie (N, 0, σ) un sistem Peano si m ∈ N un element fixat. Notam

Nm = {n ∈ N,∃k ∈ N, n = (σ ◦ · · · ◦ σ︸ ︷︷ ︸k ori

)(m)} = {m,σ(m), σ2(m) = (σ ◦ σ)(m), ....}

si σm restrictia aplicatiei σ la submultimea Nm ⊂ N. Sa se demonstreze ca (Nm,m, σm)este un sistem Peano.

Observatie. Principiul I al inductiei matematice poate fi reformulat corespunzatorsistemului Peano (Nm,m, σm). Fie P (n) o propozitie matematica ce poate fi asociatacu orice element n ∈ Nm. Daca P (m) este adevarata si daca pentru k ∈ Nm avemP (k) adevarata implica P (σ(k)) adevarata atunci P (n) este adevarata pentru oricen ∈ Nm.

2 Operatii binare pe N

2.1 Operatia de adunare a numerelor naturale

Teorema 3 Consideram (N, 0, σ) un sistem Peano. Exista o unica lege de compozitieϕ : N × N −→ N (pentru care vom folosi notatia ϕ(m,n) =: m + n) care satisfaceurmatoarele axiome:

A1: ϕ(m, 0) = m (m+ 0 = m), ∀m ∈ N;

5

A2: ϕ(m,σ(n)) = σ(ϕ(m,n)) (m+ σ(n) = σ(m+ n)), ∀m,n ∈ N.

Demonstratie. Existenta: Pentru m ∈ N fixat, consideram tripleta (N,m, σ).Conform Teoremei Recursiei, exista o unica functie ϕm : N −→ N astfel ıncatϕm(0) = m si urmatoarea diagrama este comutativa:

N σ−→ Nϕm ↓ ↓ ϕmN σ−→ N

(2)

Comutativitatea diagramei (2) este echivalenta cu ϕm(σ(n)) = σ(ϕm(n)). Functiaϕm este translatia cu m unitati, sau compunerea succesiva a lui σ de m ori.

Definim ϕ(m,n) = ϕm(n) =: m+n. Axiomele A1 si A2 sunt satisfacute datoritaproprietatilor lui ϕm.Unicitatea: Presupunem ca, pe langa aplicatia ϕ definita anterior, mai avem oaplicatie ϕ : N×N −→ N pentru care axiomele A1 si A2 sunt satisfacute: ϕ(m, 0) =m si ϕ(m,σ(n)) = σ(ϕ(m,n)). Pentru m ∈ N fixat, definim ϕm : N −→ N,ϕm(n) = ϕ(m,n). Avem ca ϕm(0) = m si ϕm ◦ σ = σ ◦ ϕm. Din unicitatea lui ϕmse obtine ϕm = ϕm, ∀m ∈ N si deci ϕ(m,n) = ϕ(m,n).Observatie. Folosind notatiile si proprietatile anterioare, avem n+ 1 = n+σ(0) =σ(n + 0) = σ(n). Pentru n = 1 obtinem o demonstratie a propozitiei matematice1 + 1 = σ(1) = 2.

Exercitiul 3 Demonstrati urmatoarele proprietati ale adunarii:

A3: 0 + n = n, ∀n ∈ N;

A4: σ(m) + n = σ(m+ n) = m+ σ(n), ∀m,n ∈ N;

A5: asociativitate: (m+ n) + p = m+ (n+ p), ∀m,n, p ∈ N;

A6: comutativitate: m+ n = n+m, ∀m,n ∈ N;

A7: reducere: n+ p = m+ p =⇒ n = m, p+ n = p+m =⇒ n = m.

A8: n+m = 0 =⇒ n = 0 si m = 0;

A8: n+m = 1 =⇒ (n = 0 si m = 1) sau (n = 1 si m = 0).

Pentru A7: prin reducere la absurd presupunem ca n 6= 0 sau m 6= 0. Daca n 6= 0atunci exista u ∈ N astfel ıncat n = σ(u). Avem 0 = m+ n = σ(u) + n = σ(u+ n)ceea ce contrazice P1.

6

Exercitiul 4 Pentru un sistem Peano (N, 0, σ) si m ∈ N∗ consideram operatia deadunare ϕm(n) = m+ n definita conform Teoremei 3. Notam

mN = {n ∈ N,∃k ∈ N, n = (ϕm ◦ · · · ◦ ϕm︸ ︷︷ ︸k ori

)(0)} = {0,m,m+m,m+ (m+m), ...}.

Sa se demonstreze ca daca m 6= 0 atunci (mN, 0, ϕm) este un sistem Peano.

Observatie. Conform proprietatilor A5, A1, A3, A6 obtinem ca (N,+) este unmonoid comutativ, al carui element neutru este 0.

2.2 Operatia de ınmultire a numerelor naturale

Teorema 4 Consideram (N, 0, σ) un sistem Peano. Exista o unica lege de compozitieψ : N×N −→ N, pentru care vom folosi notatia ψ(m,n) =: m ·n si pe care o numimınmultirea numerelor naturale, care satisface urmatoarele axiome:

M1: ψ(m, 0) = 0 sau (m · 0 = 0), ∀m ∈ N;

M2: ψ(m,σ(n)) = ψ(m,n) +m sau (m · σ(n) = m · n+m), ∀m,n ∈ N.

Demonstratie. Demonstratia este asemanatoare cu cea a Teoremei 3. Fie sistemulPeano (N, 0, σ) si pentru m ∈ N fixat consideram tripleta (mN, 0, ϕm). ConformTeoremei Recursiei, exista o functie unica ψm : N −→ mN pentru care ψm(0) = 0 siurmatoarea diagrama este comutativa:

N σ−→ Nψm ↓ ↓ ψmmN ϕm−→ mN

(3)

Operatia de ınmultire se defineste astfel: ψ : N×N −→ N, m·n := ψ(m,n) = ψm(n).Proprietatea M2 este echivalenta cu comutativitatea diagramei (3).

Exercitiul 5 Demonstrati urmatoarele proprietati ale ınmultirii:

M3: 0 · n = 0, ∀n ∈ N;

M4: σ(m) · n = m · n+ n, ∀m,n ∈ N;

M5: asociativitate: (m · n) · p = m · (n · p), ∀m,n, p ∈ N;

M6: element neutru: m · 1 = 1 ·m = m, ∀m ∈ N;

7

M7: comutativitate: m · n = n ·m, ∀m,n ∈ N;

M8: simplificare: n · p = m · p (p 6= 0) =⇒ n = m, p · n = p ·m (p 6= 0) =⇒ n = m;

M9: distributivitate: n ·(m+p) = n ·m+n ·p, (m+n) ·p = m ·p+n ·p, ∀m,n, p ∈ N.

Propozitia 3 Urmatoarele proprietati sunt adevarate.

M10: Daca n ·m = 0 atunci n = 0 sau m = 0.

M11: Daca n ·m = 1 atunci n = 1 si m = 1.

Demonstratie. M10: Prin reducere la absurd presupunem n 6= 0 si m 6= 0. Existadeci u, v ∈ N astfel ıncat m = σ(u), n = σ(v). Atunci 0 = m · n = σ(u) · σ(v) =u · σ(v) + σ(v) = u · v + u+ σ(v) = σ(uv + u+ v), ceea ce contrazice P1.

M11: Deoarece mn = 1 6= 0 obtinem n 6= 0 si m 6= 0. Exista deci u, v ∈ Nastfel ıncat m = σ(u), n = σ(v). Atunci 1 = σ(0) = mn = σ(uv + u + v). Folosindinjectivitatea functiei σ avem uv + u + v = 0. Folosind Propozitia ?? rezulta cau = v = 0 si deci m = n = 1.

3 Relatia de ordine pe NDefinitia 1 Pentru doua numere naturale m,n ∈ N spunem ca:

1: m precede n, sau ca m este mai mic decat n, si scriem m < n, daca ∃u ∈ N,u 6= 0 astfel ıncat m+u = n; mai scriu n > m si citesc n este mai mare decatm;

2: m precede sau este egal cu n, sau ca m este mai mic sau egal decat n, si scriemm ≤ n, daca ∃u ∈ N astfel ıncat m+ u = n; mai scriu n ≥ m si citesc n estemai mare sau egal decat m.

Urmatoarele proprietati se obtin imediat din definitia precedenta:1) ∀n ∈ N avem: n ≥ 0 si σ(n) > n; ın plus n ∈ N∗ daca si numai daca n > 0.2) m < n daca si numai daca σ(m) ≤ n.

Exercitiul 6 Demonstrati urmatoarele proprietati ale relatiei de ordine pe multimeanumerelor naturale.

O1: relatia ”<” este tranzitiva;

8

O2: relatia ”≤” este o relatie de ordine pe N: este reflexiva, antisimetrica si tranz-itiva.

O3: compatibilitatea cu adunarea: m < n daca si numai daca pentru ∀p ∈ N avemm+ p < n+ p;

O4: compatibilitatea cu ınmultirea: m < n daca si numai daca pentru ∀p ∈ N,p 6= 0 avem m · p < n · p;

O5: (Proprietatea lui Arhimede) ∀n ∈ N∗, ∀m ∈ N ∃t ∈ N astfel ıncat m < n · t.

Principiul II al inductiei matematice. (PII) Fie P (n) o propozitie ce poatefi asociata cu orice numar natural. Daca P (0) este adevarata si pentru un numarnatural arbitrar m avem P (r) adevarata pentru orice r < m implica P (m) adevarata,atunci P (n) este adevarata pentru orice numar natural n.

Teorema 5 (Principiul trihotomiei, PT) Pentru doua numere naturale m si n unasi numai una din urmatoarele relatii are loc: m < n, m = n sau m > n.

Demonstratie. Se demonstreaza mai ıntai, prin reducere la absurd, ca nu pot avealoc simultan doua dintre aceste relatii. Demonstram apoi ca are loc cel putin unadintre aceste relatii. Fixam m ∈ N si demonstram, prin inductie dupa n, ca ∀n ∈ Nare loc una din urmatoarele relatii: m < n, m = n sau m > n.Observatie. Folosind principiul trihotomiei se obtine ca pentru orice doua numerenaturale m si n una din urmatoarele relatii are loc: m ≤ n sau n ≤ m. Aceastaınseamna ca relatia ”≤” este o relatie de ordine totala pe N, cu alte cuvinte (N,≤)este total ordonata.

Teorema 6 (Principiul bunei ordonari, PBO) (N,≤) este o multime bine ordonata.Aceasta ınseamna ca orice submultime nevida a multimii numerelor naturale admiteun prim element: ∀A ⊂ N, A 6= ∅, ∃a ∈ A astfel ıncat a ≤ x, ∀x ∈ A.

Demonstratie. Vom nota cu M = {n ∈ N, n ≤ x, ∀x ∈ A}, multimea minorantilormultimii A. Avem ca 0 ∈M . Daca pentru orice numar natural n din M am obtineca σ(n) ∈ M atunci conform axiomei inductiei am avea ca M = N. Nu este ınsaposibil sa avem M = N deoarece pentru un element fixat x ∈ A avem ca x < σ(x)si deci σ(x) /∈M .

Exista deci a ∈ M astfel ıncat σ(a) /∈ M . In continuare trebuie demonstrat caa ∈ A, ceea ce va ınsemna ca a cel mai mic element al multimii A. Demonstratiase face prin reducere la absurd. Presupunem ca a /∈ A ceea ce ınseamna ca a < x,

9

∀x ∈ A de unde se obtine σ(a) ≤ x, ∀x ∈ A. Aceasta ınseamna ca σ(a) ∈ M ceeace contrazice alegerea lui a.

Obervam ca ın demostratie s-a folosit pricipiul I al inductiei matemtice. Cu altecuvinte am demostrat ca PI =⇒ PBO. Vom demonstra imediat ca aceste douaprincipii sunt de fapt echivalente.

Lema 1 Orice sir descrescator de numere naturale contine un numar finit de ter-meni distincti.

Demonstratie. Fie α : N −→ N un sir descrescator de numere naturale. NotamA = {α(n), n ∈ N}. Deoarece A 6= ∅ conform PBO exista un cel mai mic element a ∈A. Daca a = α(m) atunci α(m) ≤ α(n), ∀n ∈ N. Deoarece sirul este descrescatoratunci ∀n ≥ m avem α(n) ≤ α(m) = a. Se obtine ca pentru ∀n ≥ m avemα(n) = α(m) = a. Aceasta ınseamna ca sirul dat contine cel mult m + 1 termenidistincti, α(0), α(1), ..., α(m).

Teorema 7 Orice multime de numere naturale nevida si marginita admite un ultimelement.

Demonstratie. Fie M ⊂ N o multime nevida si marginita. Aceasta ınseamna ca:∃ b ∈ N astfel ıncat x ≤ b, ∀x ∈ M . Consideram multimea M ′ = {y ∈ N, x ≤y, ∀x ∈ M}. Deoarece multimea M ′ este nevida (b ∈ M ′), conform PBO obtinemca M ′ are un prim element a. Este imediat ca a ∈ M si x ≤ a, ∀x ∈ M , ceea ceınseamna ca a este ultim element pentru M .

Teorema 8 (Echivalenta principiilor inductiei matematice cu principiul bunei or-donari) Principiile I si II ale inductiei matematice sunt echivalente cu principiulbunei ordonari.

Demonstratie. Se demonstreaza PI =⇒ PBO =⇒ PII =⇒ PI. ImplicatiaPI =⇒ PBO a fost facuta ın cadrul demonstratiei PBO.

Vom demonstra implicatia PBO =⇒ PII. Consideram P (n) o propozitiematematica ce poate fi asociata unui numar natural oarecare n astfel ıncat:

1) P (0) este adevarata;

2) daca P (r) este adevarata pentru orice r < m atunci P (m) este adevarata.

Trebuie sa demonstram ca P (n) este adevarata ∀n ∈ N. Pentru aceasta vom notaA = {n ∈ N, P (n) nu este adevarata} si demonstram ca A = ∅. Prin reducere laabsurd presupunem ca A 6= ∅. Conform PBO exista un cel mai mic element a ∈ A,

10

ceea ce ınseamna ca a ∈ A, a ≤ x, ∀x ∈ A. Pentru ∀l < a avem l /∈ A si deci P (l)este adevarata. Conform ipotezei obtinem P (a) adevarata si deci a /∈ A ceea ce estefals.

Pentru a ıncheia demonstratia teoremei ramane sa demonstram PII =⇒ PI(exercitiu).

4 Sisteme de numeratie

Teorema 9 (Teorema ımpartirii cu rest - TIR) Pentru orice doua numere naturalea si b, b 6= 0, exista si sunt unice numerele naturale q si r astfel ıncat a = bq + r,cu r < b.

Demonstratie. Existenta: Pentru b ∈ N, b 6= 0, fixat, demonstram prin inductiematematica dupa a ∈ N.

Daca a = 0, atunci q = 0, r = 0 < b, a = 0 = b · 0 + 0. Presupunem ca ∃q, r ∈ N,r < b astfel ıncat a = b · q + r. Atunci σ(a) = b · q + σ(r). Daca σ(r) < b atuncir′ = σ(r) si q′ = q. Daca σ(r) = b atunci σ(a) = b · q + b = b · σ(q). Consideramq′ = σ(q) si r′ = 0 < b.Unicitatea: Presupunem ca avem a = b · q + r si a = b · q′ + r′. Daca presupunemq < q′ atunci ∃u 6= 0 astfel ıncat q′ = q+u, de unde obtinem b ·(q+u)+r′ = b ·q+r.Reducand termenii asemenea r = b · u + r′ ≥ b ceea ce este fals. Asemanator seobtine ca nu putem avea q′ < q si deci q = q′ ceea ce antreneaza imediat r = r′.

Exercitiul 7 Fie numerele naturale a si b, b 6= 0. Notam Ma,b = {y ∈ N,∃x ∈N a.i. y + bx = a}. Sa se demonstreze ca Ma,b 6= ∅ si ca r = minMa,b este restulımpartirii lui a la b.

Teorema 10 (Algoritmul de scriere a unui numar natural ıntr-o baza) Fie u ∈ N,u > 1. Pentru orice numar natural nenul a, exista si sunt unice: numarul natural n,n numere naturale nenule q0, q1, ..., qn−1, si n+ 1 numere naturale a0, a1, ..., an−1, ancu ai < u,∀i ∈ {0, 1, ..., n}, an 6= 0 astfel ıncat

a = u · q0 + a0, a0 < u;q0 = u · q1 + a1, a1 < u;· · · ;qn−2 = u · qn−1 + an−1, an−1 < u;qn−1 = an, 1 ≤ an < u.

Demonstratie. Algoritmul consta ın ımpartiri succesive ale numarului dat sicaturilor obtinute la u pana obtinem un cat mai mic decat u.

11

Daca a < u, atunci n = 0 si a0 = a. Daca a ≥ u, conform teoremei ımpartirii curest a = uq0 + a0, a0 < u, q0 ≥ 1. In plus avem a = uq0 + a0 ≥ uq0 > q0. Aplicamprocedeul lui q0 si obtinem: q0 = uq1 + a1, a1 < u, q1 ≥ 1, a > q0 > q1. Vom notaA = {a, q0, q1, ... | qi 6= 0}. Deoarece A 6= ∅, conform PBO, ∃qn−1 prim element almultimii A. Cum qn < qn−1 obtinem ın mod necesar qn = 0 si qn−1 = u·qn+an = an,cu an < u. Deoarece qn−1 6= 0 obtinem qn−1 ≥ 1 si deci 1 ≤ an < u.

Teorema 11 (Scrierea unui numar natural ıntr-o baza) Fie u ∈ N, u > 1 si a ∈ N∗.Atunci exista si sunt unice numerele naturale: n, a0, a1, ..., an; ai < u,∀i = 0, n,an ≥ 1, astfel ıncat a = an ·un+an−1 ·un−1 + · · ·+a1 ·u+a0. Numarul u se numestebaza sistemului de numeratie, numerele a0, a1, ..., an se numesc cifrele numarului aın baza u, pentru care folosim scrierea a = anan−1 · · · a1a0(u).

Demonstratie. Existenta scrierii: Conform Teoremei 10 avem:

a = u · q0 + a0, a0 < u;u | q0 = u · q1 + a1, a1 < u;

· · · ;un−1 | qn−2 = u · qn−1 + an−1, an−1 < u;un | qn−1 = an, 1 ≤ an < u.

Adunand termen cu termen si efectuand reducerile obtinem a = anun + an−1u

n−1 +· · ·+ a1u+ a0.Unicitatea scrierii: Vom demonstra, mai ıntai, prin inductie ca P (n) : anu

n +an−1u

n−1 + · · ·+ a1u+ a0 < un+1 este adevarata ∀n ∈ N, cu ai < u,∀i = 0, n.Pentru n = 0, P (0) : a0 < u este adevarata. Presupunem P (n) adevarata.

Atunci

P (n+1) :n+1∑i=0

aiui = an+1u

n+1+n∑i=0

aiui < an+1u

n+1+un+1 = (an+1+1)un+1 ≤ un+2.

Pentru ultima egalitate am folosit ca an+1 < u implica an+1 + 1 ≤ u. Conform PI alinductiei matematice se obtine ca P (n) este adevarata pentru ∀n ∈ N.

Presupunem ca pentru numarul a mai avem o scriere a =∑m

j=0 cjuj, cj < u, 1 ≤

cm < u. Demonstram mai ıntai ca n = m. Prin reducere la absurd sa presupunemca n < m. Aceasta implica n + 1 ≤ m si conform rezultatului demonstrat anterioravem:

a =n∑i=0

aiui < un+1 ≤ um ≤

m∑j=0

cjuj = a

ceea ce este fals. In mod asemanator se arata ca nu putem avea m < n. Conformprincipiului trihotomiei obtinem n = m.

12

Demonstram acum, prin inductie, ca propozitia:

P (n) :n∑i=0

aiui =

n∑i=0

ciui =⇒ ai = bi, ∀i = 1, n

este adevarata pentru orice n ∈ N. Pentru n = 0 se obtine a0 = b0 si deci P (0) esteadevarata.

Presupunem ca P (n) este adevarata pentru un numar natural n. Folosind faptulca a0 < u, c0 < u si unicitatea scrierii pentru Teorema ımpartirii cu rest, dinegalitatea a0 + u(a1 + a2u+ · · · an+1u

n) = c0 + u(c1 + c2u+ · · ·+ cn+1un) se obtine:

a0 = c0 si a1 +a2u+ · · · an+1un = c1 +c2u+ · · ·+cn+1u

n. Folosind ipoteza inductiva,din ultima egalitate se obtine: a1 = c1, ..., an+1 = cn+1 si deci P (n + 1) esteadevarata. Folosind principiul ıntai al inductiei matematice se obtine ca P (n) esteadevarata ∀n ∈ N.

Teorema 12 (Relatia de ordine pentru doua numere scrise ıntr-o baza) Fie a =anan−1 · · · a1a0(u) si b = bmbm−1 · · · b1b0(u). Atunci a < b daca si numai daca:

• sau n < m (b are mai multe cifre decat a)

• sau n = m si ∃k ∈ {0, 1, 2, ..., n} astfel ıncat an = bn, ..., ak+1 = bk+1, ak < bk.

Demonstratie. Vom demonstra doar implicatie reciproca. Daca n < m atuncin + 1 ≤ m si deci un+1 ≤ um. Acestea implica a =

∑ni=0 aiu

i < un+1 ≤ um <∑mj=0 bju

j = b, ceea ce ınseamna ca a < b.Sa presupunem ca n = m si ∃k ∈ {0, 1, ..., n} astfel ıncat aj = bj pentru ∀j ∈

{n, ..., k + 1} si ak < bk. Se obtine atunci ak + 1 ≤ bk si deci

a0+a1u+· · ·+ak−1uk−1+akuk < (1+ak)u

k ≤ bkuk ≤ b0+b1u+· · ·+bk−1uk−1+bku

k.

Adunand ambilor membri ai inegalitatii precedente ak+1uk+1+· · ·+anun = bk+1u

k+1+· · · bnun se obtine a < b.

Justificati implicatia directa.

5 Relatia de divizibilitate pe NDefinitia 2 Date doua numere naturale a si b, spunem ca a divide b daca existanumarul natural c astfel ıncat b = a · c.

Daca a divide b vom nota a | b sau b... a, mai citesc a este divizor al lui b, b se

divide la a sau ca b este multiplu de a. Daca a 6= 0 si a | b avem ca restul ımpartiriilui b la a este zero.

Proprietati imediate ale relatiei de divizibilitate:

13

D1: 0 | b ⇐⇒ b = 0; a | 0, ∀a ∈ N;

D2: 1 | b si b | b, ∀b ∈ N∗; b | 1 ⇐⇒ b = 1; ∀b ∈ N∗, b 6= 1 admite cel putin doidivizori;

D3: relatia de divizibilitate este o relatie de ordine (partiala) pe N:

– reflexiva: a | a, ∀a ∈ N;

– antisimetrica: a | b si b | a =⇒ a = b;

– tranzitiva: a | b si b | c =⇒ a | c;– nu este totala: ∃a, b ∈ N astfel ıncat a 6 | b si b 6 | a.

D4: a | b =⇒ a ≤ b, relatia de divizibilitate este compatibila cu relatia de ordine;

D5: a | b si a | c =⇒ a | b · x + c · y, ∀x, y ∈ N, relatia de divizibilitate estecompatibila cu operatiile de adunare si ınmultire;

D6: a | b+ c si a | b =⇒ a | c.

Demonstratie. Vom demonstra doar ultima proprietate pentru cazul a 6= 0.Deoarece:

• a | b+ c =⇒ ∃u ∈ N astfel ıncat b+ c = au

• a | b =⇒ ∃v ∈ N astfel ıncat c = av.

In mod evident avem b + c ≥ b deci au ≥ av, a 6= 0, de unde obtinem u ≥ v. Inconsecinta ∃w ∈ N astfel ıncat u = v+w. Avem b+ c = au = a(v+w) = av+aw =av + c. Din ultima egalitate, dupa reducere, se obtine c = aw cee ce ınseamna caa | c.

Definitia 3 1) Un numar natural p se numeste indecompozabil (sau ireductibil)daca p 6= 0, p 6= 1 si singurii sai divizori sunt 1 si p;

2) Un numar natural se numeste compus (decompozabil sau reductibil) daca ad-mite mai mult de doi divizori;

3) Un numar natural p, p 6= 0 si p 6= 1, se numeste prim daca p | a · b implicap | a sau p | b.

Propozitia 4 Fie a > 1 un numar natural.

1) Daca a este decompozabil atunci exista b, c ∈ N cu 1 < b, c < a astfel ıncata = b · c.

14

2) Numarul natural a admite un divizor indecompozabil.

Demonstratie. 1) Fie a > 1 un numar natural compus. Aceasta ınseamna, conformdefinitiei, ca exista b /∈ {1, a} astfel ıncat b | a, de unde rezulta 1 < b < a. Existadeci c ∈ N astfel ıncat a = bc. Se obtine imediat ca c /∈ {1, a} si deci 1 < c < a.

2) Pentru numarul natural a > 1 notam M = {q ∈ N, q > 1, q | a}, multimeadivizorilor lui a. Deoarece a ∈ M avem ca M 6= ∅ si conform PBO, multimea Mare un cel mai mic element b. Aratam ca b este indecompozabil. Prin reducere laabsurd presupunem ca b ar fi decompozabil. Conform primei parti exista numarulnatural c, 1 < c < b astfel ıncat c | b. Deoarece b | a se obtine ca c | a si cum c < bse contrazice minimalitatea lui b.

Teorema 13 Fie p un numar natural, p > 1. Urmatoarele afirmatii sunt echiva-lente:

1) p este numar prim;

2) p este numar indecompozabil.

Demonstratie. 1) =⇒ 2) Fie p un numar prim despre care presupunem prinreducere la absurd ca este decompozabil. Exista deci numerele naturale a si b cu1 < a, b < p astfel ıncat p = a · b. Aceasta ınseamna ca p | a · b si cum p este primobtinem p | a sau p | b. Dar p = a · b si deci a | p si b | p, de unde obtinem p = a saup = b, ceea ce contrazice faptul ca a < p si b < p.

2) =⇒ 1) Fie p un numar indecompozabil despre care presupunem prin reducerela absurd ca nu este prim. Folosind PBO, pot presupune ca p este cel mai mic numarcu aceasta proprietate. Deoarece p nu este numar prim obtinem ca ∃a, b ∈ N astfelıncat p | ab, p 6 | a si p 6 | b iar produsul a · b este minim cu aceasta proprietate. Vomdemonstra acum ca a < p si b < p. Daca prin reducere la absurd presupunem caa > p, conform TIR, a = pq + r, q ≥ 1, 0 < r < p. Obtinem ab = pqb+ rb de underezulta p | rb, p 6 | b, p 6 | r si rb < ab ceea ce contrazice alegerea perechii (r, b). Inconsecinta 1 < a < p si 1 < b < p.

Deoarece p | ab exista q > 1 (q 6= 1 deoarece p indecompozabil) astfel ıncatpq = ab. Deoarece 1 < a < p si 1 < b < p obtinem pq = ab < pp de unde se obtineq < p. Fie c un divizor indecompozabil al lui q, c ≤ q < p. Avem c | q | ab decic | ab, este indecompozabil si cum este mai mic decat p, din alegerea lui p (cel maimic neprim cu proprietatlie pe care le are si q) se obtine c numar prim. Deoarecec | ab rezulta c | a sau c | b.

Presupunem c | a=⇒ a = ca1. Cum ab = pq obtinem ca1b = pcq1 de unde rezultaa1b = pq1, si deci p | a1b ceea ce contrazice alegerea perechii (a, b) cu produsul abminim (a1b < ab).

15

In continuare vom folosi doar notiunea de numar prim pentru a desemna atatnumerele prime cat si pe cele indecompozabile.

Teorema 14 (Teorema lui Euclid) Exista o infinitate de numere prime.

Demonstratie. Demonstratia 1 (Euclid) Prin reducere la absurd presupunem caexista o multime finita de numere prime P = {p1, p2, ..., pk}. Consideram numarulN = p1 · p2 · · · pk + 1. Cum N > 1 exista un numar prim p astfel ıncat p | N .Cum p prim rezulta ca exista i ∈ {1, 2, ..., k} astfel ıncat p = pi. Deoarece p | N sip | p1 · p2 · · · pk obtinem ca p | 1 ceea ce este fals.Demonstratia 2 Observam ca ∀n ∈ N ∃p prim cu p > n (numarul n! + 1 are undivizor prim p si ın mod necesar p > n). Se obtine atunci ca pentru orice numarprim p exista p′ prim cu p′ > p.Ciurul lui Eratostene: O modalitate simpla de a obtine numere prime consta ına scrie numere naturale succesive si a elimina multiplii numerelor care nu au fosteliminate anterior: 2, 3, 64, 5, 66, 7, 68, 69, 610, 11, 612, 13, 614, 615, 616, 17, 618, 19, 620, ...

Teorema 15 (Teorema Fundamentala a Aritmeticii) Orice numar natural n > 1admite o scriere unica, pana la ordinea factorilor, ca produs finit de numere prime.

Demonstratie. Existenta scrierii: NotamM = {n ∈ N, n > 1, n nu se poate scrieca un produs finit de numere indecompozabile}. Daca prin reducere la absurd pre-supunem ca M 6= ∅, conform PBO, exista a un prim element al multimii M .Deoarece a nu este prim atunci se poate scrie a = b · c, 1 < b, c < a. Rezultab, c /∈ M si deci b si c se pot scrie ca un produs finit de factori primi. Aceastaınseamna ca a are aceeasi proprietate, ceea ce contrazice a ∈M .Unicitatea scrierii: Presupunem a = p1 · p2 · · · pn = q1 · q2 · · · qm. Demonstramprin inductie dupa n ca n = m si dupa o eventuala permutare a factorilor pi = qi.

Pentru n = 1 avem p1 = q1 · q2 · · · qm. Rezulta p1 | q1 · q2 · · · qm si deci ∃j ∈{1, 2, ...,m} astfel ıncat p1 | qj. Deoarece qj este indecompozabil rezulta p1 = qj sim = n = 1.

Presupunem proprietatea adevarata pentru n − 1 si consideram p1 · p2 · · · pn =q1 ·q2 · · · qm. Din pn | q1 ·q2 · · · qm se obtine pn | qm (printr-o eventuala renumerotare).Deoarece qm este indecompozabil obtinem pn = qm si deci p1 · p2 · · · pn−1 = q1 ·q2 · · · qm−1. Folosind ipoteza inductiva avem n − 1 = m − 1 si dupa o eventualarenumerotare pi = qi, ∀i ∈ {1, 2, ..., n− 1}.Observatie.

1) Factorii din descompunerea precedenta pot sa coincida. Vom scrie

a = pα11 · pα2

2 · · · pαkk , p1 < p2 < · · · pk (descompunerea canonica).

16

2) Fie b = pα11 · pα2

2 · · · pαkk . Atunci a | b daca si numai daca a = pβ11 · p

β22 · · · p

βkk ,

cu 0 ≤ βi ≤ αi, ∀i ∈ {1, ..., k}.

Criterii de divizibilitate (pentru numere scrise ın baza zece) Fie numarul a =an · · · a1a0(10) = an10n + · · ·+ a110 + a0. Atunci numarul a se divide la:

CD1) 2, 5 sau 10 daca si numai daca ultima cifra, a0, are aceasta proprietate;

CD2) 2m, 5m sau 10m daca si numai daca numarul format cu ultimele m cifre,am−1 · · · a1a0, are aceasta proprietate, m ≥ 1;

CD3) 3 sau 9 daca si numai daca suma cifrelor,∑n

i=0 ai, are aceasta proprietate.Deoarece

a = an(9 + 1)n + · · ·+ a1(9 + 1) + a0 = 9 ·m+n∑i=0

ai

atunci 3(9) | a ⇐⇒ 3(9) |∑n

i=0 ai.

CD4) 11 daca si numai daca 11 |∑n

i=0(−1)iai. Deoarece

a = an(11− 1)n + · · ·+ a1(11− 1) + a0 = 11 ·m+n∑i=0

(−1)iai

atunci 11 | a ⇐⇒ 11 |∑n

i=0(−1)iai.

Observatie Ideile folosite ın demonstratia criteriilor de divizibilitate precedentepermit de asemeni sa obtinem mai usor restul ımpartirii numarului a = an · · · a1a0(10)la diverse numere. Astfel, restul ımpartirii numarului a la

R1) 2 sau 5 este egal cu restul ımpartirii ultimei cifre a0 la 2 sau 5;

R2) 2m sau 5m este egal cu restul ımpartirii numarului format cu ultimele m cifream · · · a1a0(10) la 2m sau 5m;

R3) 3 sau 9 este egal cu restul ımpartirii sumei cifrelor∑n

i=0 ai la 3 sau 9;

R4) 11 este egal cu restul ımpartirii sumei alternate a cifrelor∑n

i=0(−1)iai la 11.

17

6 Cel mai mare divizor comun

Definitia 4 Spunem ca numarul natural d este cel mai mare divizor comun al nu-merelor a si b (scriu d = c.m.m.d.c{a, b} sau d = (a, b)) daca:

1: d | a si d | b;

2: pentru d′ ∈ N avem d′ | a si d′ | b atunci d′ | d.

Teorema 16 (Teorema de existenta si unicitate a celui mai mare divizor comun).Pentru orice doua numere naturale a si b exista si este unic cel mai mare divizorcomun al lor.

Demonstratie. Existenta: (Algoritmul lui Euclid) Daca a = 0 sau b = 0 atuncid = b sau d = a. Presupunem a 6= 0 si b 6= 0. Aplicam TIR, exista q0, r0

a = bq0 + r0, 0 ≤ r0 < b.

Daca r0 = 0 atunci a = bq0 si d = (a, b) = b. Daca r0 6= 0 aplic din nou TIR pentrub si r0. Continuam procedeul pana obtinem un rest nul.

b = r0q1 + r1, 0 < r1 < r0;· · · ;rn−2 = rn−1qn + rn, 0 < rn < rn−1;rn−1 = rnqn+1.

(4)

Algoritmul prezentat are un numar finit de pasi deoarece sirul de numere naturaleb > r0 > · · · > rn este strict descrescator. Vom demonstra ca rn = (a, b). Deoarecern | rn−1 se obtine rn | ri, ∀i si rn | b, rn | a. Daca d′ | a si d′ | b se obtine d′ | r0, ...,d′ | rn. In consecinta rn = (a, b).Unicitatea: Fie d si d′ numere naturale care satisfac conditiile 1) si 2) din Definitia4. Obtinem ca d | d′ si apoi d′ | d de unde rezulta d = d′.Observatie

1) Fie numerele a si b si r0, r1, ..., rn obtinute conform algoritmului lui Euclid (4).Atunci (a, b) = (b, r0) = (r0, r1) = · · · = (rn−1, rn) = rn.

2) Fie a = pα11 · · · pαn

n si b = pβ11 · · · pβnn . Atunci cel mai mare divizor al numerelor

a si b este numarul d = (a, b) = pmin{α1,β1}1 · · · pmin{αn,βn}

n .

Definitia 5 Spunem ca doua numere a si b sunt prime ıntre ele daca (a, b) = 1.

18

Fie a = pα11 · · · pαn

n si b = pβ11 · · · pβnn . Conform observatiei precedente se obtine ca asi b sunt prime ıntre ele daca si numai daca min{αi, βi} = 0, ∀i ∈ {1, 2, ..., n}.Proprietati:

1) (a, a) = a (idempotenta); (a, b) = (b, a) (simetria);

2) (a, b) = d =⇒ (ac, bc) = dc, ∀a, b, c ∈ N;

3) (a, (b, c)) = ((a, b), c), (asociativitatea, permite sa definim c.m.m.d.c. pentrumai mult de doua numere, astfel putem defini (a, b, c) := (a, (b, c)) ∀a, b, c ∈ N);

4) (a, b) = 1 si (a, c) = 1 ⇐⇒ (a, bc) = 1;

5) a | c, b | c, (a, b) = 1 =⇒ ab | c;

6) (a, b) = d =⇒ a = a1d, b = b1d astfel ıncat (a1, b1) = 1;

7) a | b · c si (a, b) = 1 =⇒ a | c.

Demonstratie. 3) Notam d1 = (b, c), d2 = (a, (b, c)) = (a, d1), d3 = (a, b) sid4 = ((a, b), c) = (d3, c). Pentru a demonstra d2 = d4 vom arata d2 | d4 si d4 | d2.Deoarece d2 = (a, d1) rezulta d2 | a si d2 | d1. Cum d1 = (a, b) se obtine d1 | asi d1 | b ceea ce implica d2 | b si d2 | c. Din d2 | a, d2 | b si d3 = (a, b) obtinemd2 | d3. Folosind d2 | d3, d2 | c si d4 = (d3, c) se obtine d2 | d4. In mod asemanatorse demonstreaza d4 | d2.

4) Folosind proprietatile anterioare avem 1 = (a, b) = (a, b(a, c)) = (a, (ab, bc)) =((a, ab), bc) = (a, bc).

5) Vom arata ca ab | c, aratand ca (ab, c) = ab. Pentru aceasta avem (ab, c) =(ab, c(a, b)) = (ab, (ac, bc)) = ((ab, ac), bc) = (a(b, c), cb) = (ab, bc) = b(a, c) = ba.

Exercitiul 8 Pentru un numar natural nenul n vom nota cu τ(n) numarul divizo-rilor naturali ai lui n.

1) Daca p este un numar prim atunci τ(pk) = k + 1, k ≥ 1.

2) Daca b si c sunt numere prime ıntre ele atunci τ(b · c) = τ(b) · τ(c) (functia τeste multiplicativa).

3) Daca n = pα11 · · · p

αkk atunci τ(n) = (α1 + 1) · · · (αk + 1).

Exercitiul 9 Pentru doua numere a, b ∈ N∗, multimea D = {d ∈ N∗, d | a, d | b}este marginita (de min{a, b}) si este nevida (1 ∈ D). Exista si este unic un cel maimare (ultim) element d al multimii D. Sa se demonstreze ca d este cel mai maredivizor comun al numerelor a si b.

19

7 Cel mai mic multiplu comun

Definitia 6 Spunem ca numarul natural m este cel mai mic multiplu comun alnumerelor a si b (scriu m = c.m.m.m.c{a, b} sau m = [a, b]) daca:

1) a | m, b | m;

2) daca pentru m′ ∈ N avem a | m′ si b | m′ atunci m | m′.

Teorema 17 (Teorema de existenta si unicitate a celui mai mic multiplu comun)Pentru orice doua numere naturale a si b exista si este unic cel mai mic multiplucomun al lor.

Demonstratie. Existenta: Date numerele naturale a si b consideram d = (a, b).Aceasta ınseamna ca a = da1 si b = db1, cu (a1, b1) = 1. Consideram m = ab1 =a1b = a1b1d. Este evident ca m satisface prima conditie din Definitia 6. Pentrua doua conditie consideram m′ astfel ıncat a | m′ si b | m′. Aceasta ınseamna cam′ = a1dx = b1dy, deci a1x = b1y. Din a1 | b1y si (a1, b1) = 1 rezulta a1 | y si deciy = a1z. Se obtine m′ = b1da1z = mz ceea ce implica m | m′.

Demonstrati unicitatea.Observatie Fie a = pα1

1 · · · pαnn si b = pβ11 · · · pβnn . Atunci cel mai mic multiplu comun

al numerelor a si b este numarul m = [a, b] = pmax{α1,β1}1 · · · pmax{αn,βn}

n .

Exercitiul 10 Pentru doua numere a, b ∈ N∗, multimea M = {m ∈ N∗, a | m, b |m} este nevida (ab ∈M). Exista si este unic un cel mai mic element m al multimiiM . Sa se demonstreze ca m este cel mai mic multiplu comun al numerelor a si b.

Proprietati:

1) [a, a] = a (idempotenta); [a, b] = [b, a] (simetria);

2) [a, b] = m =⇒ [ac, bc] = mc, ∀a, b, c ∈ N;

3) [a, [b, c]] = [[a, b], c], (asociativitatea, permite sa definim c.m.m.m.c. pentrumai mult de doua numere, astfel putem defini [a, b, c] := [a, [b, c]] ∀a, b, c ∈ N);

4) (a, [a, b]) = a si [a, (a, b)] = a, ∀a, b ∈ N (absorbtie);

5) (a, b) · [a, b] = a · b, ∀a, b ∈ N;

6) (a, [b, c]) = [(a, b), (a, c)] si [a, (b, c)] = ([a, b], [a, c]), ∀a, b, c ∈ N (distributivi-tate);

7) a | c si b | c =⇒ [a, b] | c.

20

8 Multimea numerelor ıntregi

Fie N multimea numerelor naturale. Pe multimea N× N definim relatia ” ∼ ” prin(m,n) ∼ (p, q) daca m+q = n+p (ganditi m−n = p−q, chiar daca nu am introdus”-”).

Exercitiul 11 Sa se demonstreze ca ” ∼ ” este o relatie de echivalenta pe multimeaN× N.

Clasa de echivalenta corespunzatoare perechii (m,n) se noteaza (m,n) = {(p, q) ∈N×N, (m,n) ∼ (p, q)} si se numeste numar ıntreg. Multimea claselor de echivalentase numeste multimea numerelor ıntregi si se noteaza cu Z. Avem deci Z = N×N/ ∼.

8.1 Adunarea numerelor ıntregi

Pe multimea numerelor ıntregi se defineste operatia binara ”+” : Z×Z −→ Z astfel:pentru doua numere ıntregi (m,n) si (p, q) suma lor este data de: (m,n) + (p, q) :=(m+ p, n+ q) (ganditi (m− n) + (p− q) = (m+ p)− (n+ q)).

Trebuie demonstrat mai ıntai ca aceasta operatie nu depinde de reprezentantiicu ajutorul carora a fost definita. Fie (m′, n′) = (m,n) si (p′, q′) = (p, q) ceea ceınseamna ca m′ + n = n′ + m si p′ + q = q′ + p. Adunand membru cu membruaceste egalitati obtinem m + p + n′ + q′ = m′ + p′ + n + q si deci (m+ p, n+ q) =(m′ + p′, n′ + q′).

Exercitiul 12 Sa se demonstreze urmatoarele proprietati ale adunarii numerelorıntregi:

1) asociativitatea: x+ (y + z) = (x+ y) + z, ∀x, y, z ∈ Z;

2) comutativitatea: x+ y = y + x, ∀x, y ∈ Z;

3) element neutru: ∃ (0, 0) = {(n, n), n ∈ N} astfel ıncat (0, 0)+(m,n) = (m,n),∀(m,n) ∈ Z;

4) element simetrizabil: ∀ (m,n) ∈ Z, ∃ (n,m) ∈ Z astfel ıncat (m,n)+(n,m) =(0, 0). Vom folosi notatia −(m,n) := (n,m).

Conform acestor proprietati se obtine ca (Z,+) este un grup abelian.

21

8.2 Inmultirea numerelor ıntregi

Pe multimea numerelor ıntregi se defineste operatia binara ” ·” : Z×Z −→ Z astfel:pentru doua numere ıntregi (m,n) si (p, q) produsul lor este data de: (m,n)·(p, q) :=(mp+ nq,mq + np) (ganditi (m− n) · ((p− q) = (mp+ nq)− (np+mq)).

La fel ca ın cazul operatiei de adunare se demonstreaza ca operatia de ınmultireeste bine definita (nu depinde de reprezentanti).Proprietati ale operatiei de ınmultire:

1) asociativitatea: x · (y · z) = (x · y) · z, ∀x, y, z ∈ Z;

2) comutativitatea: x · y = y · x, ∀x, y ∈ Z;

3) element neutru: ∃ (1, 0) = {(n + 1, n), n ∈ N} astfel ıncat (1, 0) · (m,n) =(m,n), ∀(m,n) ∈ Z;

4) ınmultirea este distributiva la dreapta si la stanga fata de adunare: x·(y+z) =x · y + x · z si (x+ y) · z = x · z + y · z, ∀x, y, z ∈ Z;

5) fara divizori ai lui zero: (m,n) · (p, q) = (0, 0) =⇒ (m,n) = (0, 0) sau (p, q) =(0, 0).

Observatie Conform acestor proprietati se obtine ca (Z,+, ·) este un domeniu deintegritate.

Dintre proprietatile enuntate anterior o vom demonstra pe ultima: fie (m,n)si (p, q) ∈ Z astfel ıncat (m,n) · (p, q) = (0, 0). Conform Principiului Trihotomieiavem una si numai una din urmatoarele situatii: m = n, m < n sau n < m. Vomdemonstra ca oricare din ultimele doua posibilitati implica p = q. Sa presupunemm < n, exista atunci u ∈ N∗ astfel ıncat m + u = n, ceea ce ınseamna ca (m,n) =(0, u). Obtinem atunci (0, u) · (p, q) = (0, 0) ceea ce este echivalent cu (uq, up) =(0, 0). In consecinta up = uq si cum u 6= 0 obtinem p = q. Cazul n < m seanalizeaza asemanator.

8.3 Relatia de ordine pe ZDefinitia 7 Fie (m,n) si (p, q) doua numere ıntregi. Vom spune ca (m,n) estemai mic sau egal (mai mic strict) decat (p, q) si scriem (m,n) ≤ (<)(p, q) dacam+ q ≤ (<)n+ p.

Trebuie demontrat mai ıntai ca relatia ” ≤ ” (” < ”) nu depinde de reprezentanti.Proprietati ale relatiei de ordine:

22

1) (m,n) ≤ (0, 0) ⇐⇒ m ≤ n ⇐⇒ ∃u ∈ N astfel ıncat m + u = n ⇐⇒ (m,n) =(0, u) ≤ (0, 0);

2) (m,n) ≥ (0, 0) ⇐⇒ m ≥ n ⇐⇒ ∃v ∈ N astfel ıncat n + v = m ⇐⇒ (m,n) =(v, 0) ≥ (0, 0);

3) ” ≤ ” este o relatie de ordine totala (este reflexiva, antinsimetrica, tranzitivasi totala), fata de relatia de ordine pe N pierdem buna ordonare;

4) este compatibila cu operatia de adunare: ∀ x, y, z ∈ Z avem x ≤ y ⇐⇒ x+z ≤y + z; x ≤ y si x′ ≤ y′ =⇒ x+ x′ ≤ y + y′;

5) este compatibila cu operatia de ınmultire: ∀ x, y, z ∈ Z

– pentru z > (0, 0) avem x < y ⇐⇒ x · z < y · z;

– pentru z < (0, 0) avem x < y ⇐⇒ x · z > y · z.

Vom demonstra ultima proprietate. Fie x = (m,n), y = (p, q) si z = (r, s). Dacaz = (r, s) < (0, 0) atunci r < s, exista u ∈ N∗ astfel ıncat r + u = s si z = (0, u).Avem urmatorul sir de echivalente x < y ⇐⇒ m+q < n+p⇐⇒ mu+qu < nu+pu⇐⇒ (nu,mu) > (qu, pu) ⇐⇒ x · z > y · z.

Teorema 18 (Principiul trihotomiei pentru numere ıntregi) Pentru oricare douanumere ıntregi x si y una si numai una din urmatoarele relatii este adevarata: x < y,x = y sau y < x.

Teorema 19 (Teorema de scufundare a multimii numerelor naturale ın multimeanumerelor ıntregi) Functia ϕ : N −→ Z, definita prin ϕ(n) = (n, 0) are urmatoareleproprietati:

1) este injectiva;

2) este aditiva (compatibila cu operatiile corespunzatoare de adunare): ϕ(m+n) =ϕ(m) + ϕ(n), ∀m,n ∈ N;

3) este multiplicativa (compatibila cu operatiile corespunzatoare de ınmultire):ϕ(m · n) = ϕ(m) · ϕ(n), ∀m,n ∈ N;

4) este monotona (compatibila cu relatiile corespunzatoare de ordine): m ≤ n⇐⇒ϕ(m) ≤ ϕ(n).

23

Deoarece ϕ : N −→ ϕ(N) este o bijectie, ın continuare, vom identifica N cu ϕ(N)(spunem ca am scufundat multimea numerelor naturale ın multimea numerelorıntregi). Aceasta ınseamna ca vom identifica numarul natural n cu numarul ıntreg(n, 0) ≥ 0 = (0, 0). Deoarece simetricul la adunare (opusul) numarului ıntreg (m,n)este −(m,n) := (n,m), identificarea n = (n, 0) ne permite sa identificam de aseme-nea −n := −(n, 0) = (0, n) ≤ 0.

Pe baza acestor identificari vom putea descrie elementele multimii numerelorıntregi astfel: Z = {· · · ,−4,−3,−2,−1, 0, 1, 2, 3, 4, · · ·}.

Functia modul. Definim |·| : Z −→ N prin |n| ={n, daca n ≥ 0,−n, daca n ≤ 0.

Urmatoarele

proprietati ale functiei modul sunt imediate: |m · n| = |m| · |n|; |m+ n| ≤ |m|+ |n|,∀m,n ∈ Z.

Teorema 20 (Teorema ımpartirii cu rest ın Z) Pentru orice doua numere ıntregia si b, b 6= 0, exista si sunt unice numerele ıntregi q si r astfel ıncat a = bq + r si0 ≤ r < |b|.

Demonstratie. Existenta: Pentru numerele naturale |a| si |b| exista numerelenaturale q′ si r′ astfel ıncat |a| = |b|q′+r′, cu 0 ≤ r′ < |b|. Trebuiesc analizate patrucazuri, dupa cum numerele ıntregi a si b sunt pozitive sau nu.

Daca a, b > 0 atunci consideram q = q′ si r = r′.Daca a < 0 si b > 0 atunci −a = bq′ + r′. Avem a = b · (−q′) + (−r′). Daca

r′ = 0 atunci q = −q′ si r = r′ = 0. Daca r′ 6= 0 avem a = b(−q′ − 1) + b − r′.Consideram q = −q′ − 1 si r = b− r′. Deoarece 0 < r′ < b se obtine 0 < r < b.

Cazurile a < 0, b < 0 si a > 0, b < 0 se analizeaza ın mod asemanator.Unicitatea: Sa presupunem ca a = bq + r = bq′ + r′, cu 0 ≤ r, r′ < |b|. Obtinemca |r − r′| < |b|. Deoarece b(q − q′) = r′ − r, folosind proprietatile modululuiavem |b||q − q′| = |r − r′|. Daca prin reducere la absurd presupunem q 6= q′ atunci|q − q′| ≥ 1 si deci |r − r′| ≥ |b|, ceea ce contrazice principiul trihotomiei.

Exercitiul 13 Sa se demonstreze ca singurele subgrupuri ale lui (Z,+) sunt deforma nZ.

8.4 Aritmetica pe ZDefinitia 8 Pentru doua numere ıntregi a si b spunem ca a | b daca exista c ∈ Zastfel ıncat b = a · c (a se numeste divizor al lui b, b se numeste multiplu al lui a).

Proprietati ale relatiei de divizibilitate.

1) ∀a ∈ Z =⇒ ±1 | a si a | 0; 0 | b⇐⇒ b = 0; a | 1⇐⇒ a = ±1;

24

2) reflexiva: ∀a ∈ Z =⇒ a | a;

3) tranzitiva a | b si b | c =⇒ a | c;

4) a | b si b | a =⇒ a = ±b (spunem ca a si b sunt asociate ın divizibilitate);

5) d | a si d | b =⇒ d | ax+ by, ∀x, y ∈ Z.

Definitia 9 Un numar a ∈ Z \ {±1, 0} se numeste

1) indecompozabil (ireductibil) daca singurii divizori ai lui a sunt {±1,±a};

2) prim daca p | a · b implica p | a sau p | b.

La fel ca si ın cazul multimii numerelor naturale avem urmatoarea teorema.

Teorema 21 Un numar ıntreg p este indecompozabil daca si numai daca este prim.

Cel mai mare divizor comun a doua numere ıntregi

Definitia 10 Pentru doua numere ıntregi a si b spunem ca numarul ıntreg d estecel mai mare divizor comun al lor (scriu d = cmmdc{a, b} sau d = (a, b)) daca:

1) d | a si d | b;

2) d′ | a si d′ | b =⇒ d′ | d.

Observatie Daca d si d′ sunt cmmdc a doua numere ıntregi a si b atunci d si d′ suntasociate ın divizibilitate (se obtine unicitate daca cerem ca cmmdc sa fie un numarnatural).

Teorema 22 (Algoritmul lui Euclid de existenta a cmmdc) Pentru orice numereıntregi a si b exista cel mai mare divizor comun.

Demonstratie. Consideram a, b ∈ Z. Daca b = 0 atunci (a, 0) = a. Daca b 6= 0∃q0, q1, ..., qn, qn+1, r0, r1, ..., rn ∈ Z astfel ıncat:

a = bq0 + r0, 0 < r0 < |b|;b = r0q1 + r1, 0 < r1 < r0;r0 = r1q2 + r2, 0 < r2 < r1;· · · ;rn−2 = rn−1qn + rn, 0 < rn < rn−1;rn−1 = rnqn+1.

La fel ca si ın cazul numerelor naturale se obtine imediat ca d = rn = (a, b).Proprietati:

25

1) d = (a, b) daca si numai daca exista u, v ∈ Z astfel ıncat d = au+ bv si |d| estecel mai mic numar nenul cu aceasta proprietate;

2) (a, bi) = 1, ∀i = 1, n =⇒ (a, b1 · · · bn) = 1;

3) (a, b) = d =⇒ (ac, bc) = dc, ∀c ∈ Z;

4) a | bc si (a, c) = 1 =⇒ a | b;

5) ai | b,∀i = 1, n si (ai, aj) = 1,∀i 6= j =⇒ a1 · · · an | b;

6) (a, b) = d =⇒ a = da1, b = db1, (a1, b1) = 1;

7) a | b =⇒ |a| ≤ |b|.

Cel mai mic multiplu comun a doua numere ıntregi

Definitia 11 Pentru doua numere ıntregi a si b spunem ca numarul ıntreg m estecel mai mic multiplu comun al lor (scriu m = cmmmc{a, b} sau m = [a, b]) daca:

1) a | m si b | m;

2) a | m′ si b | m′ =⇒ m | m′.

Observatie Daca m si m′ sunt cmmmc a doua numere ıntregi a si b atunci m si m′

sunt asociate ın divizibilitate (se obtine unicitate daca cerem ca cmmmc sa fie unnumar natural).

Teorema 23 (De existenta a cmmmc a doua numere ıntregi) Date doua numereıntregi a si b exista cel mai mic multiplu comun al lor si este unic pana la asociereain divizibilitate.

9 Congruente

Definitia 12 Fie n un numar natural. Pentru a, b numere ıntregi spunem ca a estecongruent cu b modulo n (scriu a ≡ b mod n) daca n | a− b.

Observatie. Pentru n = 0 relatia de congruenta mod 0 este relatia de egalitate.Pentru n = 1 relatia de congruenta mod 1 este relatia universala. In continuare vompresupune n ≥ 2.Proprietati ale relatiei de congruenta mod n.

1) Congruenta mod n este o relatie de echivalenta pe Z (este reflexiva, simetricasi tranzitiva).

26

2) Congruenta mod n este compatibila cu operatiile de adunare si ınmultire pe

Z: daca x ≡ x′ si y ≡ y′ (mod n) atunci

{x+ x′ ≡ y + y′ (mod n)x · x′ ≡ y · y′ (mod n).

3) a ≡ b (mod n) ⇐⇒ a · c ≡ b · c (mod n), ∀c ∈ Z.

4) a ≡ b (mod n) =⇒ am ≡ bm (mod n), ∀m ∈ N.

5) a ≡ b (mod n) si m | n =⇒ a ≡ b (mod m).

6) a · c ≡ b · c (mod n), (c, n) = 1 =⇒ a ≡ b (mod n).

7) a · c ≡ b · c (mod n), (c, n) = d =⇒ a ≡ b (mod n/d).

8) a ≡ b (mod mi), i = 1, k =⇒ a ≡ b (mod m), m = [m1,m2, ...,mk].

Demonstratie. Vom demonstra proprietatile 7) si 8).7) Deoarece (c, n) = d exisa c1, n1 ∈ Z astfel ıncat (c1, n1) = 1, c = c1d si

n = n1d. Daca a · c ≡ b · c (mod n) atunci n | c · (a − b). Aceasta ınseamna can1 · d | c1 · d · (a− b) =⇒ n1 | c1 · (a− b). Deoarece (n1, c1) = 1 din ultima relatie dedivizibilitate se obtine n1 | a− b ceea ce implica a ≡ b (mod n1 = n/d).

8) Demonstratia se face prin inductie dupa k. Pentru k = 2 presupunemm1 | a−bsi m2 | a − b, ceea ce ınseamna ca a − b = m1x = m2y. Daca d = (m1,m2)atunci exista u, v ∈ Z astfel ıncat d = um1 + vm2. Inmultind cu a − b avemd(a−b) = um1m2y+vm2m1x = m1m2(uy+vx) = [m1,m2]d(uy+vx). Simplificandcu d se otine ca [m1,m2] | a− b. Pentru etapa inductiva se foloseste un rationamentasemanator.

Propozitia 5 (Criteriu de congruenta mod n) Doua numere ıntregi a si b suntcongruente mod n daca si numai daca au acelasi rest la ımpartirea cu n.

Demonstratie. Fie a = nq1 + r1 si b = nq2 + r2 cu 0 ≤ r1 < n si 0 ≤ r2 < n deunde obtinem 0 ≤ |r1 − r2| < n. Avem echivalentele a ≡ b (mod n) ⇐⇒ n | a − b⇐⇒ n | r1−r2. Folosind inegalitatea 0 ≤ |r1−r2| < n, ultima relatie de divizibilitateeste echivalenta cu r1 − r2 = 0.

Observatie Singurele subgrupuri ale grupului aditiv (Z,+) sunt de forma nZ,n ∈ N. Clasele de echivalenta modulo n sunt clasele relativ la aceste subgrupuri,ceea ce ınseamna ca a = a+ nZ.

27

9.1 Inelul claselor de resturi modulo n

Definitia 13 Clasa de echivalenta modulo n a numarului ıntreg a se noteaza a ={b ∈ Z, a ≡ b} = a + nZ. Vom folosi notatia Zn := Z/≡ = Z/nZ pentru multimeafactor, pe care o numim multimea claselor de resturi modulo n.

Conform Propozitiei 5 obtinem ca multimea claselor de resturi modulo n poatefi explicit scrisa astfel: Zn = {0, 1, ..., n− 1}.

Definitia 14 Numerele ıntregi a1, a2, ..., an formeaza un sistem complet de resturi(scr) modulo n daca Zn = {a1, a2, ..., an}.

Teorema 24 (Sisteme complete de resturi modulo n) Fie r1, ..., rn un sistem com-plet de resturi modulo n si a, b ∈ Z astfel ıncat (a, n) = 1. Atunci ar1 +b, ..., arn+bformeaza un sistem complet de resturi modulo n.

Demonstratie. Trebuie demonstrat ca cele n numere ari + b, i = 1, n nu sunt,doua cate doua, congruente mod n. Prin reducere la absurd presupunem ca existai, j ∈ {1, 2, ..., n}, i 6= j astfel ıncat ari + b ≡ arj + b (mod n), de unde obtinemari ≡ arj (mod n). Deoarece (a, n) = 1, conform Proprietatii 6), se obtine ri ≡ rj(mod n), ceea ce este fals.

Pe multimea claselor de resturi modulo n, Zn se definesc operatiile de adunaresi ınmultire astfel:

a+ b := a+ b, a · b := a · b. (5)

Conform Proprietatii 2, operatiile astfel definite nu depind de alegerea reprezentantilor.

Teorema 25 Multimea Zn = {0, 1, ..., n− 1} a claselor de resturi modulo n, ınzestratacu operatiile de adunare si ınmultire a claselor de resturi modulo n, definite prinrelatiile (5), formeaza un inel comutativ si unitar.

Demonstratie. Se demonstreaza, folosind proprietatile adunarii si ınmultirii ın in-elul Z al numerelor ıntregi, urmatoarele proprietati ale adunarii si ınmultirii modulon:

1) (a+ b) + c = a+ (b+ c), ∀ a, b, c ∈ Zn;

2) a+ b = b+ a, ∀ a, b ∈ Zn;

3) a+ 0 = 0 + a = a, ∀ a ∈ Zn;

4) a+ −a = −a+ a = 0, ∀ a ∈ Zn;

28

5) (a · b) · c = a · (b · c), ∀ a, b, c ∈ Zn;

6) a · b = b · a, ∀ a, b ∈ Zn;

7) a · 1 = 1 · a = a, ∀ a ∈ Zn;

8) a · (b+ c) = a · b+ a · c, ∀ a, b, c ∈ Zn;

Propozitia 6 1) O clasa de resturi a ∈ Zn este element inversabil ın inelul Zndaca si numai daca (a, n) = 1.

2) Inelul Zn are divizori ai lui zero daca si numai daca n este numar decompoz-abil.

3) Zn este corp daca si numai daca n este numar prim.

Demonstratie.1) Elementul a ∈ Zn este inversabil daca si numai daca exista b ∈ Zn astfel ıncat

a · b = 1 ⇐⇒ n | ab − 1 ⇐⇒ ∃q ∈ Z astfel ıncat ab − 1 = qn ⇐⇒ ab + (−q)n = 1⇐⇒ (a, n) = 1. Obtinem ca unitatile inelului Zn sunt: U(Zn) = {a ∈ Zn, (a, n) =1}.

2) Elementul a ∈ Zn (1 < a < n) este divizor al lui zero daca si numai daca exisab ∈ Zn (1 < b < n) astfel ıncat a · b = 0 ⇐⇒ n | ab. Deoarece n 6 | a si n 6 | b (altfelare rezulta n ≤ a sau n ≤ b) se obtine ca n nu este numar prim, ceea ce ınseamnaca este un numar compus.

3) Deoarece inelul Zn este finit obtinem ca este corp daca si numai daca nu aredivizori ai lui zero. Aceasta se ıntampla daca si numai daca n este numar prim.

9.2 Functia indicatoare a lui Euler

Functia ϕ : N∗ −→ N∗ definita prin ϕ(n) = numarul numerelor naturale mai micidecat n si prime cu n, se numeste functia indicatoare a lui Euler. Putem deci exprimafunctia indicatoare a lui Euler astfel: ϕ(n) = card{a ∈ Zn, (a, n) = 1} = cardU(Zn).

Daca U(Zn) = {r1, r2, ..., rϕ(n)} spunem ca r1, r2, ..., rϕ(n) formeaza un sistemredus de resturi (srr) modulo n. Cu o demonstrati asemanatoare cu cea facuta ıncazul sistemelor complete de resturi modulo n (Teorema 24) se poate demonstraurmatorul rezultat:

Propozitia 7 (Sisteme reduse de resturi modulo n) Fie r1, r2, ..., rϕ(n) un sistemredus de resturi modulo n si a ∈ Z astfel ıncat (a, n) = 1. Atunci: a · r1, a · r2, ...,a · rϕ(n) formeaza un sistem redus de resturi modulo n.

29

Teorema 26 Functia indicatoare a lui Euler are urmatoarele proprietati:

1) ϕ(pα) = pα (1− 1/p), pentru p un numar prim si α ∈ N∗;

2) ϕ este functie multiplicativa: daca m,n ∈ N cu (m,n) = 1 atunci ϕ(m · n) =ϕ(m) · ϕ(n);

3) daca m1,m2, ...,ms ∈ N cu (mi,mj) = 1, ∀i 6= j atunci ϕ(m1 ·m2 · · ·ms) =ϕ(m1) · ϕ(m2) · · ·ϕ(ms).

4) daca n = pα11 · pα2

2 · · · pαkk este descompunerea canonica a numarului natural n

atunci

ϕ(n) = n

(1− 1

p1

)(1− 1

p2

)· · ·(

1− 1

pk

).

Demonstratie.1) Deoarece p este numar prim avem ca (a, pα) = 1 daca si numai daca (a, p) = 1

ceea ce este echivalent cu p 6 | a. Avem ca ϕ(pα) = pα− numarul multiplilor de p maimici sau egali decat pα. Acesti multipli sunt: 1 · p, ..., p · pα−1, ın numar de pα−1. Inconsecinta ϕ(pα) = pα − pα−1.

2) Pentru doua numere prime ıntre ele m si n avem ca (a,mn) = 1 daca si numaidaca (a,m) = 1 si (a, n) = 1.

Presupunem m > 1 si n > 1. Un sistem complet de resturi modulo m · n este:1, 2, ...,m · n pe care ıl aranjam ıntr-un tabel cu n linii si m coloane:

1 2 · · · r · · · mm+ 1 m+ 2 · · · m+ r · · · 2m

......

......

......

(n− 1)m+ 1 (n− 1)m+ 2 · · · (n− 1)m+ r · · · nm

In acest tabel oricare din cele n linii este un sistem complet de resturi modulo m sioricare din cele m coloane este un sistem complet de resturi modulo n.

In tabel sunt ϕ(m·n) numere prime cu m·n. Cum am observat anterior un numareste prim cu m · n daca si numai daca este prim atat cu m cat si cu n. Deoarece(km + r,m) = (r,m) toate elementele de pe coloana r au acelasi c.m.m.d.c. cu m.Rezulta ca fie toate elementele de pe o coloana sunt prime cu m fie nu sunt. Inconsecinta doar ϕ(m) coloane, din cele m, contin numere prime cu m. Fiecare astfelde coloana este un s.c.r mod n. Pe fiecare dintre aceste ϕ(m) coloane avem ϕ(n)numere prime cu n. Se obtine ca tabelul contine ϕ(m) ·ϕ(n) numere prime cu m ·n,ceea ce demonstreaza ca ϕ(m · n) = ϕ(m) · ϕ(n).

3) Se demonstreaza prin inductie dupa s. Pentru 4) se folosesc ın mod directpunctele 1) si 3) anterioare.

30

Teorema 27 Pentru orice numar natural n ∈ N∗ avem∑

d|n ϕ(d) = n.

Demonstratie. Daca n = pα11 · · · p

αkk este descompunerea canonica numarului n > 1

atunci∑d|n ϕ(d) =

∑0≤βi≤αi, i=1,k ϕ(pα1

1 ) · · ·ϕ(pαkk )

= [1 + ϕ(p1) + ϕ(p21) + · · ·+ ϕ(pα11 )] · · · [1 + ϕ(pk) + ϕ(p2k) + · · ·+ ϕ(pαk

k )]

= [1 + (p1 − 1) + (p21 − p1) + · · · (pα11 − pα1−1

1 )] · · · [1 + (pk − 1) + (p2k − pk) + · · ·+ (pαkk − p

αk−1k )]

= pα11 · · · p

αkk = n.

9.3 Teoreme celebre

Teorema 28 (Teorema lui Euler) Fie n ∈ N, n ≥ 2 si a ∈ Z astfel ıncat (a, n) = 1.Atunci aϕ(n) ≡ 1 (mod n).

Demonstratie. Fie r1, r2, ..., rϕ(n) un sistem redus de resturi modulo n. Cum(a, n) = 1, conform Propozititiei 7, obtinem ca ar1, ar2, ..., arϕ(n) este deasemeneaun sistem redus de resturi modulo n. Aceasta ınseamna ca produsele acestor douasrr sunt congruente modulo n, deci aϕ(n)r1 · · · rϕ(n) ≡ r1 · · · rϕ(n) (mod n). Deoarece

(ri, n) = 1 ∀i = 1, ϕ(n) obtinem ca (r1 · · · rϕ(n), n) = 1. Folosind proprietatea 6)pentru congruenta modulo n, se obtine aϕ(n) ≡ 1 (mod n).Observatie Am vazut deja ca a ∈ Zn este inversabil daca si numai daca (a, n) = 1.

In acest caz inversul lui a este aϕ(n)−1.

Teorema 29 (Teorema lui Fermat) Fie p un numar prim si a ∈ Z astfel ıncatp 6 | a (ceea ce este echivalent cu (a, p) = 1). Atunci ap−1 ≡ 1 (mod p), ceea ce esteechivalent cu ap ≡ a (mod p).

Teorema 30 (Teorema lui Wilson) Daca p este un numar prim atunci (p−1)!+1 ≡0 (mod p). Reciproc, daca p ∈ N \ {0, 1} astfel ıncat (p− 1)! + 1 ≡ 0 (mod p) atuncip este prim.

Demonstratie. Daca p este prim atunci U(Zp) = {1, 2, ..., p− 1}, ceea ce ınseamnaca toate elementele sunt inversabile. Deoarece (p−1)·(p−1) ≡ 1 (mod p), obtinem ca

p− 1−1

= p− 1. Cum 1−1 = 1, obtinem ca ∀a ∈ Zp \{1, p− 1}, ∃b ∈ Zp \{1, p− 1}astfel ıncat a · b ≡ 1 (mod p). Vom demonstra ca a 6= b. Prin reducere la absurd

31

presupunem ca a = b, si deci a2 ≡ 1 (mod p). Aceasta ınseamna ca p | (a−1)(a+ 1)si cum p este prim are rezulta ca p | a − 1 sau p | a + 1, ceea ce este fals deoarece

a − 1 < a + 1 < p. Aceasta ınseamna ca 2 · 3 · · · p− 2 = 1, de unde obtinem ca(p− 1)! = p− 1, ceea ce este echivalent cu (p− 1)! + 1 ≡ 0 (mod p).

Reciproc, fie p ∈ N astfel ıncat (p − 1)! + 1 ≡ 0 (mod p). Prin reducere laabsurd presupunem ca p este neprim, ceea ce ınseamna ca este decompozabil, si deciexista 1 < b, c < p astfel ıncat p = bc. Aceasta ınseamna ca bc ≡ 0 (mod p). Sapresupunem acum ca b 6= c, cum b, c ≤ p − 1 obtinem (p − 1)! ≡ 0 (mod p), ceeace contrazice ipoteza. Daca b = c avem p = b2, b > 2 de unde rezulta 2b < b2 = p.Atunci b 6= 2b si (p − 1)! = · · · b · · · 2b · · · ≡ 0 (mod p), ceea ce contrazice din nouipoteza. In concluzie p este numar prim.

Teorema 31 (Lema chineza a resturilor) Fie a1, a2, ..., an ∈ Z arbitrare si m1,m2, ..., mn ∈ N∗ astfel ıncat (mi,mj) = 1, ∀i 6= j. Atunci sistemul de congruentex ≡ ai (mod mi), i = 1, n, admite o solutie ın Z, unica pana la congruenta moduloM = m1 · · ·mn.

Demonstratie. Vom nota Mi = M/mi = m1 · · ·mi−1 · mi+1 · · ·mn. Deoarece(mi,Mi) = 1, exista ui, vi ∈ Z astfel ıncat uiMi + vimi = 1. Aceasta ınseamnaca uiMi ≡ 1 (mod mi) si uiMi ≡ 0 (mod mj) pentru j 6= i. Consideram x =∑n

i=1 uiaiMi pentru care avem ca x ≡ ai (mod mi) ∀i ∈ {1, 2, ..., n}. Pentru oricealta solutie y a sistemului y ≡ ai (mod mi) ∀i ∈ {1, 2, ..., n} avem mi | x− y, ∀i, sicum (mi,mj) = 1, ∀i 6= j obtinema ca M | x− y.

10 Congruente de gradul I cu o necunoscuta. Ecuatii

diofantice de gradul I cu doua necunoscute.

Propozitia 8 Fie n ∈ N∗ fixat si a, b ∈ Z. Orice solutie a congruentei de gradul I,ax ≡ b (mod n) determina o solutie a ecuatiei diofantice ax+ ny = b si reciproc.

Demonstratie. Daca x0 este o solutie a congruentei ax ≡ b (mod n) atunci n |ax0 − b, si deci exista y0 ∈ Z astfel ıncat ax0 − b = ny0. Rezulta ca (x0, y0) este osolutie a ecuatie diofantice ax+ ny = b.

Reciproc daca ax0 + ny0 = b atunci evident ax0 ≡ b (mod n).

Teorema 32 1) Congruenta ax ≡ b (mod n) are solutii daca si numai dacad = (a, n) | b.

32

2) Daca x0 este o solutie a congruentei ax ≡ b (mod n) atunci exista exactd = (a, n) solutii, distincte modulo n, ale acestei congruente si acestea sunt:x0, x0 + n1, ..., x0 + (d− 1)n1, unde n = n1d.

Demonstratie. 1) Necesitatea: Fie (x0, y0) solutie a ecuatiei diofantice core-spunzatoare, deci ax0 + ny0 = b. Daca d = (a, n) atunci a = da1 si n = dn1

cu (a1, n1) = 1. Obtinem b = d(a1x0 + n1y0) ceea ce ınseamna ca d | b.Suficienta: Presupunem ca d = (a, n) | b. Avem ca b = db1 si exista x1, y1 ∈ Z

astfel ıncat ax1 + ny1 = d. Inmultind cu b1 obtinem ax1b1 + ny1b1 = b, ceea ceınseamna ca x1b1 este solutie a congruentei ax ≡ b (mod n).

2) Fie x0 si x1 solutii ale congruentei ax ≡ b (mod n). Aceasta ınseamna caax0 ≡ ax1 (mod n). Daca a = a1d si n = n1d, (a1, n1) = 1 atunci n1 | a1(x1 − x0),de unde obtinem ca n1 | x1 − x0. Aceasta ınseamna ca exista t ∈ Z astfel ıncatx1 = x0 + n1t. Folosind TIR pentru t si d avem t = dq + r, r ∈ {0, 1, ..., d − 1}.Aceasta ın seamna ca x1 = x0 + n1r + nq. Pentru r ∈ {0, 1, ..., d − 1}, numerelex0 + n1r sunt distincte modulo n si sunt solutii ale congruentei date.

33