număr prim - este un număr natural. având exact două diferite divizor naturale. 1 și în sine. Studiul proprietăților numerelor prime este teoria numerelor.
1 nu este nici număr prim, nici compozit.
Secvența de numere prime începe cu
Numerele naturale care au mai mult de doi divizori, numit compozit. Astfel, toate numere întregi pozitive, cu excepția unităților sunt împărțite în simple și complexe.
Descompunerea numerelor naturale într-un produs de prim [edita]
Teorema fundamentală a aritmeticii afirmă că fiecare număr natural. mai mult de un (1) poate fi reprezentat ca un produs de numere prime, cu numai metoda (cu o precizie de ordinul a factorilor de repetiție). Astfel, numerele prime - „blocurile de construcție de bază“ de numere naturale.
Introducerea unui număr natural într-un produs numit de descompunere simplu sau factorizarea în numere prime. În momentul de față, un număr necunoscut de algoritmi de factorizare polinomial, deși nu dovedit, că o astfel de algoritm nu există. (În continuare, este vorba despre un algoritm în timp polinomial bazat pe logaritmul numărului care urmează să fie testat, adică numărul de cifre sale). Pe complexitatea algoritmică a problemei factorizării bazate pe RSA Criptosistem.
Ciurul lui Eratostene. Sundaram sită și sita de Atkin oferă modalități ușoare de a găsi lista de numere prime până la o anumită valoare.
Pentru anumite clase de numere, există teste specializate simplitate eficiente. De exemplu, pentru a verifica ușurința numerelor Mersenne folosit testul Lucas - Lehmer.
Câte numere prime? [Referirea]
Primes este infinit. Cea mai veche dovadă cunoscută a acestui fapt a fost dat de Euclid în „Principia“ (Cartea IX, declarația 20). Argumentul său poate fi reprodus pe scurt după cum urmează:
Imaginați-vă că numărul de numere prime este finit. Înmulțiți-le împreună și se adaugă unul. Numărul rezultat nu este divizibil cu oricare dintr-un set finit de amorse, deoarece restul de divizare pe oricare dintre ele oferă unității. Prin urmare, numărul trebuie să fie divizibil cu un număr prim nu este inclus în acest kit.
Matematica a oferit alte probe. Unul dintre ei (prezentat de Euler) arată că suma tuturor numerelor care sunt inverse la cote simple.
Cunoscut număr prim teorema arată că numărul de amorse mai puțin \ (n \), notată cu \ (\ pi (n) \), creste ca \ (n / \ ln (n) \).
Cel mai înalt cunoscut simplu [citare]
număr prim Mersenne favorabil la prezența alt test primality eficient. test de Luc - Lehmer. Datorită lui, amorse Mersenne au ținut mult timp recordul ca cel mai mare simplu cunoscută. Pentru a găsi un număr prim de mai mult de 10 de 7 cifre zecimale FEP numit [2] atribuirea de 100.000 $.
Unele proprietăți [modifică]
- Dacă \ (p \) - simplu și \ (p \) divide \ (a b \), apoi \ (p \) divide \ (a \) sau \ (b \). Dovada acestui fapt a fost dat de Euclid și este cunoscut sub numele de Lema lui Euclid. Este folosit în demonstrația teoremei fundamentale a aritmetice.
- deducerilor Ring \ (\ mathbb_n \) este un domeniu dacă și numai dacă \ (n \) - simplu.
- Caracteristicile fiecărui domeniu - un număr prim sau zero.
- Dacă \ (p \) - un simplu și \ (a \) - un naturale, apoi \ (o ^ p - un \) este împărțit în \ (p \) (Teorema lui Fermat Mica).
- Dacă \ (G \) - elemente de grup finit \ (p ^ n \), apoi \ (G \) cuprinde un element de ordine \ (p \).
- Dacă \ (G \) - un grup finit și \ (p ^ n \) - gradul maxim de \ (p \), care împarte \ (| G | \), apoi \ (G \) are un subgrup de ordinul \ (p ^ n \), numit Sylow subgrup. Mai mult, numărul de subgrupuri Sylow este egal cu \ (pk + 1 \) pentru un întreg \ (k \) (teorema lui Sylow).
- Natural \ (p> 1 \) este simplu, dacă și numai dacă \ ((p - 1) + 1 \) este împărțit în \ (p \) (teorema lui Wilson).
- Dacă \ (n> 1 \) - natural, atunci există un simplu \ (p \), astfel încât \ (n
- O serie de numere care sunt inverse la cote simple. Mai mult decât atât, în cazul în care \ (x \ a \ infty \)
Întrebări deschise [modifică]
Există încă multe semne de întrebare numere prime, dintre care cele mai renumite au fost enumerate Landau (Landau) la al cincilea Congres al Matematicienilor [3]:
- Conjectura lui Goldbach (Landau prima problemă) că fiecare număr chiar mai mare decât două pot fi exprimate ca suma a două numere prime și fiecare număr impar mai mare de 5 poate fi scris ca suma a trei numere prime.
- A doua problemă Landau infinit pluralitatea de gemeni simple - amorse, diferența dintre care este egal cu 2.
- Ipoteză Legendre (Landau treia problemă) care între \ (n ^ 2 \) și \ ((n + 1) ^ 2 \) este întotdeauna un număr prim.
- A patra problemă a Landau un număr infinit de tip \ obișnuit (n ^ 2 + 1 \).
Deschideți problema este existența unui număr infinit de numere prime în multe secvențe întregi, inclusiv numerele lui Fibonacci. Fermat și t. D.