Cuprins

1 Divizibilitate 3

1.1 Definitii. Proprietati de baza . . . . . . . . . . . . . . . . . . . . . 3

1.2 Divizori. Numere prime . . . . . . . . . . . . . . . . . . . . . . . . 4

1.3 Exponentul unui numar prim n descompuneri n factori primi . . . 17

2 Congruente 25

2.1 Introducere. Proprietati de baza

a congruentelor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

2.2 Aplicatie: Criterii de divizibilitate. . . . . . . . . . . . . . . . . . . 30

2.3 Teorema fundamentala a aritmeticii . . . . . . . . . . . . . . . . . 34

2.4 Sisteme complete de resturi modulo m. . . . . . . . . . . . . . . . . 42

2.5 Patrate si cuburi perfecte . . . . . . . . . . . . . . . . . . . . . . . 54

2.6 Suma cifrelor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58

2.7 Inegalitati n teoria numerelor . . . . . . . . . . . . . . . . . . . . . 60

2.8 Probleme de constructie . . . . . . . . . . . . . . . . . . . . . . . . 67

2.9 Algoritmul lui Euclid. Divizori comuni . . . . . . . . . . . . . . . . 80

3 Metode Algebrice 89

3.1 Descompuneri . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92

3.2 Relatii de tip ab = cd. Consecinte si aplicatii . . . . . . . . . . . . 95

3.3 Inductia Matematica . . . . . . . . . . . . . . . . . . . . . . . . . . 101

3.4 Impartirea n perechi . . . . . . . . . . . . . . . . . . . . . . . . . . 105

3.5 Metoda coborrii. Teorema lui Viete . . . . . . . . . . . . . . . . . 108

3.6 Teoremele lui Fermat si Euler . . . . . . . . . . . . . . . . . . . . . 112

3.7 Ordinul unui numar . . . . . . . . . . . . . . . . . . . . . . . . . . 121

1

3.8 Teorema Chineza a Resturilor (T.C.R.) . . . . . . . . . . . . . . . 125

3.9 Reprezentari n forme speciale . . . . . . . . . . . . . . . . . . . . . 136

3.10 Resturi patratice . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144

4 Diverse 153

4.1 Equatii Diofantice . . . . . . . . . . . . . . . . . . . . . . . . . . . 153

4.2 Siruri . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155

4.3 Progresii aritmetice . . . . . . . . . . . . . . . . . . . . . . . . . . . 158

4.4 Teorema lui Bertrand . . . . . . . . . . . . . . . . . . . . . . . . . 162

4.5 Multimi. Partitii speciale ale lui N . . . . . . . . . . . . . . . . . . 1634.6 Ecuatii functionale . . . . . . . . . . . . . . . . . . . . . . . . . . . 165

4.7 Permutari. Principiul lui Dirichlet . . . . . . . . . . . . . . . . . . 167

4.8 Diverse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169

5 Probleme propuse 183

2

Capitolul 1

Divizibilitate

1.1 Definitii. Proprietati de baza

Definitie. Fie numerele ntregi a, b, b 6= 0. Spunem ca a se divide cu b, dacaexista un numar ntreg k astfel nct a = kb. In acest caz, mai spunem, echivalent,

ca b divide pe a, b este divizor al lui a, sau a este multiplu al lui b. Aceasta relatie

ntre a si b se noteaza in urmatoarele moduri:

a... b a se divide cu b

b | a b divide pe a

Evident, orice numar natural a i are ca divizori pe 1 si a. Daca acestia sunt

singurii divizori pozitivi ai sai, a se numeste prim, iar in caz contrar compus.

Definitie. Fie a, b Z. Daca d Z divide pe a si pe b, atunci spunem ca d estedivizor comun al lui a si b. Cel mai mare divizor comun al lui a si b se noteaza

prin (a, b). Numerele a si b se numesc prime ntre ele daca (a, b) = 1. Daca m Zse divide cu a si cu b, spunem ca m este multiplu comun al lui a si b. Printre

multiplii comuni pozitivi a lui a si b exista unul minim cel mai mic multiplu

comun al lui a si b notat prin [a, b].

Relatiile de divizibilitate au urmatoarele proprietati de baza:

1. (reflexivitate) a | a

2. (antisimetrie) a | b, b | a a = b

3

3. (tranzitivitate) a | b, b | c a | c

4. a | b, c | d ac | bd. In particular, a | b an | bn, n N.

5. (a, c) = 1, a | bc a | b.

1.2 Divizori. Numere prime

Problema 1. Fie n un numar prim, mai mare ca 5. Demonstrati ca

240 | n8 1.

Solutie. Descompunem numarul n8 1 n felul urmator:

n8 1 = (n 1)(n+ 1)(n2 + 1)(n4 + 1)

Deoarece n nu se divide la 3 (fiind prim si mai mare ca 5), unul din numerele

n 1, n + 1 se divide la 3, deci produsul de mai sus se divide la 3. Aratam caacest produs se divide si cu 5. Intr-adevar, deoarece 5 nu divide pe n, unul din

numerele n 1, n+ 1, n 2, n+ 2 se divide cu 5, adica

5 | (n 1)(n+ 1)(n+ 2)(n 2)

Ultima expresie se mai scrie astfel

(n 1)(n+ 1)(n2 4) = (n 1)(n+ 1)(n2 + 1) 5(n 1)(n+ 1),

prin urmare, 5 | (n1)(n+1)(n2+1). Deoarece n este impar, n1, n+1, n2+1 sin4+1 se divide toate la 2, si atunci produsul lor se divide cu 16. Mai sus am aratat

ca el se mai divide la 3, 5. Prin urmare, el se divide si la [3, 5, 16] = 3 5 16 =240.

Problema 2. Care este cel mai mare numar pozitiv n, pentru care n3 + 100 se

divide la n+ 10?

Solutie. Evident, n3 + 103 = (n + 10)(n2 10n + 100) se divide cu n + 10. Decin+ 10 | n3 + 100 n+ 10 | 900. Asadar, cel mai mare numar n pentru care 900este divizibil cu n+ 10 este 890.

Problema 3. Fie n un numar natural, n > 1. Demonstrati ca numarul 1 + 12 +13 + . . .+

1n nu este ntreg.

4

Solutie. Aducem toate fractiile din suma Fie A = 1 + 12 +13 + . . .+

1n la numitorul

comun. Din toti termenii sumei, alegem pe cel n care numitorul se divide cu

cea mai mare putere a lui 2 (acest termen unic are forma 12k

unde 2k n 15, n 10. Fie n este par, n = 2k 10, atuncian = 2

3k(k + 1)(k + 2). Cel putin unul dintre numerel k, k + 1 sau k + 2 este

divizibil la 2 si exact unul din ei se divide la 3. Deoarece k 5, numerele k, k+ 1,k+ 2 nu pot fi toate concomitent puteri ale lui 2 si 3. Deci k(k+ 1)(k+ 2) mai are

un divizor prim p > 3. Prin urmare, 24 3 p divide an, si atunci din observatiilede mai sus, avem

(an) (24 3 p) = 5 2 2 > 15.Fie n 10 si impar. Atunci numerele n, n+ 2, n+ 4 sunt prime ntre ele doua ctedoua, si atunci (an) = (n)(n+ 2)(n+ 4). Evident, fiecare din cei trei factori

este mai mare ca 1. Vom arata ca unul din ei este mai mare ca 3. Intr-adevar,

unul din numerele n, n + 2, n + 4 se divide cu 3. Acesta, fiind mai mare ca 9,

sau se divide cu 33, sau mai are un alt divizor prim p, si deci numarul divizorilor

sai este cel putin min{(33), (3p)} = 4. Prin urmare, pentru n 10 impar,(an) 4 2 2 > 15.

Astfel, numarul an are cel mult 15 divizori pentru n = 1, 2, 3, 4, 5, 7, 9.

Problema 11. Sa se determine toate numerele naturale n si m pentru care

(n, n+ 6) + (n+ 1, n+ 7) + (n+ 2, n+ 8) + . . .+ (n+m,n+m+ 6) = 2010.

Maria Pop

7

Solutie. Fie d = (k, k+ 6). Arunci d|(k+ 6) k = 6, deci d {1, 2, 3, 6} si n plus(k, k + 6) = (k + 6, k + 12).

Pentru k = 1 + 6p avem (k, k + 6) = 1.

Pentru k = 2 + 6p avem (k, k + 6) = 2.

Pentru k = 3 + 6p avem (k, k + 6) = 3.

Pentru k = 4 + 6p avem (k, k + 6) = 2.

Pentru k = 5 + 6p avem (k, k + 6) = 1.

Pentru k = 6p avem (k, k + 6) = 6.

Impartim suma data n succesiuni de sase termeni, fiecare succesiune avand

suma

1 + 2 + 3 + 2 + 1 + 6 = 15.

Avem 2010 = 134 15 si n suma de m+ 1 termeni apar 134 6 numere. Astfelobtinem m = 134 6 1 = 803 si n este arbitrar.

Problema 12. Pentru fiecare numar natural n 1 notam cu an = (n + 1)(n +2) . . . (2n). Sa se arate ca:

a) an|an+1;b) 2n|an;c) 2n+1 - an.

Maria Pop

Solutie. a)an+1an

=(n+ 2)(n+ 3) . . . (2n)(2n+ 1)(2n+ 2)

(n+ 1)(n+ 2) . . . (2n)

=(2n+ 1)(2n+ 2)

n+ 1= 2(2n+ 1).

b) Din a) avem:a2a1

= 2 3, a3a2

= 2 5, . . ., anan1

= 2(2n 1), pe care daca lenmultim obtinem

ana1

= 2n1 3 5 . . . (2n 1)

si cum a1 = 2 rezulta an = 2n(3 5 7 . . . (2n 1))...2n.

c) In paranteza de mai sus avem un produs de numere impare, care este impar,

deci 2n+1 nu divide an.

Problema 13. Sa se determine numerele naturale p 2 pentru care exista numerenaturale N formate din 5 cifre distincte, cu proprietatea ca orice numar obtinut

prin orice permutare a cifrelor lui N , se divide cu p.

8

Vasile Pop

Solutie. Daca n numarul N exista doua cifre consecutive a si a + 1, consideram

numerele obtinute prin permutarea cifrelor lui N : N1 care se termina cu cifrele

(a+ 1), a si N2 care se termina cu a, (a+ 1) si primele trei cifre la fel. Deoarece

N1 si N2 se divid cu p, rezulta N1 N2 se divide cu p p|q (N1 N2 =(a+ 1)10a (a 10 +a+ 1) = 9), deci p {3, 9}. Se stie ca N se divide cu 3 sau9 daca suma cifrelor se divide cu 3 sau 9. Orice numar obtinut prin permutarea

cifrelor este acelasi, daca p = 3 si p = 9 verifica cerinta. Daca numarul N nu

contine cifre consecutive atunci cifrele lui sunt 1, 3, 5, 7 si 9 sau 0, 2, 4, 6, si 8.

In primul caz luam N1 = 97531 si N2 = 97513, N1N2 = 18 deci p poate fi 2,3, 6, 9, 18. Deoarece N este impar raman doar 3 si 9 (nimic n plus).

In al doilea caz luam N1 = 86420 si N2 = 86402, N1 N2 = 18 deci p {2, 3, 6, 9, 18} si cum suma cifrelor lui N este 20 (nedivizibila cu 3) ramane p = 2care verifica conditia.

In concluzie p {2, 3, 9}.

Problema 14. Un patrat de dimensiuni 3 3 se mparte n 9 casute 1 1dispuse pe 3 linii si 3 coloane. In cele 9 casute se scriu toate numerele de la 1 la

9. O completare se numeste buna (c.b.) daca pentru orice i = 1, 2, 3 produsul

numerelor de pe linia i este egal cu produsul numerelor de pe coloana i.

Sa se determine numarul completarilor bune.

Vasile Pop

Solutie. a) Numerele 5 si 7 sunt pe diagonala. Daca 5 ar apare pe pozitia (i, j), 5

de pe linia i trebuie compensat n produs cu un 5 de pe coloana j si cum 5 apare

o singura data rezulta i = j. Analog si 7 se afla pe o pozitie (i, i).

b) Numarul 9 se afla pe diagonala.

Daca 9 ar fi pe pozitia (i, j), 9 de pe linia i poate fi compensat n produsul

de pe coloana h doar cu perechea de numere 3 si 6 = 3 2, iar 9 de pe coloanaj trebuie compensat pe linia i cu perechea 3 si 6. Daca i 6= j atunci cele douanumere 3 si 6 ar trebui sa ocupe 3 casute, deci i = j si 9 este pe diagonala.

c) Numerele 5, 7 si 9 ocupa diagonala n 3! = 6 noduri.

d) Daca 8 se afla n casuta (i, j), i 6= j, atunci 4 se afla n casuta (j, i).Produsul de pe linia i care contine pe 8 poate fi compusat doar de perechea 4

si 2 sau de perechea 4 si 6 pe coloana i, analog 8 de pe coloana j se compenseaza

pe linia j doar cu una din perechile 4 si 2 sau 4 si 6. Rezulta ca 4 se afla n casuta

9

(j, i) si astfel linia j si coloana i se completeaza total n doua moduri (cu 2 si 6

sau invers).

e) Pentru fiecare aranjare (arbitrara) a numerelor 5, 7 si 9 pe diagonala si a lui

8 pe una din cele 6 pozitii ramase, se pot construi doua c.b..

Conform lui d) daca 8 este n casuta (i, j) linia j si coloana i sunt completate

n doua c.b.. Raman doua casute n care sa plasam pe 1 si pe 3 sau pe 3 si pe 1.

5 8 1, 3

4 7 6, 2

2, 6 3, 1 9

In concluzie avem 6 6 2 = 72 c.b..Observatie. Daca se considera ca prin notatiile de 90C, 180C, 270C se obtine

aceeasi c.b. se obtin72

4= 18 c.b. diferita.

Daca se considera ca tablele pot fi privite si de pe cealalta parte (fata) atunci

numarul c.b. distincte este72

4 2 = 9 table.

Problema 15. Fie a, b numere naturale astfel ca (a, b) = 6. Sa se determine

valorile posibile ale lui (a2, b3).

Solutie. Fie a = 6a, b = 6b cu (a, b) = 1. Avem

(a2, b3) = (36a2, 36 6b3) = 36(a2, 6b3).

Deoarece (a, b) = 1 singurii divizori comuni pentru a2 si 6b3 pot fi doar 1, 2, 3,6 si obtinem pentru (a2, b3) valorile 36, 2 36, 3 36 si 6 36.

Problema 16. Sa se arate ca pentru orice numar natural n numerele n! + 1 si

(n+ 1)! + 1 sunt relativ prime.

Solutie. Din relatia (n+ 1)(n! + 1) ((n+ 1)! + 1) = n rezulta ca daca d|n! + 1 sid|(n+ 1)! + 1 atunci d|n. Dar daca d|n evident ca d - n! + 1.

Problema 17. Sa se arate ca numarul de zerouri cu care se termina reprezentarea

n baza 10 a unui numar factorial n! este egal cu puterea maxima a lui 15 cu care

se divide n!.

Solutie. Numarul zerourilor este egal cu puterea maxima a lui 10 care divide pe

n!, adica v10(n!). Dar v10(n!) = v5(n!) caci puterea lui 5 n n! este mai mica decat

10

puterea lui 2 n n!. Pe de alta parte v15(n!) = v5(n!) tot din acelasi motiv (puterea

lui 3 n n! este mai mare ca puterea lui 5 n n!).

Problema 18. Sa se arate ca numarul de zerouri n care de termina numarul n!

n scrierea lui zecimala este

zn =n (a10 + a1 + . . .+ ak)

4

unde n = a0 + a1 5 + a2 52 + . . .+ ak 5k este scrierea n baza 5 a lui n.

Solutie. Prin calcul obtinem

zn = ak(5n1 + 5k2 + . . .+ 5 + 1) + ak1(5k2 + 5k3 + . . .+ 5 + 1)

+ . . .+ a2(5 + 1) + a1.

Pe de alta parte numarul de zerouri cu care se termina n! este egal cu puterea

maxima a lui 10 la care se divide n!, aceeasi cu puterea maxima a lui 5 cu care se

divide n! care este

sn =[n

5

]+[ n

52

]+ . . .+

[ n5k

].

Daca n ultima suma nlocuim pe n obtinem sn = zn.

Problema 19. (Rusia, 1995) Fie (an)n1 un sir de numere naturale cu propri-etatea (am, an) = (m,n) pentru orice m 6= n. Sa se arate ca an = n, pentru oricen 1.

Solutie. Avem (an, a2n) = (n, 2n) = n, deci n|an, deci n|an pentru orice n, decitoti divizorii lui n sunt divizori pentru an.

Reciproc: Fie m un divizor al lui an. Din m|am rezulta m|(an, am) = (n,m),deci m|n si astfel numerele n si an au aceiasi divizori.

Problema 20. Sa se determine cel mai mic numar natural n cu proprietatile:

2|(n+ 1), 3(n+ 2), . . . , 9|(n+ 8).

Solutie. Avem urmatoarele relatii de divizibilitate:

2|(n+ 1) 2|(n 1) + 2 2|(n 1)

3|(n+ 2) 3|(n 1) + 3 3|(n 1). . . . . . . . .

11

9|(n+ 8) 9|(n 1) + 9 9|(n 1)

Deci n 1 se divide cu 2, 3, 4, . . . , 9. Cel mai mic multiplu comun al acestornumere este M = 23 32 5 7 = 2520 si atunci cel mai mic n este n = 2521.

Problema 21. Fie x, y, z numere naturale nenule care satisfac relatia xy = z(x+

y) si are au doar pe 1 ca divizor comun. Sa se arate ca x+ y este patrat perfect.

Solutie. Fie d = (x, y), x = dx1, y = dy1 cu (x1, y1) = 1. Avem

xy = z(x+ y) d2x1y1 = zd(x1 + y1) dx1y1 = z(x1 + y1).

Deoarece (d, z) = 1 rezulta ca z divide produsul x1y1.

Deoarece (x1, x1 + y1) = 1 rezulta ca x1|z si analog y1|z si cum (x1, y1) = 1rezulta (x1y1)|z, n concluzie x1y1 = z si x1 + y1 = d, deci

x+ y = d(x1 + y1) = d2.

Problema 22. Fie a, b, c, d numere ntregi astfel ca |ac bd| = 1. Sa se arate ca

(a+ b, c+ d) = 1.

Solutie. Avem (a+ b)c+ (c+ d)b = ac bd = 1 si daca d|a+ b si d|c+ d rezultaca d| 1, deci d = 1.

Problema 23. Fie p > 3 astfel ca p si p+ 2 sa fie numere prime. Sa se arate ca

p+ 1 se divide cu 3.

Solutie. Deoarece p este prim el poate fi de forma p = 3k + 1 sau p = 3k + 2. In

primul caz p+ 2 = 3k + 3 = 3(k + 1) care nu este prim. Ramane ca p = 3k + 2 si

atunci p+ 1 = 3(k + 1) care se divide cu 3.

Problema 24. Fie n, a1, a2, . . . , an numere naturale impare. Sa se arate ca

n-uplurile (a1, a2, . . . , an) si

(a1 + a2

2,a2 + a3

2, . . . ,

an + a12

)au acelasi cel mai

mare divizor comun.

Solutie. Fie d1 si d2 cei doi divizori si fie

a1 = d1b1, a2 = d1b2, . . . , an = d1bn,

12

astfel ca b1, b2, . . . , bn sa nu aiba divizor comun 1. Deoarece a1, . . . , an suntimpare rezulta ca d1, b1, b2, . . . , bn sunt impare si atunci

ai + ai+12

= d1 bi + bi+12

= d1ki,

deci d1 divide pe d2. Analog

a1 + a22

= d2c1,a2 + a3

2= d2c2, . . . ,

an + a12

= d2cn,

deci a1 +a2, a2 +a3, . . . , an+a1 se divide cu 2d2. Adunandu-le obtinem ca 2(a1 +

a2 + . . .+ an) se divide cu 2d2 si cum a1 + a2 + . . .+ an nu se divide cu 2 rezulta

ca a1 + a2 + . . .+ an se divide cu d2. Adunam acum

(a1 + a2) + (a3 + a4) + (a5 + a6) + . . .+ (an2 + an1) = a1 + a2 + . . .+ an1

care se divide cu 2d2, deci si cu d2. Din a1 +a2 + . . .+an si a1 +a2 + . . .+an1 sedivide cu d2 rezulta an se divide cu d3 si procedand analog (permutari circulare)

rezulta an, an1, . . . , a1 se divide cu d2 deci d2 divide d1.

Problema 25. Fie m,n numere naturale astfel ca 0 < m < n. Sa se decida daca

urmatoarele afirmatii sunt adevarate pentru orice numere naturale a, b:

1) am|bn a|b2) an|bn a|b.

Solutie. Prima afirmatie nu este n general adevarata. Un contraexemplu este dat

de a = 2n, b = 2m.

A doua afirmatie este adevarata: fie p un numar prim care divide pe a si vp(a)

puterea maxima a lui p care divide pe a. Avem vp(an) = nvp(a) si din conditia

an|bm rezulta nvp(a) mvp(b) si cum n > m rezulta vp(a) < vp(b), deci a|b.

Problema 26. Fie n un numar natural nenul si d1, d2, . . . , dk divizorii lui naturali.

Sa se arate ca:

a)d1 + d2 + . . .+ dk1

d1+

1

d2+ . . .+

1

dk

= n.

b) (d1d2 . . . dk)2 = nk.

Solutie. a) Avem de aratat ca

d1 + d2 + . . .+ dk = n

(1

d1+

1

d2+ . . .+

1

dk

).

13

Daca d este un divizor al lui n atuncin

deste tot un divizor al lui n si atunci

multimile

{d1, d2, . . . , dk} si{n

d1,n

d2. . . ,

n

dk

}coincid, deci au aceeasi suma.

b) Deoarece

{d1, d2, . . . , dk} ={n

d1,n

d2. . . ,

n

dk

}rezulta

d1d2 . . . dk =n

d1 nd2 . . . n

dk (d1d2 . . . dk)2 = nk.

Problema 27. Pentru orice numar natural n notam cu P (n) produsul tuturor

divizorilor naturali ai lui. Sa se arate ca P (n) = P (m) daca si numai daca m = n.

Solutie. Fie n = p11 p22 . . . pkk si m = p11 p22 . . . pkk descompunerile nfactori primi, n care 1, 1, . . . , k, k 0. Evident ca

P (n) = pa1a pa22 . . . pakk .

Numarul p1 apare n toti divizorii lui p22 . . .pkk , n numar de (2+1). . .(k+1),

la fel p21, . . . , p11 astfel ca exponentul lui p1 n P (n) este

a1 = (1 + 2 + . . .+ 1)(2 + 1) . . . (k + 1)

=1(1 + 1)

2(2 + 1) . . . (k + 1) = 1

2d(n),

unde d(n) este numarul divizorilor lui n. Avem:

P (n) = P (m) 12d(n) =

12d(m) 1 = 1 d(n)

d(m)

si analog

2 = 2 d(n)d(m)

, . . . , k = k d(n)d(m)

.

Revenind n relatia P (n) = P (m) obtinem:

(1 + 1) . . . (k + 1) = d(n)d(m)

(d(n)

d(m)1 + 1

) . . .

(d(n)

d(m)k + 1

).

Din simetrie putem presupune d(n) d(m), decid(n)

d(m) 1.

14

Pentrud(n)

d(m)> 1 egalitatea de mai sus este falsa, deci

d(n) = d(m) 1 = 1, . . . , k = k n = m.

Reciproc: daca m = n atunci P (n) = P (m).

Problema 28. Sa se arate ca pentru orice numar natural n 1 numarul (n!)(n1)!divide numarul (n!)!.

Solutie. Numarul (n!)! este produsul a n! numere consecutive

1 2 . . . n (n+ 1) . . . (2n) . . . (n!)

si separam acest produs n produse de cate n numere consecutive, n numar de

(n 1)!. Fiecare astfel de produs se divide la n! (produsul a n numere consecutivese divide la n!), deci ntregul produs se divide la (n!)(n1)!.

Problema 29. Fie p1, p2, . . . , pn numere prime. Sa se arate ca1

p1+

1

p2+ . . .+

1

pnnu este numar ntreg.

Solutie. Aducand la numitor comun obtinem ca numarul este

p2p3 . . . pn + p1p3 . . . pn + . . .+ p1p2 . . . pn1p1p2 . . . pn

.

Numitorul se divide cu p1 iar numaratorul nu, deoarece primul produs nu se divide

cu p1 iar celelalte se divid cu p1.

Problema 30. Fie p > 3 un numar prim si sumele

S1 = 1 +1

2+

1

3+ . . .+

1

p 1 , S2 = 1 +1

22+

1

32+ . . .+

1

(p 1)2 .

Daca S1 =a

b, cu (a, b) = 1 si S2 =

c

d, cu (c, d) = 1, sa se arate ca p2|a si p|c.

Solutie. In S, grupam cate doi termeni:

S1 =

(1 +

1

p 1)

+

(2 +

1

p 2)

+

(3 +

1

p 3)

+ . . .

= p

(1

1 (p 1) +1

2(p 2) +1

3(p 3) + . . .).

15

In aceasta forma numaratorul se divide cu p si toti numitorii care contribuie la

numitorul comun sunt primi cu p, deci p va divide numaratorul final.

Ramane de aratat ca si numaratorul suma:

S3 =1

1 (p 1) +1

2(p 2) +1

3(p 3) + . . .

se divide cu p.

Daca lucram modulo p atunci p 1 1, p 2 = 2, p 3 = 3 (mod p)deci

S3 = (

1

12+

1

22+

1

32+ . . .

)= 1

2S2 (mod p).

Va ramane de aratat doar ca numaratorul lui S2 se divide cu p.

In Zp numerele1

12,

1

22,

1

32, . . . ,

1

(p 1)2 sunt aceleasi cu 12, 22, . . . , (p 1)2 (n

alta ordine) si atunci

S2 12 + 22 + . . .+ (p 1)2 = p(p+ 1)(2p+ 1)6

0 (mod p).

Problema 31. Sa se determine numerele naturale impare n 3 cu proprietatea capentru orice doi divizori d1, d2 relativ primi, numarul d1 +d21 este de asemeneaun divizor al lui n.

Rusia 2001

Solutie. Daca n este o putere a unui numar prim: n = pk, cu p 3, atunci doidivizori reciproc primi sunt 1 si pm, cu m k si evident ca

d1 + d2 1 = 1 + pm 1 = pm|n.

Vom arata ca aceste numere sunt singurele ce satisfac conditiile din enunt.

Intr-adevar, presupunem ca n satisface conditiile din enunt, si n nu este o

putere a unui numar prim. Atunci putem scrie n = pkq unde p este cel mai mic

divizor prim al lui n, q 3, (p, q) = 1. Alegem d1 = p, d2 = q si atunci

p+ q 1 | n

Fie q1 un divizor prim al lui q. Din minimalitatea lui p si q1 | n, avem q1 > p, deciq < p + q 1 < q + q1. Deoarece q si q + q1 sunt doi multipli consecutivi ai luiq1, concludem ca p+ q 1 nu este multiplu de q1. Acest fapt este valabil pentru

16

orice q1, si deci (p + q 1, q) = 1. Prin urmare, acest divizor al lui n are formap+ q 1 = p cu 1 k. Acum consideram divizorii lui n:

d1 = p, d2 = q

si atunci din conditiile din enunt avem

d1 + d2 1 = 2p p = p(2p1 1) | n = pkq

Cum 2p1 1 nu divide p, rezulta ca 2p1 1 divide pe q. Deoareceq

2p1 1 | n,

minimilitatea lui p implica q2p1 > p sau q = 2p1 1. In primul caz, avem

q > 2 p 2 1 < p+ q 1 = p, absurd. In celalalt caz, avem

p = p+ q 1 = p+ 2p1 1

Deoarece pentru > 1 membrul drept al acestei ecuatii nu se divide cu p, obtinem

= 1 si atunci p = p+ 1, contradictie.

Problema 32. (Iran 2005) Fie n un numar ntreg pozitiv si p un numar prim

impar astfel nct n divide p 1 si p divide n3 1. Demonstrati ca 4p 3 estepatrat perfect.

Solutie. Evident, n1 < p (n1, p) = 1. Cum p | n31 = (n1)(n2+n+1),obtinem ca p | n2 + n+ 1. Vom demonstra ca p = n2 + n+ 1.

Fie p1 = qn. Daca n p, atunci p n2+n+1 < 2p, de unde p = n2+n+1.Daca n >

p, atunci q 99.

Problema 35. Fie a, b, c numere naturale nenule.

a) Sa se arate ca daca numerele ab, bc, ca sunt cuburi perfecte atunci a, b, c

sunt cuburi perfecte.

b) Afirmatia de mai sus ram1ne adevarata pentru patrate perfecte?

Solutie. a) Fie vp(n) puterea maxima a numarului prim p care divide n. Avem

vp(ab) = vp(a) + vp(b)

si atunci conditiile date sunt

3 | vp(a) + vp(b), 3 | vp(b) + vp(c) si 3 | vp(c) + vp(a)

3 | vp(a) vp(c) 3 | (vp(a) + vp(c)) + (vp(a) vp(c)),

deci 3|2vp(a) 3|vp(a) si analog 3|vp(b), 3|vp(c).b) Pentru patrate perfecte rezultatul nu este adevarat (de exemplu, pentru

a = b = c = 2 numerele ab, bc, ca sunt patrate perfecte).

Problema 36. Fie m,n numere naturale. Sa se arate ca:

a) m! n! divide (m+ n)!b) m! n! (m+ n)! divide (2m)! (2n)!.

19

Solutie. a) Fie p un numar prim arbitrar care divide m! sau n!. Trebuie aratat ca

vp(m! n!) vp((m+ n)!).

Avem:

vp(m! n!) = vp(m!) + vp(n!)

=

[m

p

]+

[m

p2

]+ . . .+

[m

pk

]+

[m

p

]+

[n

p2

]+ . . .+

[n

pk

]=

([m

p

]+

[n

p

])+

([m

p2

]+

[m

p2

])+ . . .+

([m

pk

]+

[n

pk

])[m+ n

p

]+

[m+ n

p2

]+ . . .+

[m+ n

pk

]= vp((m+ n)!)

(Am folosit inegalitatea [x] + [y] [x+ y] iar k este astfel ca pk m+ n < pk+1).Observatie.

(m+ n)!

m! n! =(m+ n

m

) N.

b) In mod analog aratam ca

bp(m! n! (m+ n)!) vp((2m)! (2n)!)

vp(m!) + vp(n!) + vp((m+ n)!) vp((2m)!) + vp((2n)!).Vom folosi inegalitatea [x] + [y] + [x+ y] [2x] + [2y].

Problema 37. Fie a, b, c, d numere naturale nenule. Sa se arate ca:

1) (a, b, c) =abc [a, b, c]

[a, b] [b, c] [c, a] ;

2) [a, b, c] =abc (a, b, c)

(a, b) (b, c) (c, a) ;3) abc = (a, b, c) [ab, bc, ca];4) (a, b) (c, d) = (ac, ad, bc, bd);5) ([a, b], [b, c], [c, a]) = [(a, b), (b, c), (c, a)].

Solutie. Fie p un numar prim (care apare n descompunerea unuia dintre a, b, c, d

si notam cu , , , exponentul la care apare n descompunerea lui a, b, c, d:

= vp(a), = vp(b), = vp(c), = vp(d),

unde , , , 0.Datorita simetriei putem presupune si atunci avem:

vp((a, b)) = , vp([a, b]) = , vp((b, c)) = , vp([b, c]) = ,

20

vp((c, a)) = , vp([c, a]) = , vp((c, d)) = , vp((a, b, c)) = ,

vp([a, b, c]) = , vp(abc) = + + ,

vp([ab, bc, ca]) = max{+ , + , + } = + ,vp((ac, ad, bc, bd)) = min{+ , + , + , + } = + .

Astfel relatiile devin:

1) = (+ + + ) ( + + )2) = (+ + + ) (+ + )3) + + = + ( + )

4) + = +

5) min{, , } = , max{, , } = care sunt evident verificate.

Problema 38. Sa se rezolve n numere naturale nenule ecuatia

1!3! . . . (2m 1)! = (m(m+ 1)2

)!

Solutie. Vom demonstra mai inti c nu avem solutii pentru m 5. Fie

k =m(m+ 1)

2, x =

mi=1

(2i 1)! = k!

Sumnd inegalitatile

[k

2i

] k

2idupa i = 1, 2, . . ., obtinem

vp(k!) =

i=1

[k

2i

]i=1

k

2i= k

Dar nu putem avea egalitate deoarece

[k

2i

]= 0 k. Astfel,

vp(k!) < k.

Pe de alta parte p((2i 1)!) = 2i1j=1 p(j) = p(1) +ij=2(p(2j 1) + p(2(j 1))) =

ij=2(p(j 1) + 1) = p((i 1)!) + i 1. Astfel p(

mi=1(2i 1)!) =

p(1!)+mi=2 p((2i1)!) =

mi=2(p((i1)!)+ i1) =

m1i=1 p(i!)+

m1i=1 i. Cum

p(i!) 1, i 5, avem p(x) p(1!) +p(2!) +p(3!) +p(4!) + (m5) 1 + (m1)m2 =0 + 1 + 1 + 3 +m 5 + (m1)m2 = m(m+1)2 = k. Astfel k p(x) < k. Contradictie.Deci m 4.

Substituind m = 1, 2, 3, 4 n ecuatia din enunt obtinem o egalitate. Astfel,

solutiile ecuatiei sunt 1, 2, 3, 4.

21

Problema 39. Fie x, y, z numere naturale nenule cu proprietatea ca numarul

x

y+y

z+z

xeste natural.

Sa se arate ca produsul xyz este un cub perfect.

Solutie. Vom arata ca pentru orice numar prim p care apare n descompunerea lui

x, y sau z, exponentul cu care p apare n produsul xyz este multiplu de 3, adica

vp(xyz)...3.

Fie a = vp(x), b = vp(y), c = vp(z), a, b, c N si din conditia data rezulta ca

vp

(x

y

)= a b, vp

(yz

)= b c, vp

( zx

)= c a, vp(xyz) = a+ b+ c

si atunci (a b) + (b c) + (c a) = 0.Daca nici o diferenta nu este negativa atunci a = b = c si vp(xyz) = 3a

...3.

Daca diferenta minima este negativa, de exemplu

vp

(x

y

)= a b < 0,

atunci scriem

x

y=y

z=z

x= pabq1 + pbcq2 + pcaq3 = pab(q1 + puq2 + pvq3)

unde q1, q2, q3 sunt numere naturale cu vp(q1) = vp(q2) = vp(q3) = 0 si u 0,v 0.

Daca u > 0 si v > 0 atunci vp

(x

y+y

z+z

x

)= a b < 0 (fals).

Ramane ca u = 0 (sau v = 0) si atunci a b = b c < 0 si a+ b+ c = 3b...3.

Problema 40. Demonstrati ca numarul n! niciodata nu se divide la pn, unde p

este numar prim.

Solutie. Se stie ca exponentul lui p n n! este egal cu

vp(n!) =

[n

p

]+

[n

p2

]+ . . .+

[n

pk

]+ . . .

Evident avem[npj

] npj n2j , inegalitatea fiind stricta pentru j astfel nct 2j > n.

Prin urmare,

vp(n!) 1 deducem p = q deci n = 3k.

29

Problema 49. Daca a b (mod n) atunci an bn (mod n2). Verificati dacareciproca este adevarata.

Solutie. Fie a = b+ cn. Atunci din formula binomului Newton, avem

(b+ cn)n bn =ni=1

(n

i

)bni(cn)i

Primul termen este egal cu nbn1cn, iar toate celelalte se divid la (cn)2, deci anbnse divide la n2. Reciproca nu este adevarata: de exemplu, 34 14 (mod 42), iar3 nu este congruent cu 1 modulo 4.

Problema 50. Cu cte zerouri poate sa se termine numarul

An = 1n + 2n + 3n + 4n, n N?

Solutie. Calculam A0 = 4, A1 = 10, A2 = 1 + 4 + 9 + 16 = 30, A3 = 100. Vom

demonstra ca pentru n , An nu se divide la 8, si astfel nu poate sa se termine n(cel putin) 3 zerouri. Daca n 3, 2n + 4n se divide la 23 = 8, 1n 1 (mod 8).Scriind n = 2k + s, s {0, 1} avem 3n 9k 3s 1k 3s 1, 3 (mod 8). Prinurmare, An 2, 4 (mod 8). Asadar, An se poate termina cu 0, 1 sau 2 zerouri.

Problema 51. (Romania, 2003) Consideram numerele prime x1, x2, . . . , x31 cu

x1 < x2 < . . . < x31 astfel nct x41 + x

42 + . . . + x

431 se divide la 30. Demonstrati

ca ntre cele 31 numere exista trei numere prime consecutive.

Solutie. Divizibilitatea la 30 ne convinge ca numerele 2,3 si 5 ar putea sa fie utile

ntr-o solutie bazata pe comparatii dupa modul. Intr-adevar, se verifica direct ca

pentru orice n Z, n4 este congruent cu 0 sau 1 modulo 2,3 si 5. mpartirea la5. Deci, daca nici unul din numere nu este 2,3 si 5, atunci suma de 31 numere va

avea restul 1 de la mpartirea la 2,3 si 5 respectiv. n fiecare din cazurile acestea

suma nu se va divide la 30, ce contrazice presupunerii.

2.2 Aplicatie: Criterii de divizibilitate.

In acest subcapitol, vom examina cateva cazuri simple a urmatoarei probleme

generale: Fie d un numar natural fix. Sa se deduca un criteriu de divizibilitate

simplu a unui numar natural N la d. Cu alte cuvinte, cautam o metoda rapida

(de exemplu, folosind operatii aritmetice asupra cifrelor lui N), care ne permite sa

30

determinam daca N se divide cu d. Consideram reprezentarea (obisnuita) n baza

10 a lui N : N = anan1 . . . a1a0. Avem N = a0 100 +a1 101 + . . .+an 10n. Fie

100 r0 (mod d)101 r1 (mod d)102 r2 (mod d). . . . . . . . . . . .

10n rn (mod d)

Atunci N Rd (mod d), unde Rd = a0r0 + a1r1 + . . . + anrn (mod d), adicaN se divide cu d daca si numai daca Rd 0 (mod d). In general, aflarea restuluide la mpartirea numarului N la d este echivalenta cu aflarea restului mpartirii

lui Rd la d.

Aflam Rd pentru cteva cazuri particulare.

1. d = 3, atunci pentru orice numar natural k, 10k 1 (mod 3). Intr-adevar,

10k 1 = 99...9 = 9 11...1 = 3 3 11...1 0 (mod 3)

100 1 (mod 3)101 1 (mod 3)102 1 (mod 3). . . . . . . . . . . . . . . . . .

10n 1 (mod 3)R3 = a0 + a1 + . . .+ an.

In acest mod numarul se divide la 3 daca si numai daca a0 + a1 + . . .+ an 0(mod 3). (12).

Inlocuind expresia (12) cu alta echivalenta 3|(a0 + a1 + . . . + an), vom primio formulare renumita a acestui criteriu de divizibilitate: numarul se mparte la 3

daca si numai daca suma cifrelor lui este multiplu de 3.

2. d = 9. Obtinem acelasi criteriu deoarece 10k 1 (mod 9), R9 = a0 + a1 +. . . an.

3. d = 11, atunci

100 1 (mod 11)101 1 (mod 11)

31

102 1 (mod 11). . . . . . . . . . . . . . . . . .

10n (1)n (mod 11)R11 = a0 a1 + a2 a3 + . . .+ (1)nan.

In acest mod, numarul se mparte la 11 daca si numai daca

(a0 + a2 + . . .) (a1 + a3 + . . .) 0 (mod 11).Cu alte cuvinte numarul se mparte la 11 daca si numai daca diferenta dintre

suma cifrelor de pe locuri pare si suma cifrelor de pe locuri mpare este multiplu

de 11.

4. d = 2k. Pentru m k avem 10m = 2m 5m 0 (mod d). Prin urmare,Rd a0 + a1 10 + ...+ ak1 10k1 ak1...a1a0 (mod d).

Deci, un numar N se divide cu 2k daca si numai daca numarul format din ultimele

k cifre ale lui N se divide la 2k.

Problema 52. Fie n = ahah1 . . . a0 un numar ntreg pozitiv. Fie s(n) = ah +ah1 + . . .+ a0. Demonstrati ca: a) n s(n) (mod 3) b) n s(n) (mod 9).

Solutie. In problemele de mai jos vom studia cteva criterii de divizibilitate a

numerelor. Pentru a) si b) vom demonstra ca n s(n) se divide la 9. Intr-adevar, n s(n) = (ah 10h + ah1 10h1 + a0) (ah + ah1 + . . . + a0) =ah (10h 1) + ah1(10h1 1) + . . . + a1 9. Toate numerele de forma 10k 1se divid la 9, deci n S(n) se divide la 9. Solutia aceasta ar putea fi scrisa si cuajutorul congruentelor modulo 9. Atunci afirmatia ca 10k 1 se divide la 9 arnsemna ca 10k 1 (mod 9).

Problema 53. Fie s(n) = a0a1+a2 . . .+(1)hah. Demonstrati ca s(n) n(mod 11).

Solutie. 102 100 1 (mod 11). Mai avem ca 102k+1 10 1(mod11).Atunci 102k 1 (mod 11). De aici rezulta ca n = a0 + a1 10 + . . . + an 10n a0 a1 + a2 . . .+ (1)hah = s(n) (mod 11). Pentru ca puterile pare si imparealterneaza (vin una dupa alta).

Problema 54. Demonstrati ca

ahah1 . . . a0 a2a1a0 a3a4a5 + . . . (mod 7, 11, 13).Deduceti de aici criteriul de divizibilitate la aceste numere.

32

Solutie. Avem 1001 = 7 11 13. Deci 1000 1 (mod 7) (aceeasi congruentaare loc si modulo 11 si 13). ahah1 . . . a0 ahah1 . . . a3 1000 + a2a1a0 ahah1 . . . a3 + a2a1a0. Dar numarul ahah1 . . . a3 tot poate sa fie un numarmare. Daca el are mai mult de 3 cifre, atunci putem sa repetam operatiile de mai

sus. Dupa cteva operatii toate cifrele vor fi situate n blocuri de cte trei cifre n

fiecare. Obtinem deci urmatorul criteriu de divizibilitate la 7, 11 si 13: mpartim

toate cifrele de pe pozitiile cele mai mici n blocuri cte trei cifre n fiecare, luam

primul bloc, scadem dintr-nsul al doilea, adunam al treilea si asa mai departe.

Atunci numarul format va avea acelati rest de la mpartirea la 7, 11 si 13, ca si

numarul initial.

Problema 55. Demonstrati ca numarul ahah1 . . . a0 ahah1 . . . a3 + a2a1a0(mod 27, 37). Determinati criteriul bazat pe proprietatea aceasta de divizibilitate

a numarului la 27 si 37.

Solutie. Procedam ca n problema precedenta: 999 = 27 37, 103 1 (mod 27, 37)de unde afirmatia de mai sus rezulta usor. Criteriul va fi urmatorul: mpartim

toate cifrele ncepnd de la pozitiile cele mai mici n blocuri cte trei cifre n fiecare

si sumam toate blocurile. Atunci suma aceasta va fi congruenta cu numarul initial

modulo 27 si 37.

Solutiile de mai sus ne conving ca pentru fiecare numar natural p exista asa un

criteriu de divizibilitate la p (unde p nu se divide la 2 sau 5): trebuie de mpartit

numarul, ncepnd cu pozitii cele mai mici n blocuri cu cte k cifre (unde k nu e

mai mare dect p 1, de le adunat unul cu altul sau de le scazut unul din altul siatunci suma obtinuta va fi congruenta cu numarul initial dupa modulul p1. Intr-adevar, ntotdeauna exista numarul k pentru care 10k 1 (mod p). De exemplu,10(p) = 1 (mod p), unde (p) este functia lui Euler pentru numarul p. Fie c(p)

- cel mai mic numar natural, pentru care 10c(p) 1 (mod p). Atunci este deajuns de mpartit numere n blocuri cu cte c(p) cifre n fiecare bloc si de le adunat

blocurile. Daca c(p) este un numar par si p e prim, atunci numarul de blocuri

poate sa fie si mai mic, dar criteriul e si mai simplu. 10c(p) 1 (mod p), de aceeasau 10

c(p)2 1 (mod p), sau 10 c(p)2 1 (mod p). Primul caz este imposibil,

pentru ca dupa definitie c(p) e cel mai mic numar natural, pentru care 10c(p) 1(mod p). In cazul al doilea ne ramne sa mpartim deja n c(p)2 blocuri si sa le

adunam si sa le scadem unul dupa altul, ca n problemele 11 si 12.

Mai departe vor fi cteva probleme, care arata importanta criteriilor de diviz-

ibilitate n probleme simple.

33

Problema 56. Determinati numarul pozitiv k pentru care numarul 11 . . . 1, care

are k cifre, este patrat perfect.

Solutie. 1 este patrat perfect. Ne ramne sa demonstram ca pentru orice alt numar

k mai mare dect 1, numarul primit nu este patrat perfet. Intr-adevar, ultimele

doua cifre ale numarului acesta sunt 11. Deci numarul da restul 3 de la mpartirea

la 4. Dar un patrat perfect da numai resturi 0 sau 1 de la mpartire la 4. Obtinem

contradictie.

Problema 57. Poate oare un numarul de 5 cifre, care toate sunt numere pare

distincte, sa fie un patrat perfect?

Solutie. Cifrele numarului atunci vor fi : 2,4,6,8 si 0. Suma lor este 20 si da restul

2 de la mpartirea la 9. Deci nsusi numarul da restul 2 de la mpartirea la 9, ce

este imposibil pentru un patrat perfect, care da resturi 0,1,4,7 de la mpartirea la

9.

Problema 58. Determinati daca numarul 200 . . . 04 (cu 2002 de zerouri) poate

sa fie patrat perfect.

Solutie. Suma cifrelor numarului este 6, ce este imposibil pentru un patrat.

2.3 Teorema fundamentala a aritmeticii

15 demonstratii ale teoremei lui Euclid.

Vom prezenta cititorului o colectie de demonstratii a acestei teoreme. Majoritatea

lor sunt elementare. Pentru intelegerea unora e nevoie de cateva cunostinte de

baza din teoria sirurilor de numere. Pentru a ntelege demonstratiile topologice,

evident, e necesara cunoasterea spatiilor topologice.

Demonstratia 1 (Euclid, sec. III .e.n). Presupunem ca multimea numerelor

prime e finita si p e cel mai mare numar prim. Cercetam numarul k care e cu 1

mai mare decat produsul tuturor numerelor prime:

k = 2 3 5 . . . p+ 1.Deci numarul k nu are divizori primi, deoarece k 1 (mod q), pentru numar

prim q. Cum orice numar natural are cel putin un divizor prim, rezulta contradictia

fata de presupunerea initiala.

34

Demonstratia 2 (Kummer). Ideea demonstratiei lui Euclid consta n gasirea

unui numar natural k care sa nu fie divizibil cu nici un numar prim. Matemati-

cianul german Kummer a schimbat un singur semn n rationamentul lui Euclid:

k = 2 3 5 . . . p 1.De la numere prime ntre ele la numere prime

Demonstratiile din acest subcapitol se bazeaza pe urmatoarea lema elementara:

Lema 1. Daca exista un sir infinit de numere naturale prime ntre ele doua

cate doua, atunci multimea numerelor prime este infinita.

Intr-adevar oricare 2 numere prime ntre ele nu au divizori primi comuni, deci

multimea divizorilor primi a acestor numere e infinita.

Demonstratia 3 (Sylvester). Sa cercetam sirul (an), definit astfel:

a1 = 2, ak+1 = a2k ak + 1, k N

Primii cativa termeni ai acestui sir sunt: 2, 3, 7, 43. Demonstram prin inductie

ca n N , are loc egalitatea:an+1 = a1 a2 . . . an + 1

Baza inductiei e evidenta. Iar

ak+2 = a2k+1 ak+1 + 1 = ak+1 (ak+1 1) + 1 = ak+1akak1 . . . a2a1 + 1.

Din (1) rezulta ca oricare 2 termeni ai sirului Sylvester sunt primi ntre ei.

Demonstratia 4 (Goldbach). Fie an = 22n + 1, . . .. Demonstram ca oricare

doua numere ale sirului

3, 5, 17, . . ., 22n

+ 1

sunt prime ntre ele. 1

Presupunem ca exista n si k astfel ncat n > k si an si ak nu sunt prime ntre ele,

adica au un divizor comun d mai mare ca 1. Sa observam ca toate numerele sunt

impare, deci d > 2. Insa are loc urmatoarea relatie, foarte usor de demonstrat, de

altfel:

(1 + 2)(1 + 22)(1 + 222

) . . . (1 + 22n1

) = 22n 1.

Astfel an2 = 22n1 se divide la ak, deci si la d. Dar atunci si 2 = an(an2)este divizibil cu d, ceea ce este imposibil.

1Termenii acestui sir se numesc numerele lui Fermat, care a observat ca pentru n = 0, 1, 2, 3, 4,

termenii corespunzatori sunt primi, si a presupus ca toti termenii vor fi primi. A gresit, a5 fiind

numar compus. Mai mult de atat, nu se cunoaste nici un numar Fermat, cu n > 4, care sa fie

prim.

35

Demonstratia 5. Sa aratam o metoda generala de construire a sirurilor cu

termeni primi ntre ei. Aceste siruri de mai sus sunt cazuri particulare.

Fie a si b doua numere prime ntre ele. Vom construi sirul (an) n modul

urmator:

a1 = a, ak+1 = a1a2 . . . ak + b.

Sa observam ca sirurile din exemplele anterioare sunt determinate de a = 2, b =

1 si a = 1, b = 2, respectiv.

Demonstram ca oricare 2 elemente ale sirului an sunt prime ntre ele. Fie n > k.

Atunci

an b = a1a2 . . . an1e divizibil cu ak. Fie d un divizor comun al numerelor an si ak. Din

an... d si (an b)

... d,

urmeaza b... d. Fie ca numerele a1, a2, . . . , ak sunt prime ntre ele. Fie d > 1

un oarecare divizor al numarului ak+1. Vom arata ca d nu divide nici unul din

numerele a1, . . . ak. Presupunem contrariul. Fie i cel mai mic numar astfel ncat

ai... d. Daca i > 1 atunci

ai = a1a2 . . . ai1 + b... d,

si deoarece b... d, iar a1, a2, . . . ai1 sunt prime ntre ele, nsa produsul lor se

divide cu d, deci unul dintre aceste numere e divizibil cu d, ceea ce contrazice

minimalitatea lui i. Daca i = 1, atunci a1 = a este divizibil cu d, care contrazice

(a, b) = 1.

Demonstratia 6. Extinderea sirului Sylvester poate fi facuta si n alt mod.

Fie a1 = a 2 si ak+1 = 1+ak(ak1)bk, unde (bn) este un sir arbitrar de numerenaturale. Sa observam ca sirul Sylvester se obtine luand a = 2, bn = 1.

O problema din cea de-a XII-a Olimpiada a Uniunii Sovietice a fost urmatoarea:

Fie f(x) = x3 x + 1, a > 1 - un numar natural. Aratati ca termenii sirului a,f(a), f(f(a)), f(f(f(a))), . . . sunt oricare doi primi ntre ei.

Este usor de observat ca punand n constructia specificata mai sus bk = ak + 1 se

obtine sirul din problema. Sa aratam ca sirul an are toti termenii primi ntre ei

(oricare doi). Intr-adevar, daca m > k, atunci avem: am1... am11

... am21...

. . .... ak+11

... ak, de unde rezulta am 1 (mod a)k, deci numerele am si ak suntprime ntre ele.

Pentru urmatoarea demonstratie ne va fi de folos urmatorul rezultat:

Lema 2. Fie k > 1, a si b - numere naturale. Atunci are loc:

36

(ka 1, kb 1) = k(a,b) 1.

Sa precautam initial cazul cand a este multiplu de b. Atunci pentru un careva

q avem a = bq si (a, b) = b. Relatia ia forma (ka1, kb1) = kb1. Insa aceastarelatie are loc, deoarece ka1 este multiplu de kb1. Acest fapt rezulta din aceeaca a este multiplu de b. Fie ca a nu este multiplu de b, deci a = bq + r, 0 < r < b.

Avem ka 1 = kbq+r 1 = kr(kbq 1) + kr 1. Deci restul mpartirii lui ka 1la kb 1 este kr 1. Deci (ka 1, kb 1) = (kb 1, kr 1). Repetand algoritmul:a = bq0 + r1, b = r1q1 + r2, r1 = r2q2 + r3, . . . rn2 = rn1qn1 + rn, rn1 = qnrn,obtinem sirul de egalitati: (ka 1, kb 1) = (kb 1, kr1 1) = (kr1 1, kr2 1) =. . . = (krn1 1, krn 1) = krn 1 = k(a,b) 1.

Corolar. Daca m si n sunt prime ntre ele, atunci 2m 1 si 2n 1 sunt primentre ele. Reciproca este, de asemenea, adevarata.

Demonstratia 7 (Holsinschii, 1994) Presupunem ca F = {n1, n2, . . . nk} estemultimea tuturor numerelor prime (n1 = 2, n2 = 3, n3 = 4, . . .). Evident ca

numerele din F sunt prime ntre ele doua cate doua. Deci pentru i 6= j, numerele2ni 1 si 2nj 1 de asemenea sunt prime ntre ele. Sa luam pentru fiecarei = 1, 2, . . . , k un careva divizor prim al lui 2ni 1. Numerele p1, p2, ..., pk vor fidoua cate doua diferite. Deci multimea acestor numere G coincide cu F . Dar G

nu contine numere pare, deci nu l contine pe 2, ceea ce este imposibil.

Cand un numar are multi divizori primi

Construirea unui sir (an), pentru care numarul de divizori primi ai termenilor

sirului creste nemarginit odata cu n, conduce la noi demonstratii ale teoremei lui

Euler.

Demonstratia 8 Sa demonstram ca numarul an = 22n + 22

n1+ 1 are nu mai

putin de n divizori primi diferiti.

In identitatea x4 + x2 + 1 = (x2 x+ 1)(x2 + x+ 1), punem x = 22n1 . Obtinem:

an+1 = 22n+1 + 22

n

+ 1 = (22n

+ 1 22n1)(22n + 1 + 22n1) = (22n 22n1 + 1)an.

Deci an+1... an. Numerele 2

2n 22n1 + 1 si an = 22n + 22n1 + 1 sunt prime ntreele. Fiindca daca ar avea un divizor (impar!) comun diferit de 1, acesta ar divide

si diferenta celor 2 numere, care este 22n1+1, imposibil. Rezulta ca la trecerea

de la n la n+ 1 numarul de divizori primi creste. Ceea ce nseamna ca an are cel

putin n divizori primi diferiti.

37

Demonstratia 9 Fie P (x) un polinom cu coeficienti ntregi. Vom numi numarul

k divizor al polinomului P (x), daca pentru careva numar natural n, numarul P (n)

se divide la k. Sa demonstram ca printre divizorii polinomului P (x) exista o in-

finitate de numere prime.

Presupunem contrariul. Fie p1, p2, . . . ps acesti divizori primi. Fie P (a) = b 6= 0.Consideram polinomulQ(x) = P (a+bp1p2 . . . psx)/b. Deoarece P (a+bp1p2 . . . psx)P (a)

... bp1p2 . . . ps, avem Q(x) 1 = P (a+bp1p2...psx)P (a)b... bp1p2 . . . ps. Deci nu-

merele p1, p2, . . . ps nu sunt divizori ai lui Q(x). Polinomul Q(x) ca orice polinom

neconstant nu ia nici o valoare de o infinitate de ori. De aceea, printre valorile lui

exista si unele diferite de -1, 0 si 1, respectiv el are divizori primi. Insa oricare

divizor prim al lui Q este si divizor prim al lui P , fiindca pentru t = a+bp1p2 . . . ps,

are loc egalitatea P (t) = bQ(x). Rezulta ca polinomul P are divizori primi diferiti

de p1, p2, ..., pn. Contradictie.

In particular, pentru orice progresie aritmetica an = a1 + (n 1)d, cu d 6= 0 sia Z, multimea divizorilor primi ai ei este infinita.O cunoscuta teorema a lui Dirichlet se enunta astfel: daca a1 si d sunt numere

prime ntre ele, atunci printre termenii progresiei aritmetice cu primul termen a1

si ratia d exista o infinitate de numere prime2. In urmatoarele demonstratii vom

analiza cateva cazuri simple ale acestei teoreme.

Cateva cazuri ale teoremei lui Dirichlet

Demonstratia 10 Exista o infinitate de numere prime de forma 3n+ 2.

Presupunem ca nu este asa. Fie p1 = 2, p2 = 5, p3 = 11, . . . ps - toate numerele

prime de forma din enunt. Consideram numarul k = 3p1p2 . . . ps1. Evident k nuse divide nici la 3, nici la numerele p1, p2, . . . ps. Rezulta ca toti divizorii lui primi

dau restul 1 la impartirea la 3, de unde rezulta ca si k da restul 1 la impartirea la

3, ceea ce este imposibil.

Este evident ca daca un numar prim mai mare ca 2 are forma 3n + 2, atunci n

este impar, si deci numarul prim are forma 6n+ 5.

Demonstratia 11 Exista o infinitate de numere prime de forma 6n+ 1.

Mai ntai sa aratam urmatoarea lema:

2Sa mentionam ca pentru orice polinom P (x) de grad mai mare ca 1, nu a fost demonstrat ca

printre numerele P (n), n N sunt o infinitate de numere prime. Dar polinomul de doua variabileax2 + bxy + cy2, unde a, b si c numere prime ntre ele contine printre valorile lui o infinitate de

numere prime

38

Lema 3 Orice divizor prim p > 3 al polinomului x2 +x+1 are forma p = 6n+1

Intr-adevar, daca p = 3k + 2 si x2 + x + 1... p, atunci x3 1 (mod p). Ridicand

ambele parti ale egalitatii la puterea k obtinem xp2 1 (mod p), adica xp1 x(mod p). Insa din teorema mica lui Fermat avem ca xp1 1 (mod p). Contradictie.Acum fie p1 = 7, p2 = 13, . . . , ps toate numerele prime de forma 6n + 1. Fie

m = p1 . . . ps si k = m2 + m + 1. Cum m nu se divide cu nici unul din numerele

p1, p2, . . . , ps, si conform lemei, k are doar divizori primi de forma 6n+ 1, obtinem

o contradictie.

Lema 4 Fie m si p - doua numere prime diferite. Daca p divide pe xm1 +xm2 + . . .+ x+ 1, unde x N, atunci p 1 (mod m).Fie p = mk + r, unde r {1, 2, . . .m 1}. Trebuie sa demonstram ca r = 1. Dinconditie rezulta imediat ca

xm 1 (mod p),deci x nu se divide la p. Sa aratam mai ntai ca xr1 1 (mod p). Intr-adevar,din teorema mica a lui Fermat, avem:

1 xp1 xmk+r1 (xm)kxr1 xr1 (mod p).

Presupunem ca r > 1. Folosind Lema 2, avem p = (xm 1, xr1 1) = x(m,r1),care este egal cu x 1, deoarece m este prim. Rezulta ca x 1 (mod p). De aicirezulta ca P (x) = xm1 +xm2 + . . .+x+1 m (mod p). Dar din conditie avemP (x) 0 (mod p). Rezulta ca m se divide la p, ceea ce este imposibil. Rezulta car = 1.

Demonstratia 12 Exista oricat de multe numere prime de forma mn+ 1, unde

m este un numar prim.

Sa consideram polinomul P (x) =m1i=0 x

i. Fie p1, p2, . . . , ps - toate numerele

prime de forma mn + 1. Fie k = P (p1p2 . . . ps). Folosind lema 4, oricare divizor

prim q al numarului k are forma q = mn + 1. Dar totodata q este diferit de

numerele p1, p2, . . . ps, deoarece k 1 (mod p)i, i {1, 2, . . . , s}. Contradictie.Demonstratii combinatoriale

Demonstratia 13 Fie 2n > (1+n)m. Demonstram ca printre numerele 1, 2, 3, . . . , 2n

exista cel putin m+ 1 numere prime.

Presupunem ca printre 1, 2, 3, . . . , 2n exista s m numere prime: p1, p2, . . . ps.Atunci fiecare numar care nu depaseste 2n, se poate reprezenta sub forma: pk11 p

k22 . . . p

kss ,

si evident, fiecare exponent poate fi si 0, si totodata nu-l depaseste pe n. Insa

39

asemenea numere sunt (1 + n)s la numar, si (1 + n)s este mai mic decat 2n.

Contradictie caci pentru orice m exista un careva n suficient de mare ca 2n >

(1 + n)m.

Demonstratia 14 Sa demonstram mai intai ca printre numerele {1, 2, . . . , n}nu mai putin de un sfert sunt libere de patrate (adica nu se divid la nici un

patrt perfect diferit de 1).3 Printre numerele {1, 2, . . . , n} avem nu mai multde np2 numere care se divid la p

2. De aceea numarul de numere care se divid la

patratul unui numar prim nu este mai mare decat:pn

np2 1.Contradictie.

8. Divizorii unui numar.

Problema 59. a) Demonstrati ca daca produsul unor numere, prime ntre ele

doua cte doua, este patrat perfect, atunci fiecare din numerele acestea e un patrat

perfect.

b) Generalizati acest rezultat pentru orice putere naturala (k 3).3Sa mentionam ca este cunoscut faptul urmator: numarul de numere libere de patrate din

multimea {1, 2, . . . , n}, cand n , tinde spre 6pi2n = 0, 6079 . . . n.

40

Solutie. a) Presupunem, ca unele din numerele acestea nu sunt patrate perfecte.

Atunci produsul lor trebuie sa fie patrat perfect. Presupunem ca unul din numere

este egal cu mn2 unde n2 este patat perfect, dar m nu este patrat si n-are ntre

divizorii sai patrate perfecte, diferite de 1. Pentru ca produsul total sa fie patrat

perfect este necesar, ca produsul tuturor membrilor ramasi sa se divida la m.

Dar membrii ramasi sunt reciproc primi cu numarul mn2, deci nu se divid cu m.

Obtinem contradictie.

b) Solutia e analoaga.

Problema 60. Demonstrati ca numarul 1986! nu este patrat perfect.

Solutie. Vom arata ca numarul acesta se divide la o putere impara a lui 3. Intr-

adevar, puterea lui 3 este egala cu urmatoarea expresie: [ 19863 ]+[198632 ]+. . .+[

198636 ].

Ea este impara, deci numarul 1986! nu poate sa fie un patrat perfect.

Problema 61. Aflati toate numerele naturale mai mici dect 300 care au exact

15 divizori.

Solutie. Vom folosi faptul ca numarul reprezentat sub forma pq11 pq22 . . . p

qnn are ex-

act (q1 + 1)(q2 + 1) . . . (qn + 1) divizori. Intr-adevar, orice divizor este de forma

pr11 pr22 . . . p

rnn unde fiecare numar ri poate sa aiba qi + 1 valori diferite de la 0 pna

la qi independent de alti rj . Daca un numar are 15 = 3 5 divizori, atunci numarulacesta va fi egal cu p2q4 sau p14. 214 > 300 deci numarul poate avea numai forma

p2q4. Vom gasi toate numerele de tipul acesta mai mici dect 300. Presupunem,

ca q este egal cu 2. Vom cauta toate numerele de forma 16p2, mai mici dect 300,

unde p este un numar prim diferit de 2. p nu poate sa fie mai mare dect 4, fiindca

atunci numarul obtinut ar depasi 300. Unicul numar prim ce nu depaseste 4 este 3

(2 nu poate fi caci q = 2). Deci obtinem numarul 144. Presupunem, ca q este egal

cu 3. Vom cauta toate numerele de forma 81p2 mai mici dect 300, unde p este

un numar prim diferit de 3. Dar deja pentru p egal cu 2, numarul final depaseste

300. Cu att mai mult pentru q > 3 avem p2q4 > 4 34 > 300. Deci 144 e unicasolutie.

Problema 62. Se stie ca un numar natural n are exact 1982 de divizori naturali.

Poate oare n sa se divida cu 66?

Solutie. Consideram descompunerea n factori primi a lui n

n = pq11 pq22 . . . p

qkk

41

Atunci conditia din enunt se scrie

1982 = (q1 + 1)(q2 + 1) . . . (qk + 1) = 2 991,

ceea ce implica k 2 caci 2 si 991 sunt numere prime. Insa daca n ar fi divizibil cu66, el ar avea cel putin 3 divizori primi (2,3,11) deci am avea k 3, contradictie.

Problema 63. Cte solutii n numere naturale are ecuatia 1x +1y =

11980?

Solutie. Ecuatia aceasta poate fi exprimata astfel: 1980x+ 1980y = xy

xy 1980x 1980y + 19802 = 19802 (x 1980)(y 1980) = 19802.

Deoarece 19802 = 243452112, avem ca 19802 are (4 + 1)(4 + 1)(2 + 1)(2 + 1) = 225

divizori (naturali). Fiecare din divizorii acestia da o solutie posibila, daca este

nlocuit cu x 1980. Deci avem 225 de solutii ale acestei ecuatii.

2.4 Sisteme complete de resturi modulo m.

Categoriile dupa un modul dat.

Sa unim toate numerele ntregi care la mpartirea la un numar natural dat m dau

acelasi rest r ntr-o categorie si sa o notam Cr.

Deoarece sunt m resturi posibile la mpartirea la m: 0, 1, 2, . . . ,m 1, toatenumerele ntregi dupa acest modul se mpart in m categorii: C0, C1, . . . , Cm1.

Toate numerele unei si aceiasi categorii sunt congruente dupa modulul m si se

numesc rezultantele categoriei date, iar categoriile nsele - categoriile rezultantelor

dupa modulul m. Evident ca doua numere din categorii diferite nu sunt congruente

dupa modulul m. Categoria rezultantelor Cr este compusa din numere de forma

mt+r, unde r e constant, iar t ia toate valorile ntregi posibile. De exemplu pentru

m = 5 formula generala a numerelor:

C0 = {5t|t Z};C1 = {5t+ 1|t Z};C2 = {5t+ 2|t Z};C3 = {5t+ 3|t Z};C4 = {5t+ 4|t Z};

De exemplu n categoria C3 intra numerele . . ., 12, 7, 2, 3, 8, 13, 18, . . .

42

Sisteme complete de resturi.

Daca din fiecare categorie modulo m sa luam cte un reprezentant, atunci vom

primi un sistem de numere, numit sistem complet de rezultante dupa modulul m.

De obicei n calitate de reprezentant al categoriei se iau rezultantele cele mai mici

nenegative, obtinute din formula generala a rezultantelor categoriei date, adica

din Cr se ia numarul r. Atunci sistemul complet de rezultante minime nenegative

dupa modulo m are forma 0, 1, 2, . . . ,m 1. De exemplu 0, 1, 2, 3, 4 e sistemulcomplet de rezultante minime nenegative modulo 5.

Daca din fiecare categorie luam rezultanta avnd cea mai mica valoare absoluta,

atunci vom primi un sistem complet de rezultante minime absolute. De exemplu

0, 1, 2,-2,-1 e sistem complet de rezultante minime absolute modulo 5.

Exercitii.

Problema 64. In cte zerouri se termina numarul 9999 + 1?

Solutie. Avem 92 81 1 (mod 10),9999 + 1 9 (92)449 + 1 0 (mod 10)

Numarul se termina cu cel putin un zero. Iar

9 1 (mod 4)9999 + 1 1 + 1 2 (mod 4)

Deci, numarul nu poate sa se termine cu mai mult de un zero.

Problema 65. Exista oare un numar natural n asa ca numarul 3n+1 sa se divida

cu 10100?

Solutie. Aratam ca numarul 3n + 1 nu se divide cu 8. 32 1 (mod 8). De aiciobtinem ca 3n poate sa dea sau restul 1 sau restul 3 la mpartirea cu 8, deci 3n+ 1

poate sa dea numai restul 2 sau 4 la mpartirea cu 8. Adica el nu se divide cu

8.

Problema 66. Rezolvati n numere naturale ecuatia x2 + y2 = 19861986.

Solutie. Observam resturile de mpartirea la 9 a patratelor.

1 1 (mod 9) 4 4 (mod 9)9 0 (mod 9) 16 7 (mod 9)25 7 (mod 9) 36 0 (mod 9)

43

49 4 (mod 9) 64 1 (mod 9)81 0 (mod 9)

Prin urmare, x2 + y2 poate fi congruent cu 0, 1, 2, 4, 5, 7, 8 la mpartirea cu 9.

Deoarece 19861986 3 (mod 9), conchidem ca ecuatia nu are solutii n numerenaturale.

Problema 67. Rezolvati n numere naturale ecuatia 105x + 211y = 106z.

Solutie. Lund dupa modulul 8, avem 105x 1 (mod 8), 211 3 (mod 8) 211y 1, 3 (mod 8) Atunci 105x + 211y 2 (mod 8) pentru y impar, si 105x +211y 4 (mod 8) pentru y par. Obtinem ca z 2 (fiindca pentru z > 2, 106zse divide la 23 = 8). Se verifica usor ca pentru z = 0 nu avem solutii, pentru

z = 1 avem doar solutia x = 1, y = 0. Pentru z = 2, avem y = 0 sau y = 1

(fiindca y < z). In primul caz nu avem solutii (1053 > 1062 1 > 1052), iar ncazul y = 1 obtinem x = 2. Asadar, ecuatia are doua solutii: x = z = 1, y = 0 si

x = z = 2, y = 1.

Problema 68. Demonstrati ca produsul p1p2 . . . pn al primelor n numere prime

nu poate sa fie cu 1 mai mare sau mai mic dect un patrat perfect.

Solutie. Acest produs este evident divizibil cu 2 dar nu cu 4. Deoarece x2 1 0,1 (mod 4), conchidem ca p1p2 . . . pn nu poate fi cu 1 mai mic dect un patratperfect. Mai observam ca pentru n > 1 p1p2 . . . pn se divide cu 3, iar x

2 + 1 nu

poate fi divizibil cu 3.

Observatie. Mai trziu vom vedea ca, n general, x2 + 1 nu poate avea divizori

de forma 4k + 3.

Problema 69. Rezolvati ecuatia 2n + 8n+ 5 = k2 n numerele naturale.

Solutie. Un patrat perfect poate fi congruent doar cu 0, 1 sau 4 modulo 8. Pentru

n > 2, 2n + 8n+ 5 5 (mod 8), deci n acest caz nu avem solutii. Pentru n 2,prin calcul direct determinam singura solutie n = 2, k = 5.

2. Fie 0 < k < n numere naturale. Sa se arate ca din orice succesiune de n

numere naturale consecutive se pot extrage doua al caror produs este divizibil cu

k n.Solutie. Fie An = {a + 1, a2, . . . , a + n} o multime de n numere naturale

consecutive. Exista un singur i {1, 2, . . . , n} astfel ca n|a+ i si exista un singur

44

j {1, 2, . . . , k} astfel ca k|a + j. Daca i 6= j atunci nk|(a + i)(a + j) si amterminat.

Daca i = j, notam (k, n) = d si [k, n] = m si atunci n k = d m.Vom cauta acum doua numere din An, unul sa se divida cu d si altul cu m.

Deoarece k|a + i si n|a + i rezulta m|a + i si astfel unul din numerele alese estea+ i.

Fie n = db, k = dc cu (b, c) = 1 si din k < n rezulta b < c si k+ d = d(b+ 1) dc = n deci i+ d k + d n si al doilea numar este a+ i+ d (d|a+ i+ d).

Problema 70. Demonstrati ca ecuatia x3 + y3 = 4(x2y + xy2 + 1) nu are solutii

n numere naturale.

Solutie. Presupunem ca ecuatia are solutii. Fie p = x+ y, q = xy. Atunci ecuatia

de mai sus se scrie

p(p2 3q) = 4(pq + 1) p3 4 = 7pq p3 4 (mod 7).

Pe de alta parte, se verifica usor ca x3 0,1 (mod 7) (ntrucat 7 = 2 3 + 1,acest fapt rezulta imediat si din teorema lui Fermat). Contradictie.

Problema 71. Rezolvati ecuatia 1 + xy = z n numere prime.

Solutie. Observam ca x si z au paritati diferite, si cum ele sunt prime, unul din

ele trebuie sa fie 2. Daca z = 2, atunci x = 1, imposibil. Deci x = 2 si 1 + 2y = z.

Observam ca pentru y impar 2y (1)y 1 (mod 3) 3 | 1 + 2y. Decipentru y impar, y > 1, 2n + 1 este un numar compus. Prin urmare, y este par, si

atunci obtinem singura solutie x = y = 2, z = 5.

Problema 72. Demonstrati ca sirul de numere 42 +1, 142 +1, 242 +1, 342 +1, . . .

contine o infinitate de numere compuse.

Solutie. Orice membru al sirului poate fi exprimat astfel: A = (10m + 4)2 + 1 =

100m2+80m+17, deci daca m se divide cu 17, atunci si A se divide cu 17 (evident

A > 17) si este numar compus.

Problema 73. Demonstrati ca numerele 2m si 2n nu pot contine aceleasi cifre n

scrierea zecimala (fiecare cifra se considera de attea ori de cte apare n scrierea

numarului), daca m > n si m,n N.

45

Solutie. Daca numerele 2m si 2n au acelasi set de cifre, atunci ele au acelasi numar

de cifre, ce poate fi numai daca unul din aceste numere este nu mai mult de 10 ori

mai mare dect altul. Deoarece un numar da acelasi rest la mpartirea cu 9 ca si

suma cifrelor sale, deducem 2m 2n (mod 9) deci 9|2m 2n = 2n(2mn 1) deci9|2mn 1. Deoarece am stabilit ca un numar e cel mult dect de 10 ori mai maredet altul, deducem 2mn 10 deci m n = 3, sau m n = 1, sau m n = 2.Insa 9 nu divide nici 2 1 nici 22 1, contradictie.

Problema 74. Exista oare un multiplu de 11, cifrele lui fiind 1,2,3,4,5,6 ntr-o

anumita ordine?

Solutie. Reamintim criteriul de divizibilitate cu 11: A = akak1 . . . a0 se dividela 11 daca si numai daca (1)kak + (1)k1ak1 + . . .+ a0 se divide la 11, adicasuma cifrelor de pe pozitii pare da acelasi rest ca suma cifrelor de pe pozitii impare

modulo 11. Deci daca numarul stipulat n conditiile problemei exista, atunci exista

o permutare a, b, c, d, e, f a numerelor 1, 2, 3, 4, 5, 6 astfel nct 11 | a+ b+ c de f . Cum a + b + c + d + e + f = 1 + 2 + 3 + 4 + 5 + 6 = 21, rezulta caa+ b+ c d e f = 21 2(d+ e+ f) este impar si mai mic dect 21 n modul,deci a+ b+ c d e f = 11, caz n care obtinem a+ b+ c = 5, d+ e+ f = 16sau a+ b+ c = 16, d+ e+ f = 5. Deoarece 5 nu poate fi scris ca suma a 3 numere

diferite dintre 1,2,3,4,5,6 raspunsul problemei este negativ.

Problema 75. Se divide oare numarul A = 192021 . . . 7980 la 1980?

Solutie. 1980 = 20 9 11. A se divide evident la 20. Suma cifrelor lui A este1+8+10(2+3+4+5+6+7)+6(0+1+2+ . . .+9) = 9+270+270 se divide la 9,

deci A se divide la 9. Suma cifrelor de pe pozitii impare minus suma cifrelor de pe

pozitii pare este 1+8+10(2+3+4+5+6+7)6(0+1+2+. . .+9) = 0+270270 = 9deci nu se divide la 11. Adica A nu se divide la 11 deci nici la 1980.

Problema 76. Demonstrati ca suma cifrelor numarului 1981n nu e mai mica dect

19, pentru orice n natural.

Solutie. Fie A suma cifrelor de pe pozitii pare si B suma cifrelor de pozitii impare

ale numarului 1981n. Deoarece 9 11 | 1980, 1981n 1 (mod 9) 11. Deci 9 |A+B 1, 11 | AB 1. Evident A+B 6= 1, altfel 1981n ar fi o putere a lui 10.Daca A+B = 10 atunci AB 1 este ntre 11 si 9. Deoarece 11 | AB 1,avem A B 1 {11, 0}. Pentru A B 1 = 11 obtinem A = 0, imposibilfiindca ultima cifra a lui 1981n este nenula. Pentru AB 1 = 0 iarasi obtinem

46

contradictie, fiindca AB 1 = 9 2B este impar. Prin urmare, A+B 6= 10, siatunci 9 | A+B 1 implica 18 A+B 1 A+B 19.

Observatie. Pentru n = 1, suma cifrelor lui 1981 este 19. Exista oare si alte

valori ale lui n cu aceasta proprietate?

Problema 77. Demonstrati ca suma divizorilor numarului n se divide la 24, daca

se stie ca n+ 1 se divide la 24.

Solutie. Deoarece n 1 (mod 3), n are un divizor prim p ce da rest 1 modulo3 si apare la exponent impar n n (altfel n ar da rest 1 modulo 3). Atunci toti

divizorii lui n se mpart n perechi (a, ap) unde p apare la putere para n a. Suma

divizorilor din fiecare grup este a(p+ 1) deci se divide la 3, adica suma divizorilor

lui n se divide la 3. Cu divizibilitatea la 8 este mai greu. Analog ca si pentru 3,

exista un numar prim p congruent cu -1 modulo 4 care apare la exponent impar.

Atunci divizorii lui n se mpart n perechi (a, ap) unde p apare la exponent par n

a. Suma numerelor n fiecare pereche se divide la p + 1 deci la 4. Daca p + 1 se

divide la 8, problema e rezolvata. Altfel, p 3 (mod 8) deci np2k+1

5 (mod 8),adica n mai are un divizor prim impar q 6= p care apare la putere para n n caciun patrat perfect nu poate da restul 5 modulo 8. Deci toti divizorii se mpart n

cvartete (a, pa, qa, pqa) unde p si q apar la puteri pare n a. Suma numerelor n

fiecare cvartet este (p+ 1)(q + 1)a deci se divide la 8.

O solutie diferita dar similara poate fi data folosind formula explicita a sumei

divizorilor: daca n =mi=1 p

ii atunci suma divizorilor lui n este

mi=1(1 + pi +

. . .+ pii ). Unul din factorii 1 + pi + . . .+ pii se divide la 3 pentru ca unul din pi

e -1 modulo 3 cu i impar. La fel 1 + pi + . . .+ pii unul din se divide la 4 pentru

ca unul din pi este 1 modulo 4 si apare la putere para. Daca pi este 1 modulo8 atunci 1 + pi + . . .+ p

ii se divide la 8, iar daca nu, mai avem un pj care apare

la putere impara deci 1 + pj + . . .+ pjj se divide la 1 + pj deci la 2 pentru j 6= i.

In orice caz,mi=1(1 + pi + . . .+ p

ii ) se divide la 3 si la 8, deci la 24.

Problema 78. E posibil oare ca

a) 5n 1 sa se divida la 4n 1,b) 7n 1 sa se divida la 6n 1?

Solutie. a) Daca n este par, atunci 4n1 (1)n1 0 (mod 5), deci 5n1 nuse divide la 4n1, fiindca nu se divide la 5. Daca n este impar atunci 5n1 2(mod 3), iar 4n 1 0 (mod 3). Deci, 4n 1 nu poate divide pe 5n 1.

47

b) Daca n este par atunci 6n 1 se divide la 7, si atunci nu poate divide pe7n 1. Daca n este impar atunci 6n 1 se divide la 5, iar cum 72 1 (mod 5),deducem ca 7n 7 (mod 5), deci 7n 1 nu se divide la 5, si prin urmare, nicila 6n 1.

Problema 79. Care numere de forma 99 . . . 9 pot fi reprezentate ca suma a doua

patrate perfecte?

Solutie. Analizam resturile de la mpartirea numarului format din n cifre de 9 la

4. Se stie ca suma a doua patrate perfecte trebuie sa dea restul 0,1 sau 2 modulo 4.

Daca n = 1, atunci numarul poate fi reprezentat ca 9 = 02 + 32. Daca n este mai

mare dect 1, atunci 9 . . . 9 da restul 3 modulo 4 deci nu poate fi reprezentat.

Problema 80. Pentru care n numarul 22 . . . 2 n cifre

poate fi exprimat ca a) diferenta

a doua patrate b) suma a doua patrate?

Solutie. a) Conditia necesara si suficienta ca un numar sa poata fi reprezentat

ca diferenta patratelor este ca numarul acesta sa fie impar sau sa se divida la 4.

Faptul acesta putem sa-l deducem din formula a2 b2 = (a b)(a+ b). Daca a si bau aceeasi paritate, atunci diferenta a2 b2 se divide cu 4, n caz contrar diferentaeste impara. Reciproc 4k = (k+ 2)2 (k 2)2 iar 2k+ 1 = (k+ 1)2 k2. Cum unnumar format numai din cifre de 2 da rest 2 modulo 4, el nu poate sa fie diferenta

a doua patrate.

b) Pentru n = 1 avem 2 = 12 + 12. Pentru n 2, analiznd ultimile trei cifreale numarului 22 . . . 2

n cifre

, deducem ca el este congruent cu 6 modulo 8. Pe de alta

parte, orice patrat da restul 0,1 sau 4 modulo 8 si atunci, suma a doua patrate

poate sa dea restul 0,1,2,4 sau 5 modulo 8. Prin urmare, doar n = 1 satisface

conditiile din enunt.

Problema 81. Demonstrati ca exista un numar infinit de numere naturale care

nu pot fi reprezentate ca a) suma a doua cuburi b) suma a trei cuburi.

Solutie. Se verifica usor ca un cub perfect poate sa dea numai resturile 0,1 sau 8 la

mparatirea cu 9. Atunci suma a doua cuburi da restul 0,1,2,7 sau 8 la mpartirea

9, iar suma a trei cuburi restul 0,1,2,3,6,7 sau 8 la mpartirea cu 9. Deci numerele

cu rest 4 sau 5 modulo 9 nu pot fi exprimate ca suma a doua sau a trei cuburi

perfecte.

48

Problema 82. Demonstrati ca numarul

A = 1 0 . . . 0 46 cifre

6 0 . . . 0 97 cifre

1

nu este cub perfect.

Solutie. Se verifica usor ca orice cub perfect este congruent cu 0,1 (mod 7).Avem

103 1 (mod 7), 106 = (103)2 1 (mod 7) 1098 = 102 (106)16 2 (mod 7), 10147 = 103 (106)24 1 (mod 7).

Atunci A = 10147 + 6 1098 + 1 1 + 6 2 + 1 5 (mod 7), deci A nu poate ficub perfect.

Problema 83. Aflati minimul expresiei |36k 5l| unde k, l N.

Solutie. Considernd expresia din enunt succesiv modulo 4,5,6 se observa ca

|36k 5l| 1 (mod 4, 5, 6)

Cele mai mici numere naturale care satisfac aceste conditii sunt 1,11. Aratam

acum ca nu putem avea |36k5l| = 1. Presupunnd contrariul, avem 36k = 5l1.Considernd ecuatia modulo 5, obtinem 36k = 5l + 1. Acum, lund ambele parti

modulo 7, obtinem 1 5l + 1 7 | 5l, imposibil. In final, ntruct 11 = 36 52,raspunsul problemei este 11.

Problema 84. Sa se determine toate numerele n N pentru care a) 6n 5n, b)7n 6n este patrat perfect.

Solutie. a) Pentru n 2 avem 6n 5n 0 1 = 1 (mod 4), iar orice patratperfect este congruent cu 0 sau 1 modulo 4. Ramne numai cazul n = 1 pentru

care 6n 5n = 1 este patrat perfect.b) Pentru n impar, n 3 avem 7n 6n 1 0 = 1 (mod 8), pe cnd

un patrat perfect poate fi congruent doar cu 0,1 (mod 8). Pentru n par, avem

7n 6n 1 (mod 7), iar un patrat perfect poate avea numai restul 0,1,2 sau 4modulo 7. Ramne numai cazul n = 1, pentru care 71 61 = 1 este patrat.

Problema 85. a) 6 numere prime reprezinta membrii consecutivi a unei progre-

sii aritmetice. Demonstrati a ratia acestei progresii nu este mai mica dect 30.

b) 15 numere prime reprezinta membrii consecutivi a unei progresii aritmetice.

Demonstrati ca ratia nu este mai mica dect 40000.

49

Solutie. a) Fie d ratia progresiei aritmetice. Daca d ar fi impar, 3 din aceste

numere ar divide cu 2, ce este imposibil. De aceea d se divide cu 2. Daca d nu

s-ar divide cu 3, doua din aceste numerele s-ar divide cu 3, ce de asemenea este

imposibil. De aceea ratia se divide cu 6 si ca consecinta este mai mare dect 6.

Presupunem ca ratia se divide cu 5. De asemenea numai un numar din numerele

acestea poate sa se divida cu 5 (daca numarul acesta este egal cu 5 ). Dar pentru

ca ratia este mai mare sau egala dect 6, numarul 5 poate sa fie numai primul,

cel mai mic din aceste 6 numere. Dar atunci numarul al saselea de asemenea s-ar

divide la 5. Obtinem contradictia. Ratia d se divide si cu 5. Atunci ea se divide si

cu 2 3 5 = 30, si este mai mare sau egala dect 30. b) Procednd ca n a), deducemca ratia d se divide cu 2, 3 si 5. Ratia d se divide cu 7, fiindca n caz contrar macar

2 numere s-ar divide cu 7, ce este imposibil, pentru ca toate numerele sunt prime.

Presupunem, ca d nu se divide cu 11. Atunci macar un numar din cele 15 se va

divide cu 11. Se stie ca d se divide cu 210 deci e mai mare dect 11. Unicul numar

prim divizibil cu 11 este nsusi 11 care poate fi numai primul termen al progresiei

caci e mai mic dect ratia ei. Dar atunci al doisprezecelea termen al progresiei se

divide si el cu 11. Obtinem contradictia si aflam ca diferenta d se divide cu 11.

Absolut analog deducem ca d se divide cu 13. Deci d 23571113 > 40000.

Problema 86. Gasiti numarul de numere naturale n mai mici ca 5987 pentru

care fractia2n+1 2n 1

2n n+ 1 este reductibila.

Solutie.2n+1 2n 1

2n n+ 1 =2n+1 2n+ 2 3

2n n+ 1 = 2 3

2n n+ 1. Deci, fractia din

enunt este reductibila daca si numai daca3

2n n+ 1 este reductibila. Consideramn pentru care (3, 2n n+ 1) > 1 3 | 2n n+ 1. Avem 2 cazuri:

1) n = 2m. 2n = 4m = (3 + 1)m 1 (mod 3). Astfel n 2n + 1 2 (mod 3)si n 2 (mod 6). In multimea A sunt [ 5987+626 ] = 998 de numere ce dau restul2 la mpartirea la 6.

2) n = 2m + 1. 2n = 2 4m 2 (mod 3). Astfel n 2n + 1 0 (mod 3) sin 3 (mod 6). In multimea A sunt [ 5987+636 ] = 998 de numere ce dau restul 2la mpartirea la 6.

In total sunt 998 + 998 = 1996 de numere n pentru care fractia data este

reductibila.

Problema 87. Gasiti valoarea minima posibila a expresiei |12m 5n| pentru

50

m,n N?

Solutie. Evident nu putem avea |12m5n| = 0 (deoarece (12,5)=1). Sa consideram2 cazuri:

1) n = 2k. 5n = 25k = (2 12 + 1)k 1 (mod 12). Avem 2 posibilitati:1.1) |12m 5n| = 12m 5n 1 (mod 12), de unde |12m 5n| 12 1 = 11.1.2) |12m 5n| = 5n 12m 1 (mod 12), de unde sau 5n 12m = 1, sau

5n 12m 12 + 1 = 13. Sa presupunem 5n 12m = 1. Atunci 12m 4 (mod 5).121 2 (mod 5)122 4 (mod 5)123 3 (mod 5)124 1 (mod 5)Fie m = 4a + b, 0 b < 4. Atunci 12m (124)a12b 12b 4 (mod 5), de

unde b = 2. Astfel 1 = 5n 12m = 52k 122(2a+1) = (5k 122a+1)(5k + 122a+1)si 5k 122a+1 = 5k + 122a+1. Contradictie. Deci 5m 12m 13.

2) n = 2k + 1. 5n = 5 25k 5 (mod 12). Avem 2 posibilitati:2.1) |12m 5n| = 12m 5n 5 (mod 12), de unde |12m 5n| 12 5 = 7.2.2) |12m5n| = 5n12m 5 (mod 12), de unde sau 5n12m = 5 (imposibil,

deoarece 5 nu divide 12), sau 5n 12m 12 + 5 = 17.Combinand toate inegalitatile se obtine |5n 12m| 7. Pentru n = m = 1 se

obtine egalitate. Astfel, 7 este numarul cautat.

Problema 88. Gasiti numarul minim n > 1 pentru care 1997n se termina n

1997.

Solutie. Fie m = n 1. 1997n 1997 (mod 10000) 24|(1997m 1) si54|(1997m 1).

1997 2 (mod 5),19972 4 (mod 5),19973 3 (mod 5),19974 1 (mod 5).Fie m = 4m1 + r, 0 r < 4. Atunci 1997m 1997r 1 (mod 5). Astfel

r = 0. Fie m2 = 2m1.

1997m = (2000 3)m (3)2m2 9m2 (10 1)m2 1 (mod 52). Dar(10 1)m2 = 1 10m2 + 1002u1 1 10m2 (mod 52) (u1 Z), de unde 5 | m2.

51

Fie m2 = 5m3. Atunci m = 10m3, m3 este par.

1997m = (2000 3)m = 3m 10m3 3m1 2000 + 20002u2 3m (mod 54)u2 Z.

3m = (101)m2 = 1+m2 10+ m2(m21)2 102+ m2(m21)(m22)6 103+104u3 1 + 50m3 + 250m3(m2 1) + 2500m3(m21)(m22)3 1 + 50m3(1 + 5(m2 1))(mod 54) (u3 Z.

54 | 252m3(1+5(m21)), dar (1+5(m21), 5) = 1, astfel conditia 54|(1997m1) este satisfacuta daca si numai daca 52|m3. Evident, m3 minimal par este2 52 = 50. Deci m = 10m3 = 500 este minimal pentru care 54 | 1997m 1.

19974 1 = (1997 1)(1997 + 1)(19972 + 1) 24 | 19974 1 1997500 =(19974)125 1 (mod 24). Deci 500 este valoarea minima a lui m pentru care1997m 1 se divide cu 24 si 54. Raspuns: n = 501.

Problema 89. Gasiti n si x astfel ncat: 499(1997n + 1) = x2 + x.

Solutie. 1996(1997n + 1) = 4x2 + 4x deci 1996 1997n + 1996 = 4x2 + 4x deci1996 1997n + 1997 = (2x+ 1)2. Deci (2x+ 1)2 nu este divizibil la 1997. 1997 esteun numar prim

Atunci (2x+ 1)2 este divizibil la 19972. Deci 1996 1997n + 1997 este divizibilla 19972, deci n = 1, x1 = 998, x2 = 999.

Problema 90. Gasiti toate perechile (p, q) de numere prime, ncat expresia p2 +

3pq + q2 este: a) patrat perfect b) putere de 5.

Solutie. a) Fie p2+3pq+q2 = r2, p, q -nr. prime si r > 0. Daca p 6= 3, q 6= 3, atuncip2 + 3pq+ q2 2 (mod 3), iar un patrat perfect nu da restul 2 modulo 3. Fie decip = 3, q2+9q+9 = r2 sau (2q+9)245 = (2r)2 deci (2q2r+9)(2q+2r+9) = 45si r > 0. Deducem 2q + 2r + 9 = 15 sau. In primul caz q + r = 3 care e clar

imposibil. In al doilea car q + r = 18 si cum 2q 2r + 9 = 1 deducem q = 7.Raspuns:p = 3; q = 7; p = 7; q = 3 (din simetrie).

b) p2 + 3pq + q2 = 5n. p 2, q 2 deci p2 + 3pq + q2 20, deci n 2,adica 25 divide p2 + 3pq + q2 = (p q)2 + 5pq. Deci 5 divide (p q)2, adica 5divide p q deci 52|(p q)2 deci 25 divide 5pq, de unde p = 5, q = 5. Noi obtinemp2 + 3pq + q2 = 125 = 53, deci p = q = 5 e solutie.

Problema 91. Demonstrati ca pentru orice n natural, numarul 19 8n + 17 estecompus.

52

Solutie. Daca n = 2k, atunci lund dupa modulo 3 avem

19 82k + 17 = 18 82k + (1 + 63)k + (18 1) 1 1 = 0 (mod 3).

Daca n = 4k + 1, atunci calculnd modulo 13 avem

19 84k+1 + 17 6 84k+1 + 4 = 48 642k + 4 9 (1)2k + 4 0 (mod 13).

Daca n = 4k + 3, atunci avem

1984k+3+17 (1)83642k+2 84k+3+483642k+17 = 1584k+3+4510642k+42(165)2k+(258) 0 (mod 5).

Problema 92. Fiem - un numar natural par. Fie {a1, a2, . . . , am} si {b1, b2, . . . , bm} doua seturi complete de resturi modulo m. Demonstrati ca {a1+b1, . . . , am+bm}nu este sistem complet de resturi modulo m.

Solutie. Presupunnd prin absurd contrarul, avem urmatoarele:

a1 + . . .+ am 1 + 2 + . . .+m = m(m+ 1)2

(mod m)

b1 + . . .+ bm m(m+ 1)2

(mod m)

(a1 + b1) + . . .+ (am + bm) m(m+ 1)2

(mod m)

Sumnd primele doua relattii si tinnd cont de a treia, obtinem

m(m+ 1)

2 m(m+ 1) 0 (mod m) m | m

2 (m+ 1)

Deoarece (m.m+ 1) = 1, rezulta ca m | m2 , imposibil.

O formulare mai simpla (dar echivalenta) a problemei precedente este urmatoarea:

Fie m un numar natural par, iar {a1, . . . , m} un sistem complet de resturi modulom. Sa se arate ca din numerele 1+a1, . . . ,m+am exista cel putin doua congruente

modulo m.

53

2.5 Patrate si cuburi perfecte

Problema 93. Fie p1 < p2 < . . . < pk . . . sirul numerelor prime. Sa se arate ca

pentru orice n 1 numarul p1 . . . p2 . . . pn + 1 nu este patrat perfect.

Solutie. Avem p1 = 2, p2, . . . , pn sunt impare deci

p1p2 . . . pn + 1 = 2(2k + 1) + 1 = 4k + 3,

care nu poate fi patrat perfect.

Problema 94. Sa se arate ca pentru orice a, b N numarul 5a+7b nu este patratperfect.

Solutie. Pentru a = 0 si b > 0, 5a + 7b = k2 7b = (k 1)(k + 1). Pentruk 1 = 1 nu exista solutii. Pentru k 1 > 1, obtinem 7 | (k 1) si 7 | (k + 1) 7|(k+ 1) (k 1) = 2, fals. In mod analog, pentru a > 0 si b = 0 nu avem solutii.

Ramane cazul a, b > 0 n care 5a + 7b, fiind patrat perfect par, se divide cu 4.

Avem

5a + 7b 1 + (1)b (mod 4),deci b trebuie sa fie impar. Considernd relatia 5a + 7b = k2 modulo 3, observam

ca a este impar; altfel 5a + 7b 2 (mod 3), imposibil pentru un patrat perfect.Fie a = 2a+1, b = 2b+1 si atunci 5 25a+7 49b = k2. Lund dupa modulul

5, avem 5a + 7b 7 49b 2 (mod 5), n timp ce resturile patratice posibilemodulo 5 snt 0,1.

Problema 95. Sa se determine numerele naturale m si n astfel nct

1! + 2! + . . .+ n! = m2.

Solutie. Fie Sn = 1! + 2! + . . . + n!. Deoarece pentru n 5 ultima cifra a lui n!este 0 rezulta ca Sn se termina n ultima cifra a sumelor

S1 + S2 + S3 + S4 = 33,

dar nici un patrat nu se termina cu 3. Raman cazurile n 3 din care singurelepatrate sunt S1 = 1

2 si S3 = 32. Rezulta perechile (1, 1), (3, 3).

Problema 96. Numerele n + 1 si 2n + 1 sunt patrate perfecte. Demonstrati ca

numarul n se divide la 24.

54

Solutie. Demonstram nti ca n se divide la 3. Intr-adevar, deoarece un patrat

perfect nu poate fi congruent cu 2 modulo 3, n + 1 nu e congruent cu 2 modulo

3 si 2n + 1 nu e congruent cu 2 modulo 3, care mpreuna implica 3 | n. Ne mairamane sa aratam ca n se divide la 8. Deoarece un patrat perfect impar da rest

1 la mpartirea cu 8, conchidem ca 8 | (2n + 1) 1, adica 4 | n. Atunci n + 1,fiind impar, este de asemenea congruent cu 1 modulo 8 si 8 | (n + 1) 1 = n. Inconcluzie, 24 | n.

Problema 97. Fie k {3, 5, 7} si a1, a2, . . . , ak numere ntregi astfel nct suma

9 | a31 + a32 + . . .+ a3k

Sa se arate ca produsul a1a2 . . . ak se divide cu 3.

Solutie. Daca prin absurd produsul nu se divide cu 3, resturile modulo 9 ale

numerelor a1, a2, . . . , ak pot fi 1, 2, 4, 5, 7, 8 care ridicate la a treia dau resturile

1,1, 1,1, 1,1. Suma oricaror 3,5 sau 7 astfel de resturi poate fi congruenta cu1,3,5,7 (mod 9), deci nu poate sa se divida cu 9.

Problema 98. Sa se arate ca daca p si p2 + 14 sunt numere prime atunci p3 + 4

este numar prim iar p4 + 10 nu este numar prim.

Solutie. Vom arata ca singurul numar pentru care p si p2 + 14 sunt prime este

p = 3. Daca p > 3 atunci

p 1 (mod 6) p2 1 (mod 6) p2 + 14 3 (mod 6) p2 + 14

se divide la 3, deci este compus. In concluzie p = 3 si atunci p3 + 4 = 31 care este

prim si p4 + 10 = 91 = 7 13 care este neprim.

Problema 99. (Putnam 1998) Sa se demonstreze ca pentru orice numere ntregi

a, b, c exista un numar poizitiv ntreg n astfel nctn3 + an2 + bn+ c nu este

ntreg.

Solutie. Fie P (x) = x3 + ax2 + bx + c si n = |b| + 1. Presupunem ca P (n) siP (n+ 2) sunt ambele patrate perfecte. Cum P (n) si P (n+ 2) au aceasi paritate,

rezulta ca P (n) P (n+ 2) (mod 4). Insa

P (n+ 2) P (n) = 2n2 + 4n+ 8 + a(4n+ 4) + 2b

55

P (n+ 2) P (n) 2n2 + 2b = 2((|b|+ 1)2 + b) 2 (mod 4) un numar nedivizibil cu 4, contradictie. Asadar unul din numerele

P (n),

P (n+ 2) nu este ntreg.

Problema 100. Se numeste numar triunghiular un numar de forma

t =n(n+ 1)

2(= 1 + 2 + . . .+ n) unde n 1.

Sa se arate ca daca t este un numar triunghiular, atunci 9t+1, 25t+3 si 49t+6

sunt numere triunghiulare, iar 8t+ 1 este patrat perfect.

Solutie. Fie tn =n(n+ 1)

2. Avem

9tn + 1 =9n2 + 9n+ 2

2=

(3n+ 1)(3n+ 2)

2= t3n+1

25tn + 3 =25n2 + 25n+ 6

2=

(5n+ 2)(5n+ 3)

3= t5n+3

49tn + 6 =49n2 + 49n+ 12

2=

(7n+ 3)(7n+ 4)

2= t7n+3

8tn+1 = 4n2 + 4n+ 1 = (2n+ 1)2.

Observatie. Pentru orice k numarul (2k+ 1)2t2n +k(k + 1)

2este numar triunghi-

ular.

Problema 101. Fie p1, p2, . . . , pn numere prime diferite de 2. Sa se arate ca

numarul (p1p2 . . . pn)2 + 1 nu este patrat perfect si nici o alta putere perfecta.

Solutie. Numerele p1, p2, . . . , pn fiind impare sunt de forma 4k+ 1 sau 4k 1, deci

p21 p22 . . . p2n 1 (mod 4)

si atunci numarul N = (p1p2 . . . pn)2 + 1 este de forma 4k + 2 = 2(2k + 1), adica

se divide la 2 si nu la 4. Prin urmare, N nu este nici o putere perfecta.

Problema 102. Sa se arate ca ca ecuatia

x61 + x62 + x

63 + x

64 + x

65 + x

66 = 20132015

nu are solutii n multimea numerelor ntregi.

56

Solutie. Vom considera relatia data modulo 8. Cuburile modulo 8 sunt 0,1,3care ridicate la patrat dau 0 sau 1 modulo 8. Astfel ca x61, x

62, x

63, x

64, x

65, x

66 {0, 1}

(mod 8). Pe de alta parte restul modulo 8 al numarului 20132015 este dat de

ultimele trei cifre deci de numarul 015 = 15 si observam ca el este congruent cu 7

modulo 8. Congruenta

x61 + x62 + x

63 + x

64 + x

65 + x

66 7 (mod 8)

nu are solutie.

Problema 103. Sa se arate ca ecuatia

x61 + x62 + . . .+ x

6n = 20112011

nu are solutii n multimea numerelor naturale pentru nici un n 7.

Solutie. Vom considera relatia data modulo 9 si avem x3 {0,1} (mod 9), decix6 {0, 1} (mod 9). Pe de alta parte

20112011 = 2 + 0 + 1 + 1 + 2 + 0 + 1 + 1 = 8 (mod 9).

Suma a mai putin de 8 numere 0 sau 1 nu poate fi 8.

Problema 104. Determinati toate numerele naturale n, pentru care numarul

11111 scris n baza n este patrat perfect.

Solutie. Numarul 11111 scris n baza n este 1111n = n4+n3+n2+n+1. Evident,

acesta este patrat perfect daca si numai daca 4n4 + 4n3 + 4n2 + 4n+ 4 este patrat

perfect. Vom arata ca pentru n > 3, numarul 4n4+4n3+4n2+4n+4 se afla strict

ntre patratele (2n2 + n)2 si (2n2 + n+ 1)2. Avem (2n2 + n)2 = 4n4 + 4n3 + n2 4n4 + 4n3 + 4n2 + 4n+ 4.

Pentru n = 2, 3, avem 111112 = 16+8+4+2+1 = 21, 111113 = 81+27+9+3+1 =

121 = 112. In concluzie, singurul n pentru care 11111n este patrat perfect este

n = 3.

57

Problema 105. Determinati cel mai mic numar k, pentru care exista numerele

ntregi x1, x2, . . . , xk astfel nct

x31 + x32 + . . .+ x

3k = 2002

2002

Solutie. Mai nti aratam ca numarul 20022002 nu poate fi reprezentat ca suma a

cel mult trei cuburi perfecte (si atunci k 4). Intr-adevar, orice cub perfect estecongruent cu 0,1 sau -1 modulo 9, si atunci suma a cel mult trei cuburi perfecte

poate fi congruenta doar cu 0,1,2,3 modulo 9. Insa,

20022002 = 2002 (2002667)3 2002 1 4 (mod 9)

Prin urmare, k 4. Pe de alta parte, 20022002 se poate scrie ca suma a patrucuburi n felul urmator:

20022002 = (1000 + 1000 + 1 + 1) (2002667)3 =

= (10 2002667)3 + (10 2002667)3 + (2002667)3 + (2002667)3

Asadar, raspunsul problemei este k = 4.

2.6 Suma cifrelor

Notam cu s(n) suma cifrelor a numarului n. Conform criteriului de divizibilitate

cu 9, avem

s(n) n (mod 9), n N.Problema 106. Demonstrati ca

1. s(a) + s(b) s(a+ b).

2. s(n1n2) min(n1s(n2), n2s(n1)).

3. s(n1n2) s(n1)s(n2).

Solutie. 1. Vom scrie numerele a si b unul sub altul si le vom aduna. Fie ai cifra

numarului a de pe pozitia i, socotind de la dreapta. Analogic vom defini bi si

ci. Daca nu este nici un transport unitatii dintr-o pozitie n alta, pentru fiecare i

ai + bi = ci, deci s(a) + s(b) = s(a+ b). Daca ntr-o s(a) + s(b) = s(a+ b). Daca

ntr-o pozitie i ai + bi este mai mare dect 10, atunci ci va fi egal cu ai + bi 10,dar ci+1 se va mari numai cu 1. Deci suma tuturor cifrelor va scadea cu 9 odata

cu fiecare trecere a unitatii n nivelul urmator. Deci s(a) + s(b) s(a+ b).

58

2. Din considerente de simetrie, este suficient sa aratam ca s(n1n2) n1s(n2).Folosind 1., avem succesiv s(n2 +n2) s(n2) + s(n2) = 2s(n2), s(3n2) s(2n2) +s(n2) 3s(n2), . . . , s(n1n2) s((n1 1)n2) + s(n2) (n1 1)s(n2) + s(n2) =n1s(n2).

3. Scriind n2 =bi10

i, avem s(n2) =bi si

s(n1n2) = s(n1

bi10i) = s(

(n1bi10

i))

s(n1bi10i) =

s(n1bi)

bis(n1) = s(n2)s(n1).

Problema 107. Calculati s(s(s(a))), unde a = 44444444.

Solutie. In primul rnd vom arata ca suma calculata nu este prea mare. Deoarece

a = 44444444 < 100004444, a are cel mult 4 4444 cifre si deci, s(a) = 4 4444 9 =159984. Se observa ca daca m 159984, atunci s(m) s(99999) = 45. Prinurmare, s(s(a)) 45, si atunci suma cifrelor lui s(s(a)) poate fi cel mult s(39) =12. Asadar, avem s(s(s(a))) 12. Deoarece s(n) n (mod 9) pentru oricenumar natural n, avem s(s(s(a))) a 44444444 (2)4444 2 (2)14813 (2) (8)1481 2 1 7 (mod 9). Unicul numar mai mic sau egal dect 12care da rest 7 la mpartirea cu 9 este desigur 7, deci s(s(s(a))) = 7.

Problema 108. Rezolvati ecuatiile:

a) x+ s(x) + s(s(x)) = 1993;

b) x+ s(x) + s(s(x)) + s(s(s(x))) = 1993.

Solutie. a) Deoarece x s(x) s(s(x)) (mod 9), obtinem ca x + s(x) + s(s(x))ntotdeauna se divide la 3. Insa 1993 nu se divide la 3, deci ecuatia nu are solutii.

b) Lund dupa modulul 9, ecuatia devine 4x 1993 4 (mod 9), deci x 1(mod 9). Pe de alta parte, avem x < 1993. Observam ca ntre numerele 1, . . . , 1993

cea mai mare suma a cifrelor o au numerele 999, 1989 si 1899. Astfel, s(x) 27si atunci s(s(x)) s(19) = 10, s(s(s(x))) s(9) = 9. Din ecuatie rezulta

x = 1993 s(x) s(s(x)) s(s(s(x))) 1993 27 10 9 = 1947.

Exista 5 numere ntre 1947 si 1993 care dau rest 1 la mpartirea cu 9: 1954, 1963,

1972, 1981, 1990. Verificnd toate cazurile obtinem singura solutie x = 1963.

59

2.7 Inegalitati n teoria numerelor

Problema 109. Demonstrati ca pentru orice numar natural n,

1

2n< {n

7} < 1 1

6n

Solutie. Fie m = [n

7] < n

7. Atunci

{n

7} = n

7m = 7n2 m2

n

7 +m>

7n2 m22n

7.

Observam ca ecuatiile 7n2m2 = 1 si 7n2m2 = 2 nu au solutii ntregi, deoarece1 si 2 nu sunt resturi patratice modulo 7. Deci, 7n2 m2 3 si {n7}

3

2n

7>

1

2n. Pentru cealalta inegalitate, fie k = [n

7]