NUMERE PRIME, NUMERE COMPUSE. DESCOMPUNEREA IN FACTORI PRIMI A UNUI NUMAR NATURAL, NUMARUL DIVIZORILOR UNUI NUMAR NATURAL NENUL (A. ELEMENTE DE TEHNICA MATEMATICA Multimea numerelor prime reprezinti o clasi foarte importantd de numere natu- tale. Majoritatea rezultatelor importante ale teoriei numerelor, referitoare la numere prime, depasesc nivelul acestei lucriri, ele vor putea fi completate progresiv in urma- toarele clase. Numim numéar prim orice numar natural p 2 2, care are exact doi divizori natu- rali: pe 1 gi pe el insusi. Observatii: 7. 0 si 1 nu sunt numere prime; 2. Singurul numar par care este numar prim este numarul 2. (Toate celelalte numere pare se divid si la 2). Orice numar n € N\ {0, 1} care mu este numér prim se numeste numar compus. Ne punem urmitoarele intrebari: 1) Cate numere prime exist? 2) Care este forma numerelor prime? La prima intrebare, raspunsul este dat de urmatorul rezultat: Teorema 1: Exist& o infinitate de numere prime. Demonstrafie: Presupunem c& nu existi o infinitate de numere prime. Fie n nu- ‘mirul acestora. Mulfimea numerelor prime va fi P= {pi, po, ---s Px}. Vom demonstra c& numirul p = p; - p2- ... - Py + 1 este numéar prim. Este evident cA p > p,, V i= 1,” si cA p,x p, V i= In = p este numar prim. Cum p ¢ P= presupunerea a fost falsd si exist un numa infinit de numere prime. Teorema 2 (Teorema fundamental’ a aritm: Orice numar natural compus se scrie ca produs de numere prime, nu neaparat distincte, Scrierea este unica, ficdnd abstractie de ordinea factorilor. Demonstrafie: Avem de demonstrat dou lucruri si anume: a) Orice numir compus se scrie ca produs de factori primi; b) Descompunerea este unicd, facdnd abstractie de ordinea factorilor. Ne vom ocupa doar de a). Fie ne N, n numar compus => 3 p; numar prim astfel incat p; | n => n= pi > m. ‘Numérul n poate fi prim si problema este rezolvati, sau poate fi compus gi la randul séu se divide la un numar prim p => m = pi - p2 - m2. Continuim procedeul pana cind N= Pi Pr os * Pk-1* Met $i Mp1 este Umar prim, Vom nota n-1 = pe Sin =pi: pr +. PeSuntem siguri c& vom ajunge la o astfel de forma intr-un numér finit de pasi avand in vedere cl n> m, > mz >... > me $i c& intre 2 gi n nu exist un numér finit de numere naturale, Observatie: a) Teorema fundamentalA a aritmeticii se poate reformula astfel: Orice numar natural compus se scrie in mod unic (cand abstractie de ordinea factorilor) sub forma n= p® + p® +...» pe, unde py, po, ..., Pe Sunt numere prime, iar 0, Ca, ...5 0% € N’. ») Scrierea de mai sus se numeste ,descompunerea in factori primi” sau ,des- compunerea in factori a numarului n”. ‘Vom incerca acum si deducem numérul divizorilor naturali ai unui numar natural. Mai intai ne amintim c& orice numar prim are exact doi divizori. + Dac& n= pi, atunci mulfimea divizorilor lui n este D, = {1, pis P?s vs PS }s deci n are exact (ot; + 1) divizori. *Dac& n= pf - pit atunci Dy = {1, pis Pas Pis PP Pho» P's Pi Pre PEO Bis ones PIPES PEs vos BE PP} Observaim c& pentru fiecare p/ cu i= 0,ct, se scriu numerele pj - p/ cuj= Cu regula produsului deducem cn are exact (ct; + 1)(ot2+ 1) divizori. « Rezultatul se poate generaliza pentru n = pf" + py? + ...+ pet. Teorema 3: Numérul divizorilor naturali ai numarului n= pi" pf? +... + pf este (04 + 1)(o2 +1) ...+ (e+ 1). in rezolvarea multor probleme este util si cunoastem forma unui numar prim, raportat la imparjirea cu 4, cu 6 sau cu alte numere. Vorn analiza situatia in raport cu 4, Se stie c& dac& p este numar prim, p > 2, atunci p este impar, Rezultd imediat c& pare una din formele p= 4k+ 1 sau p= 4k +3. Observatii: a) Orice numar prim mai mare decat 2 are una din formele p = 4k + 1 sau p = =4k+3. ) Dac un numa natural are una din formele de mai sus, nu rezultd c& numarul este prim. c) Dact un numar natural mai mare ca 2 nu are una din formele de mai sus, atunci numarul nu este prim. ‘Numim numere prime intre ele dou numere naturale a si b pentru care (a, b) = 1, unde (a, b) reprezinta cel mai mare divizor comun al numerelor a si b. Au loc urmatoarele afirmatii: a) Dous numere naturale consecutive sunt prime intre ele; b) Doua numere prime distincte sunt prime intre ele; ©) Doua numere impare consecutive sunt prime intre ele; 4) Dac& un numér natural este divizibil cu dou numere prime intre ele, atunci acel numir este divizibil si cu produsul lor; e) Daci un numar natural este divizibil cu produsul a dou numere naturale prime intre ele, atunci acesta este divizibil cu fiecare dintre ele. , a.Justificare: a) Fie m sin + 1 numere consecutive. Considerim d¢ N’ astfel incat d| » sid | | Qr+ 1), Atunci d | (n+ 1)—n, decid | 1=> d=1>(n,n+1)=1;Vne WN. b) Fie p,q numere prime, p # g. Atunci D, = (1, p}, D, = {1,9} => D, 0D, = =H>@geql ©) Fie 2k+ 1 si 2k+3 cele doud numere cu ke IN. Fie de N’ astfel ineét d| 2k-+ +1 sid|2k+3 =| (2k+3)-(2k+ 1) = d| 2. Dar deste impar, de unde d= 1 => = 2k+1,2k+3)=1,VkEN. Ultimele doua afirmayii sunt consecinfe ale celor de mai sus. APLICATI: 1. Determinati numerele naturale n,n +2 si n + 4, stiind c& sunt simultan numere prime. Solutie: Dacf n este numar natural par, atunci n, n + 2, n + 4 sunt pare si nu pot fi simultan prime. Fie ne N, 23. Atunci m are forma 3k, 3k +1 sau 3k+2, ke N’. Daca n = 3k i n prim rezulta cd n= 3 i obfinem tripletul 3, 5, 7 de numere prime. n=3k+1, Atuncin +2=3k-+1+2=3k+3 este divizibil cu 3, mai mare decat 3, deci nu este prim. n= 3k+ 2, Atunci n +4 = 3k+2+4=3(k-+ 2) care este divizibil cu 3, mai mare decit 3, deci nu este prim. Comentariu: 1) Numerele prime a c&ror diferent& este 2 se numese numere prime gemene, De exemplu 17 si 19. 2) Problema precedent& arati c& exist o singuri formatie de trei numere prime trigemene, adic& de forma n, n+ 2,n+ 4. Aceasta este 3, 5, 7. 2. Determinati numerele a, b, c, d astfel incat 2° + 3b + 2c + 6d = 56. Solutie: Daca a este prim, atunci a2 si 2*2 4, numar par; 2c, 6d, 56 sunt numere pare => 36 numfr par => b este numa par; beste prim, atunci b= 2. Egalitatea se mai scrie: 2° + 2c + 6 0 Wl +e+3d=25 Pentru a> 6, 2°-' > 2° = 32 nu sunt solutii. {in aceste condifii distingem cazurile: La=2. Atunci c+ 3d=23 Pentru d <7 sid prim verifict d= 2, c= 17,d=7,c=2. I a=3, Atunci 4+¢+3d=25 c+3d=21 3d £3, 21/3 => !3,¢ prim = c=3 sid=6 mu convine,IIT, a= 5. Atunci 16 + ¢ + 3d = 25 e+3d=9 c 13, deci c=3 si se obtine d= 2 Solutii: (2, 2, 2, 7), 2, 2, 17, 2)s (5, 2,3, 2). 3. Aratafi cd numarul z = 37° + 3 +2 nu este prim, oricare ar fin € N°. Solutie: Bn? + 3n+2=3n(n+1)+2 n(n + 1) este numar par, fiind produs de dou numere consecutive, deci 3n(n + 1) este numéar natural par. Obfinem c& z = 3n(n + 1) +2 este numar par si z= 3n(n + 1)+223-1-2+2=8, VneN’ in concluzie, z nu este numar prim. 4, Demonstraji ci dack numirul A= 1-2-3... + m+ 1 este divizibil cu m +1, atunei m + 1 este numér prim, Solutie: Presupunem c& (m + 1) | A si m+ 1 este numar compus. Atunci 3p, q € N° astfel incat m+ 1 = pq. Evident 1

p = 1. Contradictie cu (1). Presupunerea a fost falsi, deci m + 1 este numar prim. + m+ 1, obfinem c& p ” Ariitafi ci numerele 3n + 1 si 9n? + 6n sunt prime intre ele, oricare ar fin € N’. Solutia I: On? + 6n=3-n-(3-n+2). 3n + 1 si 3m sunt numere consecutive, deci nu au divizori comuni # 1. 3n+1 si 3n +2 sunt numere consecutive, deci nu au divizori comuni # 1. {in concluzie, 3n + 1 si 3- (3m + 2) nu au divizori comuni diferiti de 1, cea ce arati cA numerele 37 + 1 si 9n? + 6n sunt prime intre ele. Soluia a H-a: Fie dé N’ astfel incat d | 3n +1 sid | 9n? + 6n => d| 3n-(3n+1) sid | 9n? + + 6n=>d|9n?+43nsid| 9n?+3n+3n. Am obfinut d | 37 si cum d | 3n +1 deducem c& d= 1. Acest lucru arat c& numerele sunt prime intre ele. 6. Aratati c& exist o infinitate de numere prime de forma 4k ~ 1 si o infinitate de numere prime de forma 6k~ 1.Solutie: Presupunem c& exist doar un numir finit de numere prime de forma 4k ~ 1. Fie acestea ay = 4k — 15 ay = 4k ~ 15 ... aq = 4ky— 1. Numarul a = 4(ay = a2... + dy) ~ 1 are cel putin un divizor prim de forma d= 4k — 1. Acesta se va gasi printre numerele prime aj, day ...5 4, => d | (aay... d,). Dar d| a => d| 1 => d= 1 contradicfie cu faptul ci d= 4k— 1 sid numar prim. Presupunerea a fost falst si deci exist& o infinitate de numere prime de forma 4k — 1. Presupunem acum c& exist’ doar un numar finit de numere prime de forma 6k — 1. Fie acestea ay = 6k, — 1; a3 = 6k ~ 1}... dy = 6ky ~ 1. Atunci numirul a= 6(ay: az ... a,)~ 1 are cel putin un divizor prim de forma 6k — 1. Daca a este prim, atunci d= a >a max {a, ... dy} => 3 a, +1= a mumar prim de forma 6k ~ 1 $idn+1€ {a1, .... 5}, contradictie. Dact a nu este prim, fied=6p-1,d|a=>de {a ...,4,} >| (a,...a,) sid|a=> = | 1 contradictie cu d= 6p ~ 1 numar prim, Presupunerea a fost fals& si deci exist o infinitate de numere naturale prime de forma 6k — 1. 7. Demonstrafi c& orice numér natural de forma 4 — 1 are cel pufin un divizor prim de forma 4s— 1. Solugie Daca a = 4k — 1 este numar prim, atunci d = a este divizorul céutat. Dacd a este numar compus, atunci divizorii sai sunt numere impare, adic& sunt de forma 4k + 1 sau 4k 1. Presupundnd d; = 4k; + 1 => a= 4k—1 = «pi = (4k: +1) pi = 4k pit pie 2 Ak-h)-(1+p)=0> 1+p1 $44 €Naipi=4n-lsip|asaare cel putin un divizor de forma 4s — 1. Daca p; este compus procedam analog si objinem 2 | pi | a $i p2=4s2— 1 si asa mai departe. Cum N are un cel mai mic element, atunci cel mai mic divizor de forma 4s — 1 al numarului a este numar prim. in concluzie, numarul a= 4k —1 are cel pufin un divizor prim de forma d= 4s ~ 1. 8. Fie A un numér natural scris in baza 10 care are 2013 cifre, dintre care una este 1, iar celelalte sunt toate egale cu 2. Aratati cd numarul nu este prim. Solutie: 2913. Daca A are ultima cif 2, atunci nu avem ce demonstra. 2 1, atunci cum 221 = 13 - 17 si 222...2 000+221, iar roid elie de? roi0cleede2 13] 22...2 000 si 13 | 221 rezulta ca 13 | 4. lotoaede2 Asadar, A nu este numar prim. 9. Scrieti numarul a = 169 + 171 + 173 + ... + 1999 ca produs de numere prime. Solutie: a= (1+3+5+...+1999)-(1+3+...+167) 1000? - 85°a= (1000 — 85) - (1000 + 85) a=915 - 1085 a=3-5-5-7-31-61 10. Scrieti numarul b = 58 + 61 + 64+... + 112 ca produs de numere prime. Solutie: ‘Numerele sunt de forma 3 -k +1, ke N. b= (14447 +..4112)- (+44... 52458) = eae ros =G-OF143-141+...+3-3741)-G-OF14+3-1414...43-18+ I= = [3+ (142+... +37)+38]-[3-(1+2+... +18) + 19]= = (3-37-38: 2+38)—3- (18-19 :2+19)=(111-19+19-2)-(9- 19 +19) = =19-113-19- 10=19- 103 11. Aflafi cel mai mic numir natural care are 21 divizori naturali i este divizibil cu 125. Solutie: Fie n= pf pS? -... pi mumirul cu proprietatea ceruta, pi, p>, .... Px humere prime, 011, 0, «1.5 Oy € NV. Numérul divizorilor lui » este (ot) + 1) - (G2 +1) +... (Ga + 1)=21. Deoarece 21 = 1 - 21 =3- 7 rezulta cin =p” sau n=p* - q°, p, q numere prime. Conditia n | 125 impune n= 5*- 5,5 ¢ Ndecin=5* sau n= 5°. p?, Dar n este cel mic numar posibil = n = 5” sau n= 5° - 2°, Dintre cele doua numere evident 5° - 2? < 5”, ‘Numarul cerut este 4 - 5°, 12. Se considera numerele a = 1010101, b= 1111? -1110°, c= 65° + 4,d=3",ne N. Stabiliti care dintre aceste numere este prim. Solutie: a= 101 - 10001 si nue prim b= A111 1110? = (1111 ~ 1110) - (1111 + 1110) = 2221 numar prim c= 65 + 4 = 655 +4. 65° + 4-4 - 65? = (657 + 2)? 4 - 65? = (657-2 65 + + 2)(65? +2 - 65 +2= 4197 - 4357 nue prim d= 3" este prim pentru n = 1 Daca n € N\ {1} doar numarul b este prim. Daca m = 1, b si d sunt numere prime. 13, Fie n, n+ 2, n + 6 trei numere naturale si S suma lor. a) Dafi exemplu de cel putin trei valori pentru n € N astfel incdt numerele n, n+ 2, n+ 688 fie simultan numere prime. b) Daca n, n + 2, m+ 6 sunt simultan numere prime, ardtafi c& exist ke N astfel incét $=9-k+5,©) Daca n, n +2, n + 6 sunt numere prime, determinafi restul imparjirii numarului Sila 18. Solupie a) n=5,n=11,n=17; b) Dacd n,n +2, n+ 6 sunt simultan prime, atunci m nu poate da la imparfirea cu 3 resturile 0 si 1. in consecinta n = 3p +2 si atunci S=nt+n+2+n+6=3nt+8=3 + Gp +2)+8=9p+14=9-k+5, ©) Analizénd ca la b) deducem ci n = 6p + 5, de unde S = 3n + 8 =3 - (6p +5) + +8= 18p +18 +5, de unde deducem ca restul imparfirii lui S la 18 este 5 14, Se dau numerele divizori comuni difei Solutic u(x) = 0 si u(y) = 0, deci 10 | x si 10 | y=> x se divide cu 2, 5 si 10 siy se divide eu 2, 5 si 10. Deci x si y au cel putin trei divizori comuni diferiti de 1 73 +3 si y = 973 + 1, Ardtati c& x gi y au cel putin trei ide 1. 15, Ardtaji c8 numarul divizorilor unui p&trat perfect este impar. Solufie: Daca a este patrat perfect, atunci a= d?-d3-....d?,ne N’. Numérul divizorilor lui a este (2+ 1) - (2+ 1)... - (2+ 1) numa impar, 16. Aratati ci numarul 3*"** — 3* este divizibil cu 30, oricare ar fin, ke IN’. Solutic Bite 3". (3-1) =3*-(81"-1) 313,Vke N’. u(81") = u(1") = 1, V ne N’ => 081" -1)=0, Vine N’ > (81-1)! 10, VneN’. Dar 3 si 10 sunt numere prime intre ele. Rezult ca 3° — 3* este divizibil cu 30, Va,keN’. 17. Aritaji c& pentru orice n € N, m2 2 multimea A = {n+ 1,n+2,...,n+ 12} confine cel mult 4 numere prime. Solutie: Mulfimea 4 confine 12 numere consecutive dintre care 6 numere sunt pare. Cum 2 A rezult& c& cele 6 numere nu sunt prime. intre elementele multimii 4 gasim patru multipli consecutivi ai lui 3. Dintre acestia, doi sunt numere impare. Obtinem c& cel putin 8 numere din A nu sunt prime, adic& cel mult 4 dintre acestea sunt prime, oricare ar fi n > 2. Pentru n= 2, obfinem n+ 1 = 3 gi A= {3,4,5,6,7,8,9, 10, 11, 12, 13, 14} care confine cinci numere prime: 3, 5,7, 11, 13. 18. Aflati numerele ab, ac, ad, ae, stiind cd sunt prime si ca daca adunim 90 la fiecare obtinem tot numere prime.Solutie: ab, ac, ad, ae sunt numere prime atunci cand 6, ¢, d, e sunt cifre impare si dife- rite de 5. Atunei numerele sunt al, a3, a7, a9. Analizim a din mulfimea {1, 2,3, ..., 9} Pentru a = 1 => 11, 13, 17 si 19 sunt prime gi de asemenea 101, 103, 107 si 109 sunt numere prime. Dac& a = 2, atunci Daca a= 3, atunci Daca a = 4, atunci Daca a = 5, atunci Daca a = 6, atunci Dacd a = 7, atunci Daca a = 8, atunci :3 nue prim. 77:7 nue prim. !3 nue prim. Dacd a =9, atunci a3=93!3 nue prim. Solutia problemei este data de numerele 11, 13, 17, 19. 19. Determinati numerele prime a si 6, stiind ch numarul n = a +b +a-b +9 este prim. Solutie: Daca a gi b sunt numere impare, atunci a’, b° sia - b sunt numere impare, iar n este numar par, 2 > 9, deci nu poate fi prim. Fie a numar par. Atunci a = 2 sin=b°+2-5+17. Daca b este numar impar, atunci 4° este numir impar, 2 - b este par, deci n numir par, n> 17 simu poate fi prim. Rezulti b = 2 si n = 29 numar prim. Expresia a’ + 5° + a b +9 fiind simetrica in a i , deducem ca pentru a par obinem = 2 sin = 29 numar prim, a 20. Determinafi numerele naturale a si b, a (a, b)- [a,b] + 15 = 123 <> a- b= 108, Din (a, b) = 3 rezulté ci 3 m,n € N’ astfel incat a= 3 -m,b=3-n,(m,n)=1. a+ b= 1089+ m-n=108 > m-n= 12. (mm, n) = 1 si mn = 12 implica (m,n) € {(1, 12), (3, 4)}. Asadar, (a,b) € {(3, 36), (9, 12)}.Solutia a H-az Notim (a, b)=d,de N’. Atunci 3 m,n € N’ astfel incat a=d-m,b=d-n,(m,n)=1. =demen. Egalitatea din enung devine: 3 - d-m-n+Sd= 123 > d-(3-m-n+5)= 123 (*). Avem m,n2 1, deci 3- m-n+528 si atunci d<16, Cum d € Dyas = (1, 3, 41, 123} avem de verificat doua posibilitagi: d= 1 si d Pentru d= 1, (*) devine 3 - m+ n+5=123 sau3+m-n=118 fra solutii in N’. Pentru d= 3, (*) devine 3 «m+n +5=41 sau3-m-n=36 cu solutiile (m,n) = (1, 12); (m, n) = (3, 4), perechi de numere prime intre ele, Problema are solutiile (a, 5) € {(3, 36), (9, 12)}. 21, Numerele naturale distincte a, b verificd 9 - [a, b]=a-b- (a,b). i) Aritafi c& a gi 6 nu sunt prime intre ele. ii) Aritafi c& diferenfa numerelor este cel putin 3. ({q, b] reprezinta cel mai mic multiplu comun al numerelor a $i 8, iar (a, b) este cel mai mare divizor comun al numerelor a i b). Solugie: Cum [a, 5] - (a, b) =a b deducem c&: i) 9[a, 6) = [a, 6) - (a, b) (a,b), adic& (a, 6) =3 si deci a si b nu sunt prime intre ele. ii) Cum a # b atunci admitem c& a> b avem ab > (a, b)!! Fie d= (a, b) atunci d> 1 sia =a'- d,b=b'- dua’, b'e N sia’ > b’, de unde inegalitatea revine la a'— "> 1 care este evidenta si din (a,b) =3 > a-b23.