Elemente de Aritmetica In Matemaica Preuniversitara

Elemente de aritmetica in matemaica preuniversitara

CAPITOLUL I

ELEMENTE DE ARITMETICĂ

Divizibilitate pe ℕ

Definiția 1.1.1 Fie a, bℕ, b0.Spunem că b divide a și vom nota ba dacă există cℕ astfel încât a=bc. Spunem ca b este un divizor al lui a , iar a este un multiplu al lui b.

De exemplu 530 ,deoarece există numărul natural 6 astfel încât 30=56.

In mod evident , relația de divizibilitate pe mulțimea numerelor naturale este reflexivă, antisimertică și tranzitivă , adică ( ℕ, ) este o mulțime parțial ordonată în care 1 este cel mai mic element (element inițial) iar 0 este cel mai mare element (numit element final).

Definiția 1.1.2 Un număr mℕ m2 se numește număr prim dacă singurii săi

divizori sunt 1 și m.

Cele mai mici numere prime sunt 2, 3, 5, 7, 11,13,17,19,23,29, 31,37,41,43,47, etc.

Observația 1.1.1 Singurul număr prim par este 2.

Teorema 1.1.1 Fiind date două numere a, bℕ, există dℕ (vom nota d=(a,b)) astfel încât d|a, d|b, iar dacă mai avem ℕ astfel încât | a și | b, atunci | d (adică în mulțimea parțial ordonată (ℕ, |) pentru orice două elemente a și b există (a, b) ).

Demonstrație. Conform teoremei împărțirii cu rest, putem scrie

a=bc1+r1, cu c1, r1 ℕiar 0 r1< b.

Dacă r1=0 atunci b|a și în mod evident d=(a, b)=b.

Dacă r1atunci conform aceleiași teoreme de împărțire cu rest putem scrie

b=r1 c2+r2 ,cu c2, r2 ℕiar 0 r2< r1.

Dacă r2=0, atunci d= r1. Într-adevăr, din b=r1 c2 deducem că d|b, iar din a=bc1+r1 deducem că d|a . Dacă mai avemℕ astfel încât | ași | b atunci cum r1=a-bc1, deducem că

| r1 =d.

Dacă r2atunci din nou putem scrie r1=r2 c3+r3, cu0 r3< r2, și

algoritmul descris până acum continuă, obținându-se un șir descrescător de

numere naturale : r1, r2, … astfel încât rm-2 = rm-1 cm (m 3). Folosind faptul că orice șir descrescător de numere naturale este staționar, șirul r1, r2, r3,… este staționar.

Astfel, dacă pentru un anumit p, rp+1=0, atunci d=r p, pe când, dacă rp+1=1 atunci d=1.

De exemplu : Dacă a=48 și b=30 avem :

48=1·30+18 (c 1=1, r1=18)

30=1·18+ 12 (c 2=1, r2= 12 )

18=1·12+6 (c 3=1, r3=6 )

12=2·6 (c 4=2, r4=0 )

Deoarece ultimul rest nenul este 6, deducem că (48, 30)=6.

Dacă a=90 și b=49 avem:

90=1·49+41 (c 1=1, r1=41)

49=1·41+ 8 (c 2=1, r2= 8)

41=5·8+1 (c 3=5, r3=1 )

Deoarece ultimul rest nenul este 1 ,deducem că cele două numere sunt prime între ele (90, 49)=1.

Observația 1.1.2 Dacă cel mai mare divizor comun a două numere naturale este 1, vom spune că cele două numere sunt prime între ele.

De exemplu 21 și 8 deoarece (21,8)=1.

Observația 1.1.3 Algoritmul de găsire a celui mai mare divizor comun a două numere

naturale descris mai înainte poartă numele de algoritmul lui Euclid .

Observația 1.1.4 Inductiv se arată că pentru oricare p numere naturale a1 , a2 , …,ap (p2) există d ℕ astfel încât d|aj pentru orice 1 j< p și dacă mai avemℕ astfel încât

| aj pentru orice 1 j< p, atunci |d . Numărul d se notează prin d=(a1 , a2 , …,ap ) și poartă

numele de cel mai mare divizor comun al numerelor a1 , a2 , …,ap .

Exemplu (15,30,75)=15.

Divizibilitate pe ℤ

Definiția 1.2.1 Dacă a, bℤ, b0 , vom spune că b divide a (vom scrie b|a ) dacă există cℤ astfel încât a=bc ( ca și în cazul lui ℕ nu vom defini, nici în cazul lui ℤ divizibilitatea prin 0).

Evident, dacă aℤ atunci 1|a, -1|a și a|0.

Numerele prime în ℤ se definesc ca fiind acele numere întregi m cu

proprietatea că m -1, 0, 1, iar singurii divizori ai lui m sunt mEvident,

numerele prime din ℤ sunt numerele de forma mcu m2 număr prim în ℕ

Se verifică imediat că dacă a, b, cℤ, atunci :

1) a|a (a0)

2) Dacă a|b și b|a, atunci a=±b (deci în ℤ relația de divizibilitate nu mai

este antisimetrică).

3) Dacă a|b și b|c, atunci a|c.

Teorema 1.2.1( Teorema împărțirii cu rest în ℤ ) Dacă d, îℤ î>0, atunci există c, rℤ astfel încât d=îc+r, cu 0 r< î.

Demonstratie. Fie P={d-xî / xℤ}; evident în P avem și numere naturale. Fie r=d-cî cel mai mic număr natural din P (cu cℤ). (un astfel de număr există deoarece dubletul (ℕ, ≤) este o mulțime bine ordonată). Avem 0≤r<î căci dacă r=d-cî≥î atunci 0≤d-(c+1)î<r, ceea ce contrazice minimalitatea lui r.

Observația 1.2.1 Putem formula teorema împărțirii cu rest din ℤ și sub forma : Dacă d, î ℤ,î , atunci există c, rℤ astfel încât d=ci+r, iar 0≤r<|î|.

Observația 1.2.2 Numerele c și r cu proprietatea de mai sus poartă numele de câtul,

respectiv restul împărțirii lui d la î, și sunt unice cu proprietatea respectivă, căci dacă am mai avea și ℤ astfel încât d=î+,cu 0≤ <|î|, atunci cî+r=î+ implică

(c-)î =-r, adică î|-r. Cum 0≤r, rʹ <|î|, dacă am presupune, de exemplu, că rʹ > r, atunci rʹ-r <  îiar condiția î rʹ-r implică rʹ-r = 0 rʹ = r și cum (c-cʹ)î=rʹ-r=0, deducem imediat că c=cʹ.

Definiția 1.2.2 Numim ideal al inelului (ℤ, +, ·) orice submulțime nevidă a ℤ astfel încât

a) Dacă x, y a, atunci x-y a

b) Dacă x a, și bℤ, atunci bx a .

Propoziția 1.2.1 . Fie a ℤ un ideal. Atunci există dℕ astfel încât a=dℤ.

Demonstrație. Dacă a={0}, atunci d=0. Să presupunem că a{0}. Atunci

există x a, x0. Dacă x>0, atunci x∈ℕ*, iar dacă x<0, cum a este un ideal, -x a ,

și atunci -xℕ*.

Deci, în concluzie a ℕ*Putem alege d∈ a ℕ* ca fiind cel mai mic element din a ℕ* și să demonstrăm ca a=dℤ. Cum d a și a este ideal al inelului ℤ, incluziunea dℤa este imediată. Fie acum a a , iar conform Teoremei împărțirii cu rest putem scrie a=cd+r, cu c, r∈ℤ și 0≤r<d, pentru că d∈ℕ*.

Scriind r=a-cd cum a, d a , deducem că r∈a. Datorită minimalității lui d deducem că r=0 și astfel a=cd∈dℤ, de unde și incluziunea inversă a  dℤcare ne asigură egalitatea a =dℤ.

Propoziția 1.2.2 Fie a1, a2 , …,an ∈ℤ. Dacă notăm prin < a1, a2 , …,an > idealul generat de { a1, a2 , …,an }, atunci < a1, a2 , …,an >= { k1a1+k2 a2 +…..+kn an ki∈ℤ , 1≤i≤n}.

Demonstrație. Dacă facem notația a={ k1a1+k2 a2 +…..+kn an ki∈ℤ , 1≤i≤n}, putem arăta imediat că a este ideal al lui ℤ ce conține elementele { a1, a2 , …,an }. Dar cum

< a1, a2 , …,an > este cel mai mic ideal al lui ℤ ce include { a1, a2 , …,an }, deducem că

< a1, a2 , …,an >a.

Pentru incluziunea inversă ținem cont că < a1, a2 , …,an >b

b ℤ ideal,

{ a1, a2 , …,an } b

și fie atunci b ℤ un ideal astfel încât { a1, a2 , …,an }∈ b . Atunci pentru orice numere

k1,k2 , …..,kn∈ ℤ deducem că k1a1+k2 a2 +…..+kn an ∈ b, adică a  b și cum b este oarecare,

deducem că a b=< a1, a2 , …,an >, de unde rezultă egalitatea dorită.

Definiția 1.2.3Fiind date numerele a1, a2 , …,an intregi prin cel mai mare divizor comun al lor înțelegem acel număr d∈ℤ astfel încât d|ai pentru orice 1≤i≤n și în plus dacă mai avem

dʹ ai pentru orice 1≤i≤n , atunci dʹ|d.

Observația 1.2.3 Evident, dacă un astfel de d există, atunci și –d are aceeași proprietate .

Observația 1.2.4 Convenim să alegem pentru rolul de cel mai mare divizor comun al numerelor întregi a1, a2 , …,an acel număr natural d cu proprietățile de mai înainte și vom

nota d=( a1, a2 , …,an).

Teorema 1.2.2 Fiind date n numere întregi a1, a2 , …,an cu an 2, dacă notăm prin d numărul natural a cărui existență este asigurată de Propoziția 1.2.1 pentru idealul a = < a1, a2 , …,an >, atunci d=( a1, a2 , …,an ).

Demonstrație. Într-adevăr, cum fiecare ai a1, a2 , …,an >=dℤ deducem că ai dℤ, adică d|ai

pentru orice 1≤i≤n.

Fie acum dʹℤ astfel încât dʹ|ai pentru1≤i≤n, iar cum ddℤ, există k1,k2 , …..,knℤ astfel încât și astfel deducem că |d, adică d=( a1, a2 , …,an ).

Teorema fundamentală a aritmeticii

Fie a ∈ℤ* și p∈ℕ cu p2, un număr prim. În mod evident, există k∈ℕ astfel încât

pk ași pk+1 ł a (altfel zis k este cel mai mare număr natural cu proprietatea pk a). Convenim să notăm k=op(a) și să-l numim ordinul sau exponentul lui p în a. Dacă a=0 vom lua op(0)=-∞ iar op(a)=0 dacă și numai dacă p ł a.

Propoziția 1.3.1 Orice număr natural nenul se scrie ca un produs de numere naturale prime.

Demonstrație. Fie M mulțimea numerelor naturale nenule ce nu se scriu ca produs de numere naturale prime. Dacă prin absurd propoziția nu ar fi adevărată, atunci M .

În aceste condiții mulțimea M va conține un element minimal x. În particular, x >1 și cum x nu este prim putem scrie x=m·n cu 1<m, n<x. Cum m, n<x, iar x=inf(M), deducem că m, n nu sunt elemente ale mulțimii M, deci m și n se scriu ca produse de numere prime. Atunci și x=m·n se scrie ca produs de numere prime-absurd . Deci M= și cu aceasta propoziția este demonstrată.

Corolar 1.3.1 . Pentru orice n∈ℤ* există numerele întregi prime p1,…,pm astfel încât

n=∈ℕ.

Putem folosi notația , unde , după cum n este pozitiv sau negativ, iar exponenții sunt numere naturale nenule numai pentru un număr finit de p-uri.

Corolar 1.3.2 Fiind date n numere întregi a1, a2 , …,an , n, d=( a1, a2 , …,an ) dacă și numai dacă există k1,k2 , …..,knℤ astfel încât d= k1a1+k2 a2 +…..+kn an.

Lema 1.3.1 Dacă a, b, cℤ astfel încât (a, b)=1 și a|bc, atunci a|c.

Demonstrație. Într-adevăr, cum (a, b)=1 conform Corolarului anterior există p, mℤ a.î. pa+mb=1, de unde c=pac+mbc. Cum a|bc deducem că a|pac+mbc=c, adică a|c .

Observația 1.3.1 Dacă (a, b), atunci lema de mai înainte nu mai este adevărată tot timpul căci, de exemplu, 12|4·9=36, dar 12ł4 și 12ł9.

Corolar 1.3.3 Dacă p, a, b∈ℤ astfel încât p este prim și p|ab, atunci p|a sau p|b.

Demonstrație. Într-adevăr, singurii divizori ai lui p în ℤ sunt p

Atunci (p,b)=1 sau p|b. Dacă p|b totul este în regulă, iar dacă (p, b)=1, atunci se aplică Lema enunțată anterior.

Observația 1.3.2 Putem utiliza corolarul de mai înainte și sub forma : dacă p, a, b∈ℤ astfel încât p este prim iar p ł a, p ł b, atunci p ł ab.

Corolar 1.3.4 Presupunem că p, a, b∈ℤ iar p este prim. Atunci op(ab)=op(a)+op(b).

Demonstrație. Dacă p(a), p(b), atunci a=pα c și b=pβ d, cu p ł c și p ł d. Atunci

ab=pα+β cd și cum p∤cd , deducem că op (ab)=α+β=op (a)+op (b).

Teorema 1.3.1 . Teorema fundamentală a aritmeticii

Pentru orice număr întreg nenul n, există o descompunere a lui în factori primi

cu exponenții e(p) în mod unic determinați de n (de fapt e(p)=op(n)).

Demonstrație. Scrierea lui n sub forma din enunț rezultă din Corolarul 1.3.1. Să probăm acum unicitatea acestei scrieri . Aplicând pentru un prim q, oq în ambii membrii ai egalității obținem : oq (n)= (n)oq(-1)+  oq (p) .

Însă oq(-1)=0 iar oq (p)= de unde deducem că op(n) și astfel această teoremă este demonstrată.

Corolar 1.3.5 Pentru orice n∈ℕ* există și sunt unice numerele prime distincte

p1,p2 , …..,pn și numerele naturale k1,k2 , …..,kn astfel încât n= în aceste condiții spunem că această scriere a lui n este descompunerea lui n în factori primi.

Corolar 1.3.6 Fie a, b, c, n∈ℕ* astfel încât (a,b)=1 și ab=cn. Atunci există x, y ∈ℕ* astfel încât a=xn și b=yn.

Demonstrație. Fie a= si b= descompunerea numerelor a și b în factori primi (deci kiși lj pentru i=1, 2,…,s și j=1, 2,…,t). Din (a,b)=1 deducem că {p1,…,ps}{q1,…,qt}=. Obținem deci că cn  , egalitate ce dă descompunerea lui cn în factori primi. Însă, conform Teoremei anterioare, descompunerea unui număr natural în produs de puteri de numere prime distincte este unică . Astfel, dacă

c  atunci cn de unde deducem că nni=ki și nmj=lj , 1≤i≤s, 1≤j≤t.

În aceste condiții putem considera x=și y=

Teorema 1.3.2(Legendre) Dacă n∈ℕ iar p este un număr prim, atunci exponentul lui p în n ! este dat de.

Demonstrație. În mod evident exponentul ep al lui p în n! este dat de ep1 k1 2 k 2 …. , unde k1 este numărul numerelor luate dintre 1, 2, …, n care se divid cu p dar nu cu p2, k2 este numărul numerelor luate dintre 1, 2, …, n care se divid cu p2 dar nu cu p3, etc

Să calculăm acum un ki . Numerele ce se divid prin pi dintre 1, 2, …, n sunt 1·pi, 2·pi, …, ti·pi, cu ti·pi ≤n< (ti+1)·pi , deoarece dacă j este luat dintre 1, 2,..,n și pi|j avem j=t·pi și cum 1≤j≤n avem 1≤t·pi ≤n. Dar titi1 , deci ti=.

Numerele dintre 1, 2, …, n care se divid cu pi+1 se află toate printre numerele dintre 1, 2, …, n care se divid cu pi.

Dacă din numerele luate dintre 1, 2, …, n care se divid cu pi (ce sunt în număr de ti) extragem toate numerele 1, 2,…,n care se divid cu pi+1 (ce sunt în număr de ti+1=) obținem numai numerele dintre 1, 2,…,n care se divid cu pi dar nu se divid cu o putere mai mare a lui p (deoarece nu se divid cu pi+1).

Conform celor de mai sus numărul acestora este egal cu ki=ti-ti+1.

Avem deci ep1 t1 t 2 2 t 2t 3…. t1 t 2 …. …. această sumă este finită deoarece va exista un k∈ℕ* astfel încât pk≤n<pk+1 și atunci =0 pentru orice s≥k+1).

Observația 1.3.3 Dacă p>n atunci ep=0.

Congruențe pe ℤ

Definiția 1.4.1 Fie n∈ℕ, n≥2 un număr fixat. Vom spune că a, b∈ℤ sunt congruente modulo n dacă n|a-b ; în acest caz scriem ab(mod n).

Propoziția 1.4.1 . Relația de congruență modulo n este o echivalență pe ℤ compatibilă cu operațiile de adunare și înmulțire de pe ℤ adică este o congruență pe inelul (ℤ, +, ·).

Demonstrație. Faptul că relația de congruentă modulo n este o relație de echivalență pe ℤ se probează imediat. Pentru a proba compatibilitatea acesteia cu operațiile de adunare și înmulțire de pe ℤ, fie a, b, a', b'∈ℤ a.î. ab(mod n) și a' b'(mod n), adică a-b=kn și a'- b'=k' n, cu k, k' ∈ℤ. Atunci a+ a'-(b+ b')=(k+k')n, adică a+a' b+b'(mod n) și scriind

aa' -bb'=a(a'-b')+b'(a-b)=ak'n+b'kn=(ak'+b'k)n deducem că și aa' bb'(mod n).

Corolar 1.4.1 Fie ai, bi ∈ℤ astfel încât . aibi(mod n) pentru orice i=1,2,3,…,k.

Atunci : și .In particular dacă a,b∈ℤ astfel încât ab(mod n) și k∈ℕ*, atunci akbk(mod n).

Pentru x ∈ℤ vom nota prin clasa de echivalență a lui x modulo n. Deoarece resturile împărțirii unui număr oarecare din ℤ prin n sunt 0, 1,…,n-1, se deduce imediat că dacă notăm mulțimea claselor de echivalență modulo n prin ℤn, atunci ℤn=, iar pentru k∈{0, 1,…,n-1} avem ={k+nt t∈ℤ}. Pe mulțimea ℤn, se definesc operațiile de adunare și înmulțire astfel: și , fiind bine definite conform propoziției anterioare.

Propoziția 1.4.2 . (ℤn , +, ·) este inel comutativ în care unitățile sale sunt

U(ℤn , +, ·)={ ∈ ℤn | (x, n)=1}

Demonstrație. Cum verificarea anumitor axiome nu ridică probleme deosebite, vom reaminti doar că elementul neutru din ℤn față de adunare este , – iar elementul neutru față de înmulțire este . Dacă ∈ U(ℤn) atunci există astfel încât 

=n xy-1, de unde deducem că (x, n)=1.

Reciproc, dacă x∈ {0,1,…,n-1} și (x, n)=1, atunci, există r, s∈ℤ astfel încât r·n+s·x=1, de unde deducem că    , deci ∈ U(ℤn).

Corolar 1.4.2 (ℤn , +, ·) este corp n este prim.

Observația 1.4.1 Dacă în inelul ℤ considerăm idealul =nℤ, urmărind tehnica factorizării unui inel (comutativ ) printr-un ideal, dacă am fi construit inelul factor ℤ/nℤ se obținea de fapt tot ℤn.

Fie acum a, b∈ℕ*, n∈ℤ, n 2 și d=(a, n).

Propoziția 1.4.3 Ecuația =are soluție în ℤn dacă și numai dacă d|b ; dacă d|b atunci ecuația are exact d soluții în ℤn .

Demonstrație. Dacă x0∈ ℤneste o soluție a ecuației =, atunci n|ax0-b, de unde deducem că d|b (căci d|n și d|a).

Reciproc, să presupunem că d|b. Cum d=(a, n),atunci există ∈ℤ astfel încât

d=ax0'-ny0'. Dacă c=, atunci -n=b, adică =, deci este o soluție a ecuației=.

Să presupunem acum că 0 și 1 sunt două soluții ale ecuației= . Atunci n|ax0-b și n|ax1-b, de unde n|a(x1-x0). Dacă notăm și atunci =1 și obținem 1-x0, adică x1=x0+kn', cu k∈ℤ.

Pe de altă parte se verifică imediat că este soluție a ecuației = cu

k∈{0, 1,…,d-1}. Cum nu e posibil să avem pentru pentru

k, k′1,…,d-1} și k≠k' , deducem că dacă 0 ∈ ℤn este o soluție a ecuației atunci această ecuație are d soluții și anume:0 , ,……..

Corolar 1.4.3 Dacă n este număr prim, atunci ecuația = are soluție unică ℤn dacă și numai dacă (a, n)=1 , adică ,dacă și numai dacă n ł a.

Fracții periodice

Fiind dată fracția ∈ℚ, n∈ ℕ* prin împărțirea numărătorului la numitor putem scrie fracția sub formă zecimală a0 ,a1…… cu a0 ,a1……∈ ℕ.

Vom presupune că fracția  este subunitară, (m).

Dacă ar fi supraunitară împărțind pe m la n putem scrie m=n·q+r , q∈ℤ și 0 și atunci fracția se poate scrie q și astfel se continuă studiul lui  cu fractie subunitară ; în aceste condiții putem nota q.

De exemplu: .

În cazul în care 0<a<1, a0=0 astfel că prin împărțiri repetate vom scrie α=0,a1a2…, cu

ai∈ ℕ iar după cum se va vedea în continuare șirul a1a2…, poate fi finit sau infinit;

Dacă șirul este finit fracția zecimală se numește fracție zecimală finită iar dacă șirul este infinit și periodic fracția se numește fracție zecimală periodică.

Exemple:

α=

α=

α=

α=

α=

α=

In exemplele 1, 2 și 3 impărtirea se termină cu una sau două zecimale exacte,iar in exemplele 4, 5,și 6 impărțirea se continuă indefinit.

In exemplele 1, 2 și 3 fracțiile zecimale sunt finite, in exemplul 4 fracția zecimală este periodică simplă, iar în exemplele 5 și 6 fracțiile sunt periodice mixte.

În cele ce urmează vom proba că în general dacă avem o fracție subunitară, atunci șirul a1, a2, … este sau finit sau periodic.

În exemplul 5 resturile parțiale trebuie să fie mai mici decât 12, deci sunt posibile 11 resturi și după cel mult 12 împărțiri parțiale trebuie să obținem un rest care a mai fost obținut și știm de îndată ce restul se repetă și cifrele încep să se repete.

În general, dacă q este câtul, resturile parțiale fiind mai mici decât q, după cel mult q împărțiri parțiale resturile parțiale și deci cifrele câtului încep să se repete. Am subliniat cel mult q împărțiri, deoarece exemplele ne arată că repetarea resturilor parțiale poate începe și înainte de a fi trecut prin toate resturile posibile a priori.

Să adâncim acum chestiunea :

Observația de bază este următoarea: fiind dată fracția subunitară pentru a găsi primele n cifre ale fracției zecimale în care se transformă ea, facem împărțirea întreagă 10na:b.

De exemplu pentru a găsi primele 3 zecimale ale fracției , facem împărțirea 7000:15. 466

60

100

90

100

90

10

Să considerăm acum o fracție cu numărătorul 1, de exemplu și să facem împărțirile întregi 10:14 , 100:14, 1000:14, etc. Resturile acestor împărțiri reproduc tocmai resturile parțiale din împărțirea

10:14=0,7142……

0

100

98

20

14

60

56

40

28

12

10:14=0 rest 14 100:14=7 rest 2 1000:14=71 rest 6.

Pentru a ști în ce fel se transformă fracția , trebuie deci să urmărim resturile obținute prin împarțirea lui 10, 102, 103,….prin a.

Să începem cu cazul a este prim cu 10 (adică a descompus în factori primi nu are nici pe 2 nici pe 5 ca factori).

Știm din cele expuse mai înainte că, în acest caz, resturile încep să se repete după ce întâlnim restul 1, până acolo resturile fiind toate diferite. Știm că dacă 10d 1 (mod a), d este un divizor al lui φ(a). Știm că, dacă a=pqr…, cel mai exponent n, astfel ca să avem

bn 1 (mod a) oricare ar fi b prim cu a, este cel mai mic multiplu comun al numerelor

φ(p), φ(q), φ(r), …

Rezultă că: dacă a este prim cu 10, primul rest care se repetă în împărțirea 1:a este1, adică numărul cu care am început, deci în aceste condiții fracția este fracție zecimală periodică simplă.

De exemplu , 33=3·11 iar, φ(3)=2 și φ(11)=9, cel mai mic multiplu comun

al numerelor φ(3) și φ(11) este 18, deci fracția este periodică simplă cu perioada divizor al

lui 18.

Dacă numărătorul nu este 1, ci un alt număr prim cu a, rezultatele enunțate se mențin.

Fie acum cazul a=2 , adică a are numai factori primi ai lui 10. De exemplu,

a=40=2 3sau a=25=52. În acest caz, 10 ridicat la puterea  dacă sau la puterea dacă se divide cu a (dacă a=40, 10 3=233 se divide cu 23dacă a=25, 102=222 se divide cu 52).

Rezultă că, în acest caz, fracția zecimală rezultând din are un număr finit de zecimale, egal cu cel mai mare din numerele α și β.

De exemplu: 40=23atunci fracția are trei zecimale .

În general =, dacă sau dacă însă împărțirea unui număr cu10α se face despărțind prin virgulă cifre.

Dacă a=2 ·pm·qn….., fracția poate fi scrisă dacă 

Fracția se transformă într-o fracție periodică simplă. Dacă ea este mai mare decât 1 – ceea ce se poate întâmpla din cauza înmulțirii cu 5- ea se transformă tot într-o fracție periodică simplă, având însă și întregi. Această fracție înmulțită cu (adică mutând virgula cu cifre spre stânga ), ne dă fracția, care va avea ca parte neperiodică cele cifre, iar partea periodică aceeași ca și a fracției.

Dacă procedăm analog.

Exemplu: , atunci, ;

· , atunci,.

Teorema 1.5.1 Orice fracție se transformă într-o fracție zecimală cu un număr finit de zecimale sau într-o fracție zecimală cu un număr înfinit de zecimale, în care caz zecimalele admit o perioadă ce se repetă.

Reciproc, să vedem cum rescriem o fracție zecimală (simplă, periodică sau periodică mixtă ) sub forma p,q∈ ℕ q0.

Cazul 1. Dacă α=a0,a1a2….an, atunci în mod evident .

De exemplu: α=2,5=, ,

Cazul 2. Să presupunem acum că . atunci:

++….

+.

Însă = astfel că:

α=+ =.

De exemplu: α=2,(3)=2 , α.

Cazul 3. Să presupunem că α este o fracție zecimală periodică mixtă de forma:

Atunci:

.

De exemplu: α=1,2(3)=, 7,12(14)=.

Teorema 1.5.2 (i) Dacă α=a0,a1a2….an, atunci .

(ii) Dacă

(iii) Dacă, atunci

.

Teoremele lui Euler, Fermat și Wilson

Lema1.6.1 Dacă G este un grup (multiplicativ) finit cu n elemente(n≥2), atunci xn=1, pentru orice x∈G.

Demonstrație. Fie x∈G, iar k=o(x) (ordinul lui x). Atunci xk=1 și conform Teoremei lui Lagrange k|n, adică n=k·p cu p∈ℕ. Deducem imediat că xn=xkp=(xk)p=1p=1.

Observația 1.6.1 În cazul că G este comutativ există o demonstrație elementară ce evită Teorema lui Lagrange. Pentru aceasta se alege G={x1, x2,…,xn} și x∈G. Cum {xx1, xx2,…,xxn}=G={x1,…,xn}, deducem că(xx1)…(xxn)=x1…xn xn(x1…xn) = x1…xnxn=1.

Corolar 1.6.1(Euler) Dacă n ≥ 2 este un număr natural iar a∈ℤ astfel încăt (a, n)=1, atunci (φ fiind indicatorul lui Euler).

Demonstrație. (ℤn , ·) este un monoid cu φ(n) elemente inversabile. Astfel, dacă aplicăm Lema anterioară grupului G=U(ℤn , ·) (ce are φ(n) elemente) pentru a ∈ G obținem că :



Corolar 1.6.2(Mica teoremă a lui Fermat) Dacă p≥ 2 este un număr prim , iar a∈ℤ astfel încât p∤a , atunci .

Demonstrație .Cum p este un număr prim, φ(p)=p-1 și acum totul rezultă din

Corolarul 1.6.1.

Lema1.6.2 Fie G un grup (multiplicativ) finit comutativ iar produsul tuturor elementelor din G. Atunci .

Demonstrație .Vom scrie . Însă în cadrul produsului

vom grupa fiecare element x cu x-1 cu x x-1 ,dacă x= x-1 atunci x2=1 și deci o(x)=2 ceea ce este absurd și astfel =1, de unde deducem că

Corolar 1.6.3(Wilson) Dacă p≥2 este un număr prim, atunci(p-1)!+10(mod p).

Demonstrație. Cum p este prim (ℤp*, ·) este grup cu p-1 elemente și conform

Lemei 1.6.2

.Rămăne să punem în evidență elementele cu propietatea că p|x2-1=(x-1)(x+1) p|x-1 sau p|x+1 de unde deducem că

= sau , astfel că 

(p-1)!+10(mod p).

Voi prezenta în continuare câteva variante de generalizare ale Teoremei lui Wilson.

Lema1.6.3 Fie p≥2 un număr prim, iar n≥2 un număr natural. Atunci :

Dacă p=2 și n în grupul U(, ·) numai elementele au ordinul cel mult doi.

Dacă p atunci în grupul U(, ·) numai elementele au ordinul cel mult doi.

Demonstrație. Avem că U(, ·)= Să determinăm acest grup elementele astfel încât adică acele numere naturale a astfel încât 1≤a, cu

și a2-1 .

Evident dacă a=1 este verificată a2-1, iar dacă a atunci putem scrie a-1=pku și a+1=ptv cu k,t≥0, (p,u)=(p,v)=1 , iar k+t≥n.

Dacă k=0, atunci t≥n iar in aceste condiții a+1 și cum a rezultă că a+1= de unde a= și astfel obținem elementul ceea ce verifică de asemenea a2-1.

Dacă t=0 atunci k deci a-1 și cum a rezultă că a-1=0 du unde obținem că a=1, ceea ce este fals.

Dacă k≠0, t≠0 atunci 2= ptv- pku, adică 2|p, deci p≥2 și se obține o contradicție.

În concluzie dacă p, atunci în U() avem numai elementele=ce au ordinul cel mult doi.

Dacă p=2 , atunci din 2=2tv-2ku rezultă t=1 sau k=1. Dacă t=1 atunci k≥n-1, deci a-1=2ku≥2n-1u și cum 12n avem că u=2 și k=n-1. Deci ,în acest caz , dacă a verifică a2-1

atunci a=2n-1+1.

Dacă k=1 atunci t≥n-1, deci a+1=2tv≥2n-1v și cum 12n rezultă că v=1 sau v=2 , cazul v=2 fiind exclus deoarece (v,2)=1.

Dacă v=1 atunci t=n-1 sau t=n. În cazul în care t=n-1 rezultă a=2n-1-1, iar dacă t=n atunci a=2n-1.

În concluzie dacă p=2 și n în U() numai elementele au ordinul cel mult doi.

Corolar 1.6.4(O generalizare a teoremei lui Wilson) Dacă p este un număr prim și n un număr natural, atunci:

Dacă p și n≥2 atunci pn| ;

Dacă p=2 și n atunci 2n|;

Dacă p=2 și n=2 atunci 22|.

Demonstrație .Totul rezultă imediat din Lema 1.6.2 ținând cont de cele stabilite în Lema 1.6.3.

Teorema chinezească a resturilor

Fie m1, m 2, …,m t ℕ astfel încât  (mi, mj)=1 pentru orice i≠j, m=m1m2…m t, iar b1, b2,…,bt

Teorema 1.7.1 Teorema chinezească a resturilor

Sistemul are soluție în ℤ și oricare două soluții diferă printr-un multiplu de m.

Demonstrație. Dacă ni=, atunci (mi, ni)=1 pentru orice 1≤i. Astfel există ri,siastfel încât ri mi+sini=1 pentru orice 1≤i.

Dacă notăm ei=sini, atunci ei mod mi) și ei mod mj) pentru 1≤i, j≤t, i≠j.

Dacă vom considera , atunci vom avea x0 mod mi) și astfel x0 mod mi) pentru orice 1≤i de unde concluzia că x0 este soluție a sistemului din enunțul teoremei.

Să presupunem că x1 este o altă soluție a sistemului . Atunci x1-x0mod mi) pentru

1≤iadică mi x1-x0 pentru orice 1≤i, și cum (mi , mj)=1 pentru i≠j, deducem că m=m1m2…m tx0-x1, adică x0 x1mod m).

Să interpretăm acum teorema chinezească a resturilor din punct de vedere al teoriei inelelor.

Fie pentru aceasta (Ai)iI o familie nevidă de inele (unitare).Vom considera un nou inel notat și având mulțimea subiacentă , iar pentru

x ,y x= și y= definim x+y= și x·y.

Se verifică imediat că () este un inel unitar în care elementul nul este 0=

Cu pentru orice iar pentru x=, -x= elementul unitate este 1= cu pentru orice , iar dacă x= atunci x dacă și numai dacă pentru orice , astfel zis =.

Fie m1 , m 2, …,m t astfel încât  (mi, mj)=1 pentru orice i≠j, m=m1m2…m t.

Teorema 1.7.2 Avem următorul izomorfism de inele :  m.

Demonstrație. Pentru fiecare 1≤i , :, morfismul surjectiv canonic de inele ce duce fiecare element xℤ în clasa sa de echivalență modulo mi.

Definim fprin f(x)= pentru orice xℤ.

Dacă x,y ℤ și f(x)=f(y) atunci (mod ) pentru orice 1≤i

deoarece (mi, mj)=1 pentru 1≤i≠j≤t  pentru orice 1≤i. Deducem astfel că f este bine definită și că funcția f este o injecție. Se verifică imediat că f este morfism de inele unitare .

Surjectivitatea lui f rezultă fie din teorema chinezească a resturilor, fie observând că

m1m2…m t.

Deci f este un izomorfism de inele unitare.

Corolar 1.7.1 Cu notațiile de la teorema precedentă avem următorul izomorfism de grupuri multiplcative : U ( Z m) U () … U () .

Corolar 1.7.2 Fie φ:ℕℕ indicatorul lui Euler.

Dacă m1, m 2, …,m t ℕ astfel încât  (mi, mj)=1 pentru orice i≠j, atunci φ(m1m2…m t)= φ(m1) φ(m2)….. φ(mt);

Dacă p≥2 este număr prim și n  ℕ*, atunci φ(pn)=pn-pn-1=pn(1-);

Dacă n= este descompunerea în factori primi a lui n , atunci

φ(n)=n(1-)… (1-).

Demonstrație.

Am văzut că = φ(m) pentru orice m ℕ, m≥2, iar dacă ținem cont de corolarul anterior deducem că



φ (m)= φ(m1) ….. φ(mt).

Prin calcul direct se deduce că între 1 și pn există pn – pn-1 numere naturale mai mici strict decât pn și prime cu pn (adică cu p), de unde egalitatea φ(pn)=pn-pn-1.

Ținând cont de (i) și (ii) deducem că:

φ (n)= φ()=( )… ( )=

=(1-)… (1-)= n(1-)… (1-).

De exemplu: φ(15)= φ(3·5)=15(1-) (1-)=15··=8.