Home > Documents > tncarte 1.2

tncarte 1.2

Date post: 02-Mar-2016
Category:
Author: luca-schidu
View: 94 times
Download: 2 times
Share this document with a friend
Description:
Da da
Embed Size (px)

of 187

Transcript
  • 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]


Recommended