am adus îmbunătăţiri paragrafelor 4 şi 7 de la Capitolul 7, ca şi paragrafului 3 de la Capitolul 11

DUMITRU BUŞNEAG ( COORDONATOR )

FLORENTINA BOBOC DANA PICIU

EDITURA UNIVERSITARIA CRAIOVA

1999

Referenţi ştiinţifici : Prof. univ. dr. Alexandru Dincă – Universitatea din Craiova.

Prof. univ. dr. François Gramain – Université Jean Monnnet, Saint -Étienne, France.

Dumitru Busneag, Florentina Boboc, Dana Piciu:

Arithmetic and number theory

© 1999 EUC – CRAIOVA

All rights reserved. No part of this publication may be reproduced, stored in a retrieval system, or transmitted, in any form or by any means, electronic, mechanical, photocopying, recording, or other wise, without the prior written permission of the publisher.

Tehnoredactare computerizată: Florentina Boboc, Dana Piciu Bun de tipar: 11.05.1999

Tipografia Universităţii din Craiova Str. Al. I. Cuza

Craiova, România.

Published in Romania by Editura Universitaria Craiova ISBN: 973 – 9271 – 73 - 1

CUVÂNT ÎNAINTE

Această lucrare este o ediţie revizuită şi îmbunătăţită a lucrării Elemente de aritmetică şi teoria numerelor, având aceiaşi autori, şi care a fost publicată în anul 1998, la editura Radical din Craiova (I.S.B.N. 973-9253-52-0).

Faţă de vechea ediţie, pe lângă îndreptarea unor mici erori (atât de redactare cât şi de tehnoredactare ), am adus îmbunătăţiri paragrafelor 4 şi 7 de la Capitolul 7, ca şi paragrafului 3 de la Capitolul 11.

În finalul Capitolului 12 am introdus un nou paragraf (paragraful 6) în care se prezintă rezolvarea în numere întregi a sistemelor de ecuaţii liniare cu coeficienţi întregi.

Pentru fiecare capitol s-au introdus exerciţii suplimentare cu soluţii complete.

În finalul lucrării s-au ataşat următoarele anexe:

Anexa 1: Tabelul cu numerele prime ( evidenţiind numerele prime gemene) de la 1 la 10.000.

Anexa 2: Funcţia p

( )

Anexa 3: Numerele lui Fermat, numerele lui Mersenne şi numere perfecte.

Dacă lucrarea iniţială avea 254 pagini format A5 , prezenta ediţie are 288 pagini (acelaşi format ).

Craiova, 20 aprilie 1999. Autorii.

L. Kronecker : Dumnezeu a creat numerele naturale – restul este munca omului .

CAPITOLUL 1 :

MULŢIMEA NUMERELOR NATURALE ℕ.

§ 1 Triplete Peano

DEFINIŢIA 1.1. Numim triplet Peano un triplet ( N, 0, s ) unde N este o mulţime nevidă, 0∈N iar s:N→N este o funcţie astfel încât sunt verificate axiomele :

P1 : 0∉s( N )

P2 : s este o funcţie injectivă

P3 : dacă P⊆N este o submulţime astfel încât 0∈P şi (n∈P⇒s(n)∈P ), atunci P=N .

În cele ce urmează, acceptăm ca axiomă existenţa unui triplet Peano (cititorului dornic de aprofundarea acestei chestiuni îi recomandăm lucrările [7]

şi [19] ) .

LEMA 1.2. Dacă ( N, 0, s ) este un triplet Peano, atunci N={0}∪s(N).

Demonstraţie Dacă notăm P={0}∪s (N), atunci P⊆N şi cum P verifică P3, deducem că P=N .∎

TEOREMA 1.3. Fie ( N, 0, s ) un triplet Peano iar ( Nʹ, 0ʹ, s ʹ ) un alt triplet format dintr-o mulţime nevidă Nʹ, un element 0ʹ∈Nʹ şi o funcţie sʹ:Nʹ → Nʹ. Atunci :

1 ) Există o unică funcţie f:N→Nʹ astfel încât f(0)= 0ʹ, iar diagrama

N

¾ ¾®

¾ ¾®

este comutativă (adică f ∘ s = sʹ∘f ) .

2 ) Dacă ( Nʹ, 0ʹ, sʹ) este un triplet Peano, atunci f este bijecţie.

Demonstraţie 1) Pentru a proba existenţa lui f, vom considera toate relaţiile R⊆N×Nʹ a.î. :

r1 : (0, 0ʹ)∈ R

r2 : Dacă (n, nʹ)∈R, atunci (s(n), sʹ(nʹ))∈R iar prin R0 vom nota intersecţia acestor relaţii .

Vom demonstra că R0 este o relaţie funcţională şi astfel f va fi funcţia ce va avea drept grafic pe R0 (astfel, din (0, 0ʹ)∈R0 vom deduce că f (0)=0ʹ iar dacă n∈N şi f (n)=nʹ∈Nʹ, (n , nʹ)∈R0, deci (s(n), sʹ(nʹ))∈R0, adică, f(s(n))=sʹ(nʹ)=sʹ(f (n)).

Pentru a demonstra că R0 este o relaţie funcţională, vom demonstra că pentru orice n∈N, există nʹ∈Nʹ a. î. (n, nʹ)∈R 0 iar dacă pentru n∈N şi nʹ, nʹʹ∈Nʹ avem (n, nʹ)∈R0 şi (n, nʹʹ)∈R0 , atunci nʹ= nʹʹ .

Pentru prima parte, fie P={n∈N : există nʹ∈Nʹ a. î. (n, nʹ)∈R0 }⊆N.

Cum (0, 0ʹ)∈R0 deducem că 0∈P. Fie acum n∈P şi nʹ∈Nʹ a.î. (n, nʹ)∈R0. Din definiţia lui R0 deducem că (s(n), sʹ(nʹ))∈R0 ; obţinem că s(n)∈P şi cum (N, 0, s) este triplet Peano, deducem că P=N.

Pentru a doua parte, fie

Q={n∈N : dacă nʹ, nʹʹ∈N ʹ şi (n, nʹ), (n, nʹʹ)∈R0 ⇒ nʹ= nʹʹ}⊆N şi să demonstrăm la început că 0∈Q.

În acest sens, vom demonstra că dacă (0, nʹ)∈R0 atunci nʹ=0ʹ. Dacă prin absurd, nʹ≠0ʹ, atunci vom considera relaţia R1=R0 ∖{(0, nʹ)}⊆N×Nʹ. Din nʹ≠0ʹ deducem că (0, 0ʹ)∈R1 iar dacă pentru m∈Nʹ avem (n, m)∈R1 , atunci (n, m)∈R0 şi (n , m) ≠ (0, nʹ). Astfel (s(n), sʹ(m))∈R0 şi cum (s(n), sʹ(m))≠(0, nʹ) (căci s(n) ≠ 0 conform cu P1), deducem că (s(n), sʹ(m))∈R1 . Cum R1 verifică r1

şi r2 ar trebui ca R0⊆R1 – absurd (căci R1 este inclusă strict în R0 ).

Pentru a proba că 0∈Q, fie nʹ, nʹʹ∈Nʹ a. î. (0, nʹ), (0 , nʹʹ)∈R0. Atunci, ţinând cont de cele stabilite mai sus, deducem că nʹ=nʹʹ=0ʹ, deci 0∈Q.

Fie acum n∈Q şi n ʹ∈N ʹ a. î. (n, nʹ)∈R0 ; vom demonstra că dacă (s(n), nʹʹ)∈R0, atunci nʹʹ=sʹ(nʹ). Să presupunem prin absurd că nʹʹ≠ sʹ(nʹ) şi să considerăm relaţia R2 =R0 ∖{(s (n), nʹʹ)} . Vom demonstra că R2 verifică r1 şi r2 .

Într–adevăr, (0, 0ʹ)∈R2 ( căci 0 ≠ s(n) ) iar dacă (p, pʹ)∈R2 , atunci (p, pʹ)∈R0 şi (p, pʹ)≠( s(n), nʹʹ) .

Deducem că (s(p), sʹ(pʹ))∈R0 şi dacă presupunem (s(p), sʹ(pʹ))=

=(s(n), nʹʹ), atunci s(p) =s(n), deci p=n. De asemenea, sʹ(pʹ)=nʹʹ.

Atunci (n, nʹ)∈R0 şi (n, pʹ)∈R0 iar cum n∈Q ⇒ nʹ=pʹ, deci nʹʹ=sʹ(pʹ)=sʹ(nʹ), ceea ce contrazice faptul că nʹʹ≠s(nʹ). Prin urmare, (s(p), sʹ(pʹ))≠ (s(n), nʹʹ), ceea ce ne arată că (s(p), sʹ(pʹ))∈R2 , adică R2 satisface r1 şi r2 . Din nou ar trebui ca R0⊂R2 – absurd !.

Deci (s (n), nʹʹ)∈R0⇒ nʹʹ=sʹ(nʹ) astfel că dacă r, s ∈N ʹ şi (s(n), r), (s(n), s )∈R0 , atunci r = s = sʹ(n), adică s(n)∈Q, deci Q=N.

Pentru a proba unicitatea lui f, să presupunem că mai există fʹ:N→Nʹ a.î. fʹ(0)=0ʹ şi sʹ(fʹ(n))=fʹ(s(n)) pentru orice n∈N.

Considerând P={n∈N : f(n)=fʹ(n)}⊆N, atunci 0∈P iar dacă n∈P (adică f(n)=fʹ(n)), atunci sʹ(f(n))=sʹ(fʹ(n))⇒f(s(n))=fʹ(s(n))⇒s(n)∈P şi atunci P=N, adică f=fʹ.

2) Să arătăm la început că f este injectivă. Pentru aceasta vom considera P={n∈N : dacă m∈N şi f(m)=f(n)⇒m=n}⊆N şi să demonstrăm la început că 0∈P. Pentru aceasta fie m∈N a. î. f(0)=f(m) şi să demonstrăm că m=0. Dacă prin absurd m≠0, atunci m=s(n) cu n∈N iar egalitatea f(m)=f(0) devine f(s(n))=f(0)=

=0ʹ, de unde sʹ(f(n))=0ʹ, ceea ce este absurd deoarece prin ipoteză (Nʹ, 0ʹ, sʹ) este un triplet Peano.

Fie acum n∈P; pentru a demonstra că s(n)∈P, fie m∈N a.î.

f(m)=f(s(n)).

Atunci m≠0 (căci în caz contrar ar rezulta că 0ʹ=f(0)=f(s(n))=sʹ(f(n)), absurd !), deci conform Lemei 1.2., m=s(p) cu p∈N iar egalitatea f(m)=f(s(n)) devine f(s(p))=f(s(n))⇔sʹ(f(p))=sʹ(f(n)), adică f(p)=f(n) şi cum n∈P, atunci n=p şi astfel m=s(p)=s(n).

Pentru a demonstra surjectivitatea lui f să considerăm Pʹ={nʹ∈Nʹ:există n∈N a. î. nʹ=f (n)}⊆Nʹ .

Cum f(0)=0ʹ deducem că 0ʹ∈Pʹ. Fie acum nʹ∈Pʹ ; atunci există n∈N a.î. nʹ=f (n). Deoarece sʹ(nʹ)=sʹ(f(n))=f(s(n)), deducem că sʹ(nʹ)∈Pʹ şi cum

tripletul (Nʹ, 0ʹ, sʹ) este un triplet Peano, deducem că Pʹ=Nʹ, adică f este şi surjectivă, deci bijectivă . ∎

Observaţie Conform Teoremei 1.3. (cunoscută şi sub numele de teorema de recurenţă ) un triplet Peano este unic până la o bijecţie.

În cele ce urmează vom alege un triplet Peano oarecare (ℕ, 0, s) şi pe care îl vom fixa ; elementele lui ℕ le vom numi numere naturale .

Elementul 0 va purta numele de zero . Notăm ℕ* = ℕ \ {0}.

Vom nota 1=s(0), 2=s(1), 3=s(2), e.t.c., astfel că ℕ={0, 1, 2, …}.

Funcţia s poartă numele de funcţia succesor . Axiomele P1 – P3 sunt cunoscute sub numele de axiomele lui Peano .

Axioma P3 poartă numele de axioma inducţiei matematice.

§2 Adunarea numerelor naturale

TEOREMA 2.1. Există o unică operaţie algebrică pe ℕ pe care o vom nota prin „+” şi o vom numi adunarea numerelor naturale astfel încât pentru orice m, n∈ℕ să avem :

A1 : 0+m=m

A2 : s(n)+m=s(n+m) .

Demonstraţie Să probăm la început unicitatea şi pentru aceasta să presupunem că mai există o operaţie algebrică ⊕ pe ℕ a.î. sunt verificate A1şi A2.

Fie P={n∈ℕ | n+m=n⊕m, pentru orice m∈ℕ}⊆ℕ.

Din A1 deducem că 0∈P iar din A2 deducem că dacă n∈P, atunci s(n)+m=s(n)⊕m ⇔ s(n+m)=s(n⊕m), ceea ce este adevărat deoarece s este injectivă şi am presupus că n∈P. Deci P=ℕ, adică cele două operaţii coincid.

Considerăm un element m∈ℕ (pe care îl fixăm) şi tripletul (ℕ, m, s) ; conform Teoremei 1.3. există o unică funcţie fm:ℕ→ℕ a. î. fm(0)=0 şi s(fm(n))=

=fm(s(n)) pentru orice n∈ℕ .

Pentru n∈ℕ definim n+m=fm (n). Atunci 0+m=fm(0)=m iar s(n)+m=

=fm (s(n))=s (fm (n))=s( n+m ). ∎

Observaţie Axiomele A1–A2 poartă numele de axiomele adunării numerelor naturale.

PROPOZIŢIA 2.2. Pentru orice m, n∈ℕ avem

0

A

20

A : n+s (m)= s(n+m) .

Demonstraţie Fie P={m∈ℕ: m+0=m }⊆ℕ. Dacă în A1 facem pe m=0, deducem că 0+0=0, adică 0∈P. Dacă m∈P, (adică m+0=m), atunci s(m)+0=s(m+0)=s(m), adică s(m)∈P, deci P=ℕ. Analog se probează şi a doua relaţie.∎

PROPOZIŢIA 2.3. Dubletul (ℕ, +) este monoid comutativ cu proprietatea de simplificare.

Demonstraţie Din cele stabilite anterior, deducem că 0 este element neutru pentru adunarea numerelor naturale.

Pentru a proba comutativitatea adunării să considerăm P={n∈ℕ : n+m=m+n pentru orice m∈ℕ}⊆ℕ .

Evident 0∈P. Dacă n∈P, adică n+m=m+n pentru orice m∈ℕ, atunci s(n)+m=m+s(n) ⇔ s(n+m)=s(m+n) ⇔ n+m=m+n, ceea ce este adevărat.

Deducem că P=ℕ, adică adunarea numerelor naturale este comutativă .

Pentru a demonstra asociativitatea adunării numerelor naturale, să considerăm

P ={p∈ℕ: (m+n)+p=m+(n+p) pentru orice m, n∈ℕ}⊆ℕ. Evident 0∈P. Fie acum n∈P. Atunci (s(n)+m)+p=s(n+m)+p=

=s(n+(m+p)) iar s(n)+(m+p)=s(n+(m+p)) şi cum (n+m)+p=n+(m+p) deducem că s(n)∈P, adică P=ℕ.

Pentru partea finală fie

P={p∈ℕ : dacă m+p=n+p ⇒ m=n}⊆ℕ.

Evident 0∈P şi să presupunem că p∈P. Atunci m+s(p)=n+s(p)

⇔s(m+p)=s(n+p) ⇔ m+p=n+p ⇔ m=n (căci p∈P), adică s(p)∈P şi astfel din nou P=ℕ. ∎

Observaţie Dacă n∈ℕ, atunci s(n)=s(n+0)=n+s(0)=n+1.

PROPOZIŢIA 2.4. Dacă m, n∈ℕ şi m+n=0, atunci m=n=0.

Demonstraţie Dacă m ≠ 0 sau n ≠ 0, atunci există p, q∈ℕ a. î. m = s(p) sau n = s(q). În primul caz, obţinem că m+n = s(p)+n = s(p+n) ≠ 0 – absurd ! şi analog în al doilea caz. Deci m = n = 0 . ∎

§3 Înmulţirea numerelor naturale

PROPOZIŢIA 3.1. Există o unică operaţie algebrică pe ℕ notată

„·” şi numită înmulţirea numerelor naturale a.î. pentru orice m, n∈ℕ să avem :

I1 : m·0=0

I2 : m·s(n)=mn+m.

Demonstraţie Fie m∈ℕ fixat ; considerând tripletul (ℕ, 0, fm ), unde fm:ℕ→ℕ este definită prin fm(n)=n+m pentru orice n∈ℕ, atunci conform Teoremei 1.3. există o unică funcţie g m :ℕ→ℕ a.î. gm (0)=0 şi fm∘gm =gm ∘s.

Definim m·n = gm(n) şi astfel m·0=gm(0)=0 iar m·s(n)=gm(s(n)=

=fm(gm(n))=fm(m·n)=m·n+m . Unicitatea operaţiei de înmulţire cu proprietăţile I1

şi I2 se probează ca în cazul adunării. ∎

Observaţie I1 şi I2 poartă numele de axiomele înmulţirii numerelor naturale.

În cele ce urmează, dacă nu este pericol de confuzie, vom scrie m·n=

=mn pentru m, n∈ℕ.

Analog ca în cazul adunării numerelor naturale, se demonstrează că pentru oricare numere naturale m, n avem :

0

I

20

I : s(n)·m=nm+m.

LEMA 3.2. Înmulţirea numerelor naturale este distributivă la stânga faţă de adunarea numerelor naturale.

Demonstraţie Fie P={p∈ℕ : m(n+p)=mn+mp pentru oricare m, n∈ℕ}⊆ℕ.

Ţinând cont de I1 deducem că 0∈P.

Să presupunem acum că p∈P şi fie m, n∈ℕ.

Avem m(n+s(p))=m(s(n+p))=m(n+p)+m=mn+mp+m=mn+ms(p), adică s(p)∈P şi astfel P=ℕ . ∎

PROPOZIŢIA 3. 3. Dubletul (ℕ, ·) este monoid comutativ.

Demonstraţie Pentru a proba asociativitatea înmulţirii fie

P={p∈ℕ : (mn)p=m(np) pentru oricare m, n∈ℕ}⊆ℕ. În mod evident, 0∈P. Să presupunem acum că p∈P şi să demonstrăm că s(p)∈P. Avem (mn)s(p)=

=(mn)p+mn iar m(ns(p))=m(np+n)=m(np)+mn (conform Lemei 3.2.), de unde egalitatea (mn)s(p)=m(ns(p)), adică s(p)∈P, deci P=ℕ.

Deoarece pentru orice n∈ℕ avem n·1=n·s(0)=n·0+n=n iar 1·n=s(0)·n=

=0·n+n=n deducem că 1 este elementul neutru al înmulţirii numerelor naturale.

Pentru a proba comutativitatea înmulţirii numerelor naturale fie P={n∈ℕ : nm=mn pentru orice m∈ℕ}⊆ℕ.

În mod evident 0∈P şi să presupunem că n∈ℕ. Atunci pentru orice m∈ℕ, s(n)·m=n·m+m iar m·s(n)=mn+m, de unde s(n)·m=m·s(n), adică s(n)∈P, deci P=ℕ . ∎

§4 Relaţia naturală de ordine de pe ℕ .

DEFINIŢIA 4.1. Pentru m, n∈ℕ vom scrie m≤n (şi vom spune că m este mai mic sau egal decât n sau că n este mai mare sau egal decât m) dacă există p∈ℕ a.î. m+p=n ; convenim în acest caz să notăm p=n-m.

Dacă p∈ℕ*, atunci m≤n şi m≠n ; în acest caz vom scrie m<n şi vom spune că m este strict mai mic decât n.

LEMA 4.2. Dacă m, n∈ℕ şi m<n, atunci s(m)≤n.

Demonstraţie Deoarece m<n, există p∈ℕ* a.î. m+p=n. Cum p∈ℕ*, există k∈ℕ a. î. p=s(k) (conform Lemei 1.2.). Atunci din m+p=n deducem că m+s(k)=n ⇒ s(m+k)=n ⇒ s(m)+k=n ⇒s(m)≤ n . ∎

COROLAR 4.3. Pentru orice n∈ℕ, n<s(n).

PROPOZIŢIA 4.4. Dubletul (ℕ, ≤) este o mulţime total ordonată.

Demonstraţie Deoarece pentru orice n∈ℕ, n+0=n deducem că n≤n, adică relaţia ≤ este reflexivă. Fie acum m, n∈ℕ a. î. m≤n şi n≤m. Atunci există p, q∈ℕ a.î. m+p=n şi n+q=m. Deducem că n+(p+q)=n, de unde p+q=0 (conform

Propoziţiei 2.3. ), iar de aici p=q=0 (conform Propoziţiei 2.4.), adică m=n, deci relaţia ≤ este antisimetrică .

Fie acum m, n, p∈ℕ a. î. m≤n şi n≤p. Atunci există r, s∈ℕ a. î. m+r=n şi n+s=p. Deducem imediat că m+(r+s)=p, adică m≤p, deci relaţia ≤ este şi tranzitivă, adică ≤ este o relaţie de ordine pe ℕ.

Pentru a proba că ordinea ≤ de pe ℕ este totală, fie m∈ℕ fixat iar Pm ={n∈ℕ: n≤m sau m≤n}⊆ℕ.

În mod evident 0∈Pm şi fie n∈Pm. Dacă n=m, atunci cum n<s(n) avem m<s(n), adică s(n)∈Pm . Dacă n<m, atunci conform Lemei 4.2. avem s(n)≤m şi din nou s(n)∈Pm . Dacă m<n, cum n<s(n) avem că m<s(n) şi din nou s(n)∈Pm. Rezultă că Pm=ℕ şi cum m este oarecare deducem că ordinea ≤ de pe ℕ este totală. ∎

Observaţie Relaţia de ordine ≤ definită anterior pe ℕ poartă numele de ordinea naturală de pe ℕ.

TEOREMA 4.5. Dubletul (ℕ, ≤) este o mulţime bine ordonată . Demonstraţie Trebuie să demonstrăm că orice submulţime nevidă A⊆ℕ are un cel mai mic element. Pentru aceasta fie:

P={n∈ℕ: n≤x pentru orice x∈A}⊆ℕ.

Evident 0∈P. Dacă pentru orice n∈P ar rezulta s(n)∈P, atunci am deduce că P=ℕ. Astfel că alegând un x0∈A atunci x0∈P, deci s(x0)∈P. În particular ar rezulta că s(x0 )≤x0 – absurd !.

Deducem că P≠ℕ, adică există a∈P a.î. s(a)∉P.

Vom demonstra că a∈A şi că a este cel mai mic element al lui A.

Dacă a∉A, atunci pentru orice x∈A avem a<x, de unde s(a)≤x (conform Lemei 4.2.), adică s(a)∈P – absurd !, deci a∈A şi cum a ∈P deducem că a ≤x pentru orice x∈A, adică a este cel mai mic element al lui A . ∎

COROLAR 4.6. Orice şir descrescător de numere naturale este staţionar.

Demonstraţie Fie (a n)n ∈ℕ un şir descrescător de numere naturale iar

A={a n : n∈ℕ}⊆ℕ. Conform Teoremei 4.5 mulţimea A are un cel mai mic element a k ; atunci pentru orice m≥k avem a m≥ a k şi cum a k ≤ am deducem că am = a k , adică şirul (a n ) n ∈ℕ este staţionar . ∎

COROLAR 4.7. În ℕ nu putem găsi un şir strict descrescător şi infinit de numere naturale.

COROLAR 4.8. Fie P⊆ℕ a.î. pentru orice n∈ℕ (x<n ⇒ x∈P) ⇒ n∈P. Atunci P=ℕ.

Demonstraţie Fie A=ℕ\P⊆ℕ şi să presupunem prin absurd că A≠∅. Conform Teoremei 4.5. mulţimea A va avea un cel mai mic element a∈A. Cum pentru x∈ℕ, x<a ⇒ x∉A ⇒ x∈P, conform ipotezei P=ℕ, adică a∈P şi astfel a∉A – absurd !. Deci A=∅, de unde P=ℕ . ∎

COROLAR 4. 9. ( Teorema împărţirii cu rest în ℕ). Pentru oricare două numere naturale m, n cu n≠0, există şi sunt unice două numere naturale c şi r a.î. m=n·c+r şi r<n .

Demonstraţie Fie A={s∈ℕ: există p∈ℕ a.î. m=np+s}⊆ℕ.

Deoarece m=0·m+m deducem că m∈A, adică A≠∅. Conform Teoremei 4.5. mulţimea A posedă un element minimal r∈A. Atunci există c∈ℕ a.î. m=c·n+r şi să demonstrăm că r<n .

Dacă prin absurd r≮n, atunci conform Propoziţiei 4.4., r≥n, adică există u∈ℕ a.î. r=n+u. Deducem că m=nc+r=nc+n+u=n(c+1)+u, adică u∈A, deci r≤u şi cum u≤r deducem că u=r, adică n=0 – absurd !.

Pentru a demonstra unicitatea lui c şi r să presupunem că m=cn+r=

=cʹn+rʹ, cu r, rʹ<n şi să arătăm că c=cʹ şi r=rʹ.

Să presupunem de exemplu că c<cʹ, adică c+u=cʹ cu u∈ℕ*.

Atunci m=ncʹ+rʹ=n(c+u)+rʹ=nc+nu+rʹ, deci r=nu+rʹ >n – absurd !. Deci c=cʹ şi deducem imediat că şi r=rʹ. ∎

Observaţie Numărul c poartă numele de câtul împărţirii lui m la n iar r se zice restul acestei împărţiri .

TEOREMA 4.10. Fie m, n, m′, n′, pÎℕ a.î. m£n şi m′£n′. Atunci:

i) m+m′£ n+n′ şi mm′£ nn′ ii) mp£ np şi m^p £ n^p.

Demonstraţie i) Putem scrie m+r=n şi m′+r′=n′, cu r, r′Îℕ. Din (m+m′)+(r+r′)=n+n′ deducem că m+m′£n+n′. De asemenea nn′=(m+r)(m′+r′)=mm′+mr′+r·m′+r·r′ şi cum m·r′+r·m′+r·r′Îℕ deducem că mm′£nn′.

ii) Se deduce ca şi i) ţinând cont de i) precum şi de regulile de calcul din ℕ stabilite mai înainte. ∎

§5. Reprezentarea numerelor naturale într-o bază dată

Din cele mai vechi timpuri s-a impus găsirea unor procedee de scriere a numerelor naturale care să permită o rapidă estimare a ordinului lor de mărime, precum şi elaborarea unor reguli simple de a efectua principalele operaţii cu acestea (adunarea, înmulţirea). Acestei probleme i s-au dat rezolvări specifice diferitelor etape de dezvoltare a matematicilor (adaptarea sistemului de numeraţie zecimal cu care suntem obişnuiţi azi s-a încheiat abia în secolele XVI- XVII când acesta a cunoscut o largă răspândire în Europa).

În cele ce urmează vom fundamenta ceea ce înseamnă scrierea numerelor naturale în baza u, unde uÎℕ, u³2.

LEMA 5.1. Fie u un număr natural >1. Oricare ar fi numărul natural a>0, există numerele naturale n, q0, q1,…, qn-1, a0, a1,…, an a. î.:

a=uq0+a0, 0£a₀<u q0=uq1+a1, 0£a1<u ………

qn-2=uqn-1+an-1, 0£a_n-1<u qn-1=an, 0£an<u

Demonstraţie. Dacă a<u, luăm n=0, a0=a şi lema este adevărată. Dacă a³u, fie q0, a0Îℕ astfel încât a=uq0+a0, 0£a0<u.

Cum a³u, avem q0>0. Există q1, a1Îℕ astfel încât q0=uq1+a1, 0£a1<u şi aşa mai departe.

Dacă qi¹0, atunci din 1<u rezultă q_i<uqi£uq_i+ai=qi-1, de unde:

a>q0>q1>…>qi-1>qi>…³0.

Este clar că există n astfel încât qn-1¹0 şi q_n=0. Rezultă că 0<qn-1=an<u şi lema este demonstrată. ∎

LEMA 5.2. Fie u, a0, a1,…,anÎℕ astfel încât u>1, 0£a_i<u pentru 0≤i<n şi 0<an<u. Atunci:

å

=

< + n i

n iui u a

0

1.

Demonstraţie Cum ai£u-1 pentru i=0, 1,…, n, atunci:

å å

= =

+ + - <

= -

n £

i

n i

n n

i

iui u u u u

a

0 0

1

1 1

) 1

( , de unde rezultă lema. ∎

TEOREMA 5.3. Fie u un număr natural >1. Oricare ar fi numărul a>0, există numerele naturale n, an,an-1,…,a0 unic determinate astfel încât:

a=anuⁿ + an-1u^n-1 + …+ a1u + a0, unde 0<a0<u şi 0£ai<u pentru orice 0£i£n-1.

Demonstraţie Conform Lemei 5.1., există n, q0,…, qn-1 şi a0,a1,…,an a.î.:

a=uq0+a0, 0£a₀<u q0=uq1+a1, 0£a₁<u ………

qn-2=uqn-1+an-1, 0£a_n-1<u qn-1=an, 0£a_n<u.

Înmulţim aceste egalităţi respectiv cu 1, u, u²,…,uⁿ. Adunând apoi termen cu termen egalităţile ce se obţin, rezultă:

a=anuⁿ + an-1u^n-1 + …+ a1u + a0.

Rămâne să dovedim unicitatea numerelor n, an,…,a1, a0. Fie de asemenea numerele naturale n¢,a_n¢_¢,a_n¢_¢-1,...,a₁¢,a₀¢ a.î.

0 1 1

1u ... a u a

a u a

a= _n¢_¢ ^n¢+ _n¢_¢- ^n¢- + + ¢ + ¢ cu 0<a_n¢_¢<u şi 0£a_i¢<u pentru n

i< ¢

0£ .

Dacă n<n¢, atunci n+1£n¢şi din Lema 5.2. rezultă:

å å

=

¢

=

¢

+ £ £ ¢ =

<

= ⁿ

i

n i

i i n n

iui u u au a

a a

0 0

1 , deci a<a (contradicţie).

Analog se arată că nu este posibil ca n¢<n, de unde n=n¢.

Să demonstrăm acum că a_i =a_i¢, 0£i£n. Dacă n=0, atunci a₀ =a=a₀¢. Presupunem că n>0 şi că afirmaţia este adevărată pentru n-1. Din egalităţile:

) ...

( )

...

( ¹ _{1 0} ¹ ₁

0 u a u a a u a u a

a

a= + _n ^n- + + = ¢ + _n¢_¢ ^n¢- + + ¢ , unde 0£a₀ <u şi u

a¢ <

£ ₀

0 rezultă, folosind unicitatea câtului împărţirii lui a prin u că a₀ =a₀¢ şi a_nu^n-1+...+a₂u+a₁ =a_n¢_¢u^n¢-1+...+a₂¢u+a₁¢.

Folosind ipoteza de inducţie, din ultima egalitate deducem că a_i =a_i¢, i=1,2,…,n.

Teorema este astfel complet demonstrată. ∎

Suntem acum în măsură să definim ceea ce este cunoscut sub numele de sistem de numeraţie în baza u, unde u este un număr natural >1.

La fiecare număr natural a>0 facem să corespundă secvenţa finită de numere naturale anan-1…a1a0, unde ai<u, 0£i£n, a_n¹0 şi

å

=

= ⁿ

i iui

a a

0

. Aşadar, anan-1…a1a0

def= anuⁿ +an-1u^n-1 +…+ a1u +a0.

Din Teorema 5.3. rezultă că se stabileşte astfel o corespondenţă biunivocă între numerele naturale >0 şi secvenţele finite anan-1…a1a0 de numere naturale ai<u, cu an¹0. Când se impune să atragem atenţia asupra bazei

sistemului de numeraţie, se obişnuieşte să se scrie anan-1…a1ao(u) sau anan-1…a1ao(u).

Dacă baza sistemului de numeraţie este zece (notată 10) el este numit sistemul zecimal. Cifrele sistemului de numeraţie se numesc cifre zecimale. Ele sunt numerele mai mici ca zece şi se notează în ordine cu 0, 1, 2, 3, 4, 5, 6, 7, 8, 9.

Secvenţa de cifre zecimale 75038 sau mai precis 75038(10) reprezintă, aşadar, numărul natural: 7´10⁴ + 5´10³ + 0´10² + 3´10 + 8.

Dacă u=2, atunci avem sistemul de numeraţie binar, cifrele binare fiind 0 şi 1. Astfel: 11010(2)=1´2⁴ + 1´2³ + 0´2² + 1´2 + 0 =26₍₁₀₎.

Printre sistemele de numeraţie mai des folosite se numără şi cel de bază u=16(10)=10000(2) numit sistemul de numeraţie hexazecimal, cifrele hexazecimale fiind 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, F.

Astfel, avem 27(10)=1A(16)=11011(2).

Iată o listă de probleme care se pun în mod natural în legătură cu reprezentarea numerelor într-o bază:

(I) Stabilirea raportului de mărime între două numere reprezentate în aceeaşi bază.

(II) Stabilirea unor reguli (algoritmi) de efectuare a sumei, produsului etc. a două numere reprezentate în aceeaşi bază.

(III) Elaborarea unor algoritmi pentru reprezentarea unui număr într-o bază dată.

În continuare se va arăta cum pot fi soluţionate aceste probleme pentru numere naturale. Să începem cu problema (I).

În teorema următoare se dă un criteriu foarte comod de a stabili raportul de mărime între două numere naturale reprezentate în aceeaşi bază.

TEOREMA 5.4. Fie a şi b două numere naturale, a=amam-1…a1a0(u)

şi b=bnbn-1…b1b0(u). Atunci a<b dacă şi numai dacă m<n şi ap<bp, unde p este cel mai mare i astfel încât a¹b.

Demonstraţie Dacă m<n, din Lema 5.2. rezultă a < u^m+n £ uⁿ £ b, deci a<b. Dacă m=n şi ap<bp, unde p=max{i|ai¹bi}, atunci

b-a=(bp-ap)u^p + (bp-1u^p-1 +…+b0) – (ap-1u^p-1 + …+ a0) > (bp-ap)u^p + (bp-1u^p-1 +…+

+ b0)- u^p³ u^p + (bp-1u^p-1 +…+ b0)- u^p³ 0, de unde b-a>0, deci a<b.

Reciproc, presupunem că a<b. Atunci m£n, deoarece m>n implică b<a.

Dacă m<n, nu mai avem nimic de demonstrat. Dacă m=n, fie p=max{i|a_i¹b_i}.

Avem ap<bp, întrucât ap>bp implică, conform primei părţi a demonstraţiei, b<a.

Teorema este demonstrată. ∎

Astfel pentru numerele 125302 şi 95034 date în baza zece avem 125302>95034. La fel, pentru numerele 101101 şi 100110 date în baza doi avem 101101>100110.

Referitor la problema (II) se va arăta cum se face adunarea şi înmulţirea numerelor naturale reprezentate într-o bază u. În particular, dacă u=10, se regăsesc cunoscutele procedee de adunare şi înmultire a numerelor naturale.

Fie a şi b două numere naturale, a=amam-1…a1a0(u) , b=bnbn-1…b1b0(u). Trebuie să găsim cifrele c0, c1,… ale numărului a+b în baza u. Putem scrie a=a0+a1u+a2u²+… şi b=b0+b1u+b2u²+…. Cum a0<u şi b0<u, rezultă că a0+b0<2u, deci a0+b0=ue₁+c0, 0£c₀<u, e₁=0 sau e₁=1; mai precis, avem e₁=0 şi c0=a0+b0 dacă a0+b0<u iar e₁=1 şi c0=a0+b0-u dacă u£a₀+b0<2u. Rezultă a+b=c0+(a1+b1+e1)u+(a2+b2)u²+…. Evident, a1+b1+e1<2u, de unde

a1+b1+e₁=ue₂+c1, 0£c₁<u, unde e₂=0 sau e₂=1. Avem a+b=c0+c1u+

+( a2+b2+e₂)u²+…, ş.a.m.d.

Se deduce că cifrele c0, c1, c2,… ale sumei a+b sunt ci= (ai+bi+ei) mod u, i=0, 1, 2, …, unde e₀=0, şi pentru i>0:

ei=0 Û ai-1+bi-1+ei-1<u şi atunci ci-1= ai-1+bi-1+ei-1,

e_i=1 Û a_i-1+bi-1+e_i-1³u şi atunci c_i-1= ai-1+bi-1+e_i-1-u.

Când m=n, numărul a+b are:

1) m cifre dacă an+bn+en<u,

2) m+1 cifre dacă an+bn+e_n³u, cifra de rang m+1 fiind în acest caz c_m+1=1.

Dacă m¹n, de exemplu m>n, atunci cele de mai sus rămân adevărate luând bn+1=…=bm=0.

Se observă că pentru a efectua a+b în baza u mai trebuie să cunoaştem, sau să avem posibilitatea să consultăm, tabla adunării numerelor naturale <u. De exemplu, dacă u=5, tabla adunării numerelor naturale <5, cu rezultatele exprimate în baza 5, este cea din tabelul 1. În acest tabel la intersecţia liniei numărului i cu coloana numărului j este pus i+j reprezentat în baza 5.

+ 0 1 2 3 4

0 0 1 2 3 4

1 1 2 3 4 10

2 2 3 4 10 11

3 3 4 10 11 12

4 4 10 11 12 13

Tabelul 1. Tabla adunării în baza 5 Cititorul poate singur acum să redacteze un algoritm al adunării numerelor naturale în baza u, luând ca motivaţie teoretică a acestuia consideraţiile de mai sus. Observăm că în acest algoritm apare variabila e care are valoarea iniţială e₀=0 iar valorile e_i, i ³ 1, sunt egale cu 1 când a_i-1+ bi-1+ e_i-1³ ≥ u, respectiv 0 când ai-1+bi-1+e_i-1<u. Se spune că varibila e realizează transportul unităţii de la cifrele de rang i la cele de rang i+1, i=0, 1,…. În calculul cu “creionul şi hârtia” al sumei a două numere naturale, operaţiile din algoritmul adunării în baza u se sistematizează astfel: amam-1 … a1a0 + bmbm-1 … b1b0 cm+1cmcm-1…c1c0 e_m e_m-1 … e₁e₀ ultima linie, care descrie transportul unităţii, de regulă se omite. Astfel, dacă u=2, a=1011101(2), b=101101(2), atunci a+b se face după cum urmează: 1011101+

101101

10001010

1111101

deci a+b=10001010(2). S-a folosit şi tabla adunării numerelor naturale <2, care este: + 0 1

0 0 1

1 1 10 rezultatele fiind reprezentate în baza 2.

În continuare se va arăta că înmulţirea a două numere naturale în baza u se reduce la următoarele tipuri de operaţii:

1) înmulţirea unui număr natural a cu o putere u^j a bazei u;

2) înmulţirea unui număr natural a cu o cifră a sistemului de numeraţie (deci cu un număr natural j, 0£j<u);

3) adunarea @n baza u.

Fie a=amam-1…a1a0(u) =amu^m+am-1u^m-1+…+a1u+a0.

Atunci au^j = amu^m+j + am-1u^m-1+j +…+ a1u^1+j + a0u^j = amam-1…a1a0123

j

0 ...

00 (u)

şi acum este clar cum se face în baza u o înmulţire de tipul 1).

Dacă i şi j sunt două numere naturale <u, atunci ij<u², de unde, folosind teorema împărţirii cu rest pentru numerele naturale, avem:

ij=uq(i, j)+r(i, j), 0£r(i, j)<u, 0£q(i, j)<u (*)

câtul q(i, j) şi restul r(i, j) împărţirii numărului ij prin u depinzând de i şi j.

Fie acum a un număr natural dat în baza u

å

- = =

= ^m

i i i u m

ma a a au

a a

) 0 ( 0 1 1...

şi j o cifră a sistemului de numeraţie de bază u, deci 0£j<u. Avem:

å å å å

³ ³

+

=

=

+

= +

=

=

0 0

1 0

0

, ) , ( )

, ( ))

, ( ) , ( (

i i

i i i i

m i

i i i

m i

ijui uq a j r a j u r a ju q a j u

a aj

deci efectuarea produsului aj în baza u revine la a face suma în baza u a numerelor a′ şi a′′ reprezentate în baza u:

a′= r(a0, j) + r(a1, j)u + r(a2, j)u²+ … şi a′′=q(a0, j) +q(a1, j)u²+…

Aşadar, s-a lămurit cum se face în baza u şi o înmulţire de tipul 2).

În sfârşit, dacă

å

- = =

= ⁿ

j j j u

n

nb bb b u

b b

) 0 ( 0 1

1... , atunci

å

=

= ⁿ

j juj

ab ab

0

, deci produsul ab se poate efectua făcând suma în baza u a numerelor abju^j, j=0, 1, 2, …, n. Dar abju^j = (abj)u^j. Aşadar abj este o operaţie de tipul 2) şi în sfârşit (abj)u^j e o operaţie de tipul 1).

Cititorul se poate convinge uşor că regula de înmulţire a numerelor naturale în baza zece se motivează din punct de vedere teoretic prin consideraţiile de mai sus, luând u=10. Un instrument important al înmulţirii numerelor în baza zece este tabla înmulţirii numerelor <10. Pe de altă parte, se observă că în regula de înmulţire a numerelor în baza u trebuie să cunoaştem numerele q(i, j) şi r(i, j), 0£i, j<u,din relaţia (*). Din relaţia (*) rezultă că q(i, j) şi r(i, j) sunt cifrele numărului ij, 0£i, j<u, reprezentat în baza u [dacă ij<u, avem q(i, j)=0]. Aşadar, procedeul de înmulţire expus uzează de tabla înmulţirii numerelor naturale <u, cu rezultatele reprezentate în baza u.

În tabelele 2 şi 3 sunt date tablele înmulţirii în baza u=5, respectiv u=2.

× 0 1 2 3 4 0 0 0 0 0 0 1 0 1 2 3 4 2 0 2 4 11 13 3 0 3 11 14 22 4 0 4 13 22 31

Tabelul 2: Tabla înmulţirii în baza 5 × 0 0

0 0 0 1 0 11

Tabelul 3: Tabla înmulţirii în baza 2

Pentru calculul cu “creionul şi hârtia” calculele pot fi sistematizate ca @n figura următoare:

a u q0 u a0 q1 u

a1 q2

a2

qn-2 u qn-1 u an-1 0

an

Să ne ocupăm acum da problema (III).

Trebuie observat că numărul natural a ce urmează să fie reprezentat într-o bază u este dat, de regulă, într-o bază v şi de fapt se face trecerea lui a din baza v în baza u. Se pot distinge 3 variante:

1) Trecerea lui a din baza v în baza u cu efectuarea calculelor în baza v;

2) Trecerea lui a din baza v în baza u cu efectuarea calculelor în baza u;

3)Trecerea lui a din baza v în baza u cu efectuarea calculelor într-o bază intermediară w;

Pentru a trece pe a din baza v în baza u cu metoda 1) se reprezintă mai întâi u în baza v şi apoi se aplică algoritmul sistemelor de numeraţie pentru a şi u cu efectuarea calculelor în baza v. Cum în calculatoare numerele sunt, de regulă, reprezentate în baza v=2, metoda 1) se aplică atunci când se livrează rezultatele numerice (de regulă în baza u=10), execuţia algoritmului sistemelor de numeraţie putând fi astfel încredinţată calculatorului (calculele se fac în baza v=2). Aceeaşi metodă se aplică şi când se trece cu “hârtia şi creionul” un număr din baza v=10, într-o altă bază u, preferându-se calculele în baza v=10 din motive lesne de înţeles.

Pentru exemplificare, să trecem numărul a=234 dat în baza v=10 în baza u=7. Algoritmul sistemelor de numeraţie este în acest caz:

234 7 3 33 7

5 4 7 4 0

de unde a=453(7).

Pentru a trece pe a=anan-1…a1a0(v) din baza v în baza u cu metoda 2) se reprezintă mai întâi a0, a1,…,an şi v în baza u cu ajutorul algoritmului sistemelor de numeraţie. Se introduce a0, a1, …, an şi v astfel reprezentaţi în expresia anvⁿ + an-1v^n-1 + …+ a1v + a0

şi se face calculul acesteia folosind algoritmului adunării şi algoritmul înmulţirii în baza u. Se obţine, în final, reprezentarea lui a în calculator. Numerele date de

regulă în baza u=2; efectuarea calculelor în baza u=2 poate fi încredinţată calculatorului.

Metoda 3) este evident o combinatie a primelor două. Astfel, dacă dorim să trecem un număr a dintr-o bază v¹2, într-o bază u¹2, folosind un calculator care lucrează cu numere reprezentate în baza 2, atunci trecem pe a în baza 2 cu metoda 2) şi apoi îl trecem în baza u cu metoda 1). Procedând astfel, toate calculele pot fi încredinţate calculatorului. Când v¹10 şi u¹10, iar trecerea de la baza b la baza u vrem să o facem cu “creionul şi hârtia”, preferăm baza intermediară w=10 pentru a putea executa toate calculele în baza 10, cu care suntem obişnuiţi.

Observaţii 1. Trecerea unui număr natural a din baza v în baza u se simplifică considerabil c`nd v=u^r, r număr natural >1. Metoda se justifică prin faptul că un număr natural b<u^r poate fi scris în mod unic sub forma

b=cr-1u^r-1 +…+c1u+c0, 0£ci<u, 0£i<r. (**)

De aici, rezultă că pentru a reprezenta numărul a=anan-1…a1a0(v)=

= anvⁿ + an-1v^n-1 + …+ a1v + a0 în baza u, unde v=u^r cu r >1, fiecare cifră ai se scrie ca în (**), anume ai=cir-1u^r-1+…+ci1u+ci0 şi se înlocuieşte fiecare ai cu secvenţa, cir-1…ci1ci0,deci obţinem secvenţa

cnr-1…cn1cn0cn-1,r-1…cn-1,1cn-1,0…c01c00.

Înlăturând cifrele egale cu 0 de la începutul secvenţei de mai sus se obţine repreprezentarea lui a în baza u.

Astfel, pentru a reprenta numărul a=375(8) în baza u=2 (deci v=u³), scriem mai întâi:

a0=5=1´2²+0´2+1´1=c₀₂×2²+c01×2+c₀₀ a1=7=1´2²+1´2+1´1= c12×2²+c11×2+c10, a3=3=0´2²+1´2+1´1= c₂₂×2²+c21×2+c₂₀, aşadar secvenţa de mai sus este în acest caz:

011 111 101.

2. Când v^r = u, r>1, trecerea unui număr din baza v în baza u se face printr-o metodă care urmează calea inversă a metodei de la observaţia 1. În acest caz, pentru a trece în baza u numărul a=anan-1…a1a0(v) se separă de la dreapta la stânga grupe de câte r cifre (ultima grupă având cel mult r cifre) şi fiecare grupă va reprezenta o cifră în baza u, cu care vom înlocui grupa respectivă. Se obţine astfel reprezentarea lui a în baza u.

Astfel, dacă u=8 şi v=2, deci v³=u, numărul a=11 111 101(2) are în baza 8 reprezentarea a=375(8) pentru că cifrele lui a în baza 2 pot fi grupate astfel:

11{ { {111 101

şi grupele obţinute reprezintă în baza 2 respectiv cifrele 3, 7 şi 5 ale bazei 8.

3)Inconvenientul sistemului binar de numeraţie constă în faptul că reprezentarea numerelor mari necesită secvenţe de cifre binare exagerat de lungi.

Aceasta complică mult lectura numerelor precum şi aprecierea ordinului lor de mărime. O metodă de a atenua aceste inconveniente este de a folosi sisteme de numeraţie cu baze mixte. Un exemplu este sistemul de numeraţie zecimal codat în binar, rezervându-se câte patru poziţii binare fiecărei cifre zecimale. Astfel, numărul a=793(10) se reprezintă în sistemul zecimal codat în binar după cum urmează:

{ { {

3 9 7

0011 1001 0111

În practică se foloseşte curent sistemul de numeraţie cu bază mixtă . Astfel expresia: 8 ani, 3 luni, 2 săptămâni, 15 ore şi 35 minute este un model de reprezentare a timpului într-un sistem de numeraţie cu şase baze.

Observaţie Acest paragraf a fost redactat în cea mai mare parte după lucrarea [14].

CAPITOLUL 2 :

INELUL NUMERELOR ÎNTREGI ℤ

§1 Construcţia lui ℤ

În vederea construirii mulţimii numerelor întregi ℤ, vom prezenta la început Teorema lui Malţev de scufundare a unui monoid comutativ cu proprietatea de simplificare într-un grup comutativ urmând ca prin particularizarea la cazul monoidului (ℕ, +) să obţinem grupul aditiv (ℤ, +).

TEOREMA 1.1. ( Malţev ) Fie (M, ·) un monoid comutativ cu proprietatea de simplificare. Atunci există un grup comutativ G(M) şi un morfism injectiv de monoizi iM:M→G(M) ce verifică următoarea proprietate de universalitate :

Pentru orice grup comutativ G şi orice morfism de monoizi f:M→G există un unic morfism de grupuri fʹ:G(M)→G a.î. diagrama

i M

M G(M) f fʹ

G

este comutativă (adică fʹ∘iM =f ).

Demonstraţie Pe mulţimea Mʹ=M×M definim relaţia (x, y)∼(xʹ, yʹ) ñ

=

á^def xyʹ=yxʹ şi să probăm că ∼ este o echivalenţă pe Mʹ compatibilă cu structura de monoid a lui Mʹ (adică ∼ este o congruenţă pe monoidul produs

Mʹ=M×M ). În mod evident, relaţia ∼ este reflexivă şi simetrică. Dacă (x, y)∼(xʹ, yʹ) şi (xʹ, yʹ)∼(xʹʹ, yʹʹ) atunci xyʹ=yxʹ şi xʹyʹʹ=xʹʹyʹ, de unde

xxʹyʹyʹʹ=xʹxʹʹyyʹ, deci xyʹʹ= yxʹʹ (am simplificat prin xʹyʹ), adică (x, y)∼(xʹʹ, yʹʹ), deci relaţia ∼ este şi tranzitivă, de unde concluzia că ∼ este o

echivalenţă pe Mʹ .

Fie acum (x, y), (xʹ, yʹ), (a, b), (aʹ, bʹ)∈Mʹ a.î. (x, y)∼(a, b) şi (xʹ, yʹ)∼(aʹ, bʹ) şi să probăm că şi (xxʹ, yyʹ)∼(aaʹ, bbʹ ).

Avem deci xb=ya şi xʹbʹ=yʹaʹ, de unde xxʹbbʹ=yyʹaaʹ, adică (xxʹ, yyʹ)∼(aaʹ, bbʹ), adică relaţia ∼ este o congruenţă pe monoidul produs Mʹ

în care reamintim că operaţia de compunere se defineşte prin (x, y)·(xʹ, yʹ)=

=(xxʹ,yyʹ). Vom considera monoidul cât G(M)=Mʹ/∼ iar pentru (x, y)∈Mʹ vom nota prin [x, y] clasa sa de echivalenţă în G(M).

Datorită faptului că relaţia ∼ este o congruenţă pe Mʹ deducem imediat că G(M) devine în mod canonic monoid comutativ, definind pentru [x, y], [xʹ, yʹ]∈G(M), [x, y]·[xʹ, yʹ]=[xxʹ, yyʹ] (elementul neutru al lui G(M) va fi [e, e], e fiind elementul neutru al lui M). Deoarece pentru [x, y]∈G(M), [x, y]·[y, x]=[xy, xy]=[e, e] deducem că [y, x]=[x, y] ^{– 1} , adică G(M) este grup (comutativ).

Definim iM:M→G(M) prin iM (x)=[x, e] pentru orice x∈M. Pentru x, y∈M avem iM (x)·iM (y)=[x, e]·[y, e]=[xy, e]=iM (xy) adică i M este morfism de monoizi. Dacă iM (x)=iM (y), atunci [x, e]=[y, e] ⇔ xe=ye ⇔ x=y, adică iM este chiar morfism injectiv de monoizi .

Să arătăm acum că dubletul (G(M), iM) verifică proprietatea de universalitate din enunţ. Pentru aceasta fie G un grup comutativ oarecare şi f: M→G un morfism de monoizi. Pentru [x, y]∈G(M), definim fʹ([x, y])=

=f(x)∘(f(y))^–1. Observăm că dacă [x, y]=[xʹ, yʹ], atunci xyʹ=xʹy, deci f(x)∘f(yʹ)=f(xʹ)∘f(y) ⇔ f(x)∘(f(y))^–1=f(xʹ)∘(f(yʹ))^-1, adică fʹ este corect

definită.

Să probăm acum că fʹ este morfism de grupuri.

Avem fʹ([x, y]·[xʹ, yʹ])=fʹ([xxʹ, yyʹ])=f (xxʹ)[ f(yyʹ)]^-1=

=f(x)f(xʹ)[f(y)·f(yʹ)]^-1=(f(x)[f(y)]^–1)( f(xʹ)[f(yʹ)]^-1)=fʹ([x, y])fʹ([xʹ, yʹ]). Pentru x∈M avem (fʹ∘iM)(x)=fʹ(iM (x))= fʹ([x, e])=f(x)[f(e)]^-1=f(x), de unde concluzia că fʹ∘iM=f .

Pentru a proba unicitatea lui fʹ (cu proprietatea din enunţ) să presupunem că mai există un morfism de grupuri fʹʹ:G(M)→G a.î. fʹʹ∘iM=f.

Atunci, pentru [x, y]∈G(M) avem [x, y]=[x, e]·[e, y]=[x, e]·[y, e]^-1, de unde fʹʹ([x, y])=fʹʹ([x, e]·[y, e]^–1)=fʹʹ(iM (x)∘(iM(y)^-1))=fʹʹ(iM (x))∘(fʹʹ(iM (y)))^-1=

=f(x)∘(f(y))^–1=fʹ([x, y]), adică fʹʹ=fʹ. ∎ Observaţii

1. Dacă f este un morfism injectiv de grupuri , atunci şi fʹ este morfism injectiv de grupuri .

Într-adevăr, dacă [x, y]∈G(M) şi fʹ([x, y])=e, atunci f(x)(f(y))^–1 =e, deci f(x)=f(y), de unde x=y, adică [x, y]=[x, x]=e.

2. Dacă pe mulţimea dubletelor (G, f) cu G grup abelian şi f:M→G morfism injectiv de monoizi definim relaţia (G, f )≤(Gʹ, fʹ)⇔există h:G→Gʹ a.î.

h este morfism injectiv de grupuri şi h∘f=fʹ, atunci se verifică imediat că relaţia de mai sus este o relaţie de ordine iar dubletul (G(M), iM ) din Teorema lui Malţev este cel mai mic element faţă de această relaţie de ordine.

DEFINIŢIA 1.2. Considerăm monoidul (ℕ, +) (ce are proprietatea de simplificare conform Propoziţiei 2.3. de la Capitolul 1) şi urmând tehnica dată de Teorema lui Malţev, mulţimea subiacentă grupului aditiv (G(ℕ), +) se notează prin ℤ şi poartă numele de mulţimea numerelor întregi .

Ţinând cont de faptul că i_ℕ:ℕ→ℤ , i_ℕ(n)=[n, 0] pentru orice n∈ℕ este morfism injectiv de monoizi, vom identifica fiecare număr natural n∈ℕ prin elementul întreg [n, 0] astfel că ℕ va fi privită în continuare ca submulţime a lui ℤ.

Fie acum z=[m, n]∈ℤ. Dacă m=n, atunci z=0. Dacă m<n, atunci există p∈ℕ* a.î. m+p=n (în acest caz convenim să notăm p=n-m şi astfel m+(n-m)=n) iar z=[0, p]=-[p, 0] se identifică cu numărul întreg –p iar dacă

n<m, atunci există q∈ℕ* a.î. n+q=m şi astfel z=[q, 0] identificându-se cu numărul natural q.

Ţinând cont de acestea putem scrie pe ℤ sub forma ℤ=(-ℕ*)∪ℕ unde -ℕ*={-n|n∈ℕ*} sau ℤ={0 , ±1 , ±2 , ….}. Vom nota ℤ* = ℤ \ {0}.

§2 Înmulţirea numerelor întregi

LEMA 2.1. Fie x, y, z, t, xʹ, yʹ, zʹ, tʹ∈ℕ a.î. [x, y]=[xʹ, yʹ] şi [z, t]=[zʹ, tʹ]. Atunci [xz+yt, xt+yz]=[xʹzʹ+yʹtʹ, xʹtʹ+yʹzʹ] .

Demonstraţie Din ipoteză avem x+yʹ=y+xʹ şi z+tʹ=zʹ+t astfel că [xz+yt, xt+yz]=[xʹzʹ+yʹtʹ, xʹtʹ+yʹzʹ]⇔

(xz+yt)+(xʹtʹ+yʹzʹ)=(xt+yz)+(xʹzʹ+yʹtʹ)⇔

x(z-t)+y(t-z)=xʹ(zʹ-tʹ)+yʹ(tʹ-zʹ)⇔(x-y)(z-t)=(xʹ-yʹ)(zʹ-tʹ) ceea ce este adevărat deoarece x-y=xʹ-yʹ şi z-t=zʹ-tʹ. ∎

Fie acum α=[x, y] şi β=[z, t] două numere întregi.

Definind α·β=[xz+yt, xt+yz], conform Lemei 2.1. deducem că această definiţie este corectă .

PROPOZIŢIA 2.2. (ℤ, +, · ) este domeniu de integritate.

Demonstraţie Conform celor de mai înainte (ℤ, +) este grup comutativ. Să demonstrăm acum că (ℤ, ·) este monoid comutativ iar pentru aceasta fie α=[x, y], αʹ=[xʹ, yʹ], αʹʹ=[xʹʹ, yʹʹ] trei elemente oarecare din ℤ.

Atunci :

α(αʹαʹʹ)=[x,y][xʹxʹʹ+yʹyʹʹ,xʹyʹʹ+yʹxʹʹ]

=[x(xʹxʹʹ+yʹyʹʹ)+y(xʹyʹʹ+yʹxʹʹ), x(xʹyʹʹ+yʹxʹʹ)+y(xʹxʹʹ+yʹyʹʹ)]

=[xxʹxʹʹ+xyʹyʹʹ+xʹyyʹʹ+xʹʹyyʹ, xxʹyʹʹ+xxʹʹyʹ+xʹxʹʹy+yyʹyʹʹ] iar (ααʹ)αʹʹ=[xxʹ+yyʹ, xyʹ+xʹy][xʹʹ, yʹʹ]

=[(xxʹ+yyʹ)xʹʹ+(xyʹ+xʹy)yʹʹ, (xxʹ+yyʹ)yʹʹ+(xyʹ+xʹy)xʹʹ]

=[xxʹxʹʹ+xyʹyʹʹ+xʹyyʹʹ+xʹʹyyʹ, xxʹyʹʹ+xxʹʹyʹ+xʹxʹʹy+yyʹyʹʹ] ,

de unde deducem că α(αʹαʹʹ)=(ααʹ)αʹʹ adică înmulţirea numerelor întregi este asociativă.

În mod evident, ααʹ=αʹα (deoarece înmulţirea numerelor naturale este comutativă ), adică înmulţirea numerelor întregi este comutativă.

Deoarece α[1, 0]=[x, y][1, 0]=[x, y]=α, deducem că elementul neutru pentru înmulţirea numerelor întregi este [1, 0].

Să arătăm acum că înmulţirea numerelor întregi este distributivă faţă de adunarea numerelor întregi .

Într – adevăr,

α(αʹ+αʹʹ)=[x, y][xʹ+xʹʹ , yʹ+yʹʹ]

=[x (xʹ+xʹʹ)+y(yʹ+yʹʹ), x(yʹ+yʹʹ)+y (xʹ+xʹʹ)]

=[xxʹ+xxʹʹ+yyʹ+yyʹʹ, xyʹ+xyʹʹ+yxʹ+yxʹʹ] iar ααʹ+ααʹʹ=[x, y][xʹ,yʹ]+[x, y] [xʹʹ, yʹʹ]

=[xxʹ+yyʹ, xyʹ+yxʹ]+[xxʹʹ+yyʹʹ, xyʹʹ+yxʹʹ]

=[xxʹ+yyʹ+xxʹʹ+yyʹʹ, xyʹ+yxʹ+xyʹʹ+yxʹʹ] de unde se observă că α(αʹ+αʹʹ)=ααʹ+ααʹʹ .

Am probat până acum că (ℤ, +, · ) este un inel comutativ unitar. Pentru a arăta că inelul ℤ nu are divizori ai lui zero, fie ααʹ=0=[0, 0] cu α≠0. Atunci xxʹ+yyʹ=xyʹ+xʹy, de unde (x-y)(xʹ-yʹ)=0. Cum α≠0 (adică x-y≠0) rezută că (xʹ-yʹ)=0 ⇔xʹ=yʹ⇔ αʹ=0. ∎

§3 Relaţia de ordine naturală de pe ℤ.

DEFINIŢIA 3.1. Pentru x, y∈ℤ definim relaţia x≤y prin x≤y ⇔ y-x∈ℕ.

TEOREMA 3.2. Dubletul (ℤ, ≤) este mulţime total ordonată.

Demonstraţie Fie x, y, z∈ℤ ; deoarece x-x=0∈ℕ deducem că x≤x.

Dacă x≤y şi y≤x atunci există m, n∈ℕ a.î. y-x=m şi x-y=n, de unde m+n=0 şi deci m=n=0, adică x=y.

Dacă x≤y şi y≤z, atunci există m, n∈ℕ a.î. x+m=y şi y+n=z. Cum x+(m+n)=z deducem că x≤z, adică ( ℤ, ≤ ) este o mulţime ordonată. Faptul că

ordonarea de pe ℤ este totală rezultă din aceea că ℤ=(-ℕ*)∪ℕ iar (-ℕ*)∩ ℕ=∅. ∎

Observaţie Din felul în care am definit relaţia de ordine ≤ pe ℤ deducem că ℕ={x∈ℤ : x≥0} iar -ℕ={x∈ℤ : x ≤0}.

PROPOZIŢIA 3.3. Fie x, y, z∈ℤ a.î. x≤y .

Atunci i ) -y≤-x

ii ) dacă z≥0 atunci xz≤yz iii ) dacă z≤0 atunci xz≥yz .

Demonstraţie

i ) Din x≤y deducem că y-x∈ℕ şi cum (–x)–(-y)=y-x∈ℕ rezultă că –y ≤- x.

ii ) Cum y-x∈ℕ şi z∈ℕ avem (y-x)z∈ℕ adică yz-xz∈ℕ, deci xz≤yz .

iii ) Cum –z∈ℕ şi y-x∈ℕ deducem că şi (y-x)(-z)∈ℕ iar cum (y-x)(-z)=xz-yz∈ℕ rezultă că xz≥yz. ∎

CAPITOLUL 3:

CORPUL NUMERELOR RAŢIONALE ℚ.

§1 Construcţia corpului ℚ al numerelor raţionale

Şi în cazul construcţiei corpului ℚ al numerelor raţionale vom adopta tehnica folosită în cazul construcţiei inelului ℤ al numerelor întregi. (în sensul că vom prezenta chestiunea într-un context mai general, urmând ca printr-o particularizare la cazul domeniului de integritate (ℤ, +, ·) să obţinem corpul ℚ).

Fie (A, +, ·) un domeniu de integritate (adică un inel unitar şi comutativ fără divizori ai lui zero) .

DEFINIŢIA 1.1. Numim sistem multiplicativ în A, orice submulţime S⊆A a.î. 0∉S, 1∈S, iar dacă x, y∈S atunci şi x·y∈S.

Exemple

1. S=A*=A\{0} este un sistem multiplicativ al lui A.

2. Dacă ℘⊂A este un ideal prim, atunci S℘=A\℘ este de asemenea un sistem multiplicativ al lui A.

3. Dacă a∈A, a≠0, 1, atunci Sa={a ^k : k∈ℤ} este un sistem multiplicativ al lui A.

Pentru un sistem multiplicativ S⊆A să considerăm mulţimea

A×S={(a, s)|a∈A, s∈S} iar pe aceasta relaţia binară definită prin (a,s)∼(aʹ,sʹ)

def= asʹ=aʹs. Analog ca în cazul Teoremei lui Malţev se demonstrează facil că ∼ este o echivalenţă pe A×S.