Glosar

Selectați unul dintre cuvintele cheie din stânga ...

Divizibilitate și Numere PrimeNumere Prime

Timp de citit: ~20 min

Atunci când calculăm perechile de divizori, se poate întâmpla ca un număr să nu aibă niciun divizor cu excepția primei perechi. Un exemplu este 13 - singurii săi divizori sunt doar 1 și 13. Aceste numere speciale se numesc numere prime. Ele nu pot fi descompuse sub forma unui produs de numere mai mici, iar asta le face, într-un fel sa fie “atomii numerelor”.

Să observăm că 1 nu este număr prim, așa că primele numere prime sunt 2, 3, 5, 7, 11, 13, …

Orice număr ce nu este prim poate fi scris sub forma unui produs de numere prime: pur și simplu continuăm să-l împărțim de mai multe ori până când toți factorii sunt primi. De exemplu,

84
2
×
42
2
×
21
3
×
7
84
=
2
×
2
×
3
×
7

2, 3 și 7 sunt numere prime și nu se mai pot împărți. Produsul 2 × 2 × 3 × 7 se numește descompunerea în factori primi a lui 84, iar 2, 3 și 7 sunt factorii primi. De observat că unele numere prime, precum 2 în acest caz, poate apărea de mai multe ori într-o descompunere în factori primi.

Orice număr întreg se poate descompune în factori primi și nu există două numere întregi care să aibă aceeași descompunere în factori primi. Mai mult de atât, orice număr întreg poate fi exprimat în mod unic ca produs de numere prime. Aceasta se numește Teorema Fundamentală a Aritmeticii (TFA).

Folosirea TFA poate simplifica multe probleme de matematică: descompunem numerele în factori primi, rezolvăm problema pentru numerele prime individuale, care adesea poate fi mult mai ușoară, iar apoi combinăm aceste rezultate pentru a rezolva problema inițială.

Ciurul lui Eratostene

S-a dovedit că poate fi destul de dificil de determinat dacă un număr este prim: trebuie să găsim mereu toți factori săi primi, ceea ce devine din ce în ce mai dificil pe măsură ce numerele cresc. În schimb, matematicianul grec Eratostene din Cyrene a găsit un algoritm simplu de aflare a tuturor numerelor prime până la 100: the Ciurul lui Eratostene.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
Scriem întâi toate numerele până la 100.
Știm că 1 nu este număr prim, așa că îl ștergem.
Cel mai mic număr prim este 2. Oricare multiplu al lui 2 nu poate fi număr prim, deoarece 2 este factorul lui. Prin urmare, putem tăia toți multiplii lui 2.
Următorul număr de pe lista noastră este 3 – tot un număr prim. Toți multiplii lui 3 nu pot fi numere prime, deoarece 3 este factorul lor. Prin urmare, îi putem tăia și pe aceștia la fel de bine.
Următorul număr, 4, este deja tăiat, așa că trecem la 5: este număr prim și tăiem din nou toți multiplii lui 5.
Următorul număr prim trebuie să fie , căci 6 este tăiat. Încă o dată, tăiem toți multiplii săi.
Următorul număr prim . Observă, însă, că toți multiplii săi sunt . Același lucru este valabil pentru toate celalalte numere rămase. Prin urmare, toate aceste numere rămase trebuie să fie prime.

Acum putem număra că sunt în total de numere prime mai mici ca 100.

Câte numere prime există?

Bineînțeles că putem folosi Ciurul lui Eratostene pentru a calcula numere prime mai mari. Sunt 21 de numere prime între 100 și 200, 16 numere prime între 200 și 300, 17 numere prime între 400 și 500 and doar 11 numere prime între 10.000 și 10.100.

Numerele prime par să se dispereze din ce în ce mai mult, dar se termină vreodată șirul lor? Există un cel mai mare sau un ultim număr prim?

Matematicianul grec Euclid din Alexandria a fost primul care a demonstrat că există o infinitate de numere prime, folosind următorul raționament:

  1. Să presupunem că șirul numerelor prime este finit.
    P, P, P, P, P
  2. Să le înmulțim pe toate împreună pentru a obține un număr foarte mare pe care îl vom nota N.
    N = P × P × P × P × P
  3. Acum hai să ne gândim la N + 1. Orice număr prim care divide pe N nu poate să-l dividă și pe N + 1. Având în vedere că toate numerele prime găsite până acum îl divid pe N, niciunul din acestea nu poate să-l dividă și pe N + 1.
    P, P, P, P,
    P
    N
    P, P, P, P,
    P
    N + 1
  4. Conform Teoriei Fundamentale a Aritmeticii N + 1 trebuie să aibă un factor prim. Fie N + 1 este el însuși prim, fie există un alt număr prim nou P’ care-l divide pe N + 1.
    P’ N + 1
  5. În ambele cazuri am găsit un nou număr prim care nu se află în lista noastră inițială, dar am presupus ca toate numerele prime se aflau în această listă.
  6. Cu siguranță că ceva nu e în regulă! Dar, având în vedere că pașii 24 erau mai mult ca sigur valizi, singura posibilitate este că presupunerea noastră inițială din pasul 1 a fost greșită. Așadar, există o infinitate de numere prime.

Explicația lui Euclid este unul din primele exemple din istorie al unei demonstrații matematice formale – un agument logic prin care se dovedește că trebuie să fie adevărat. Acest exemplu se numește adesea demonstrație prin reducere la absurd: pornim de la o presupunere, deducem ceva imposibil și astfel știm că propria noastră presupunere trebuie să fie incorectă.