Multiplicator simplu

În teoria numerelor , factorii primi ( divizori primi ) ai unui număr întreg pozitiv sunt numere prime care împart acel număr la un factor ( fără rest ) [1] . A extrage factorii primi ai unui număr întreg pozitiv înseamnă a enumera acești factori primi împreună cu multiplicitățile lor. Procesul de determinare a factorilor primi se numește factorizare întregi . Teorema fundamentală a aritmeticii afirmă că orice număr natural poate fi reprezentat ca un produs unic (până la ordin) al factorilor primi [2] .

Pentru a scurta expresia, factorii primi sunt adesea reprezentați ca puteri ale primelor (multiplicitate). De exemplu,

360=2\times 2\times 2\times 3\times 3\times 5=2^{3}\times 3^{2}\times 5

unde factorii 2, 3 și 5 au multiplicitatea 3, 2 și, respectiv, 1.

Pentru un factor prim p al lui n , multiplicitatea lui p este cea mai mare dintre exponenții a pentru care pAîmparte n egal.

Pentru un număr întreg pozitiv n , numărul factorilor primi n și suma factorilor primi n (fără multiplicitate) sunt exemple de funcții aritmetice din n ( funcții aritmetice aditive [3] ).

Pătrat complet

Pătratul unui număr are proprietatea că toți factorii săi primi au multiplicitate pară. De exemplu, numărul 144 (pătratul 12) are factori primi

144=2\times 2\times 2\times 2\times 3\times 3=2^{4}\times 3^{2}.

Într-o formă mai înțeleasă:

144=2\times 2\times 2\times 2\times 3\times 3=(2\times 2\times 3)\times (2\times 2\times 3)=(2\times 2\times) 3)^{2}=(12)^{2}.

Deoarece fiecare factor prim este prezent aici de un număr par de ori, numărul inițial poate fi reprezentat ca pătratul unui număr. În același mod, cubul unui număr este un număr ai cărui factori primi sunt divizibili cu trei și așa mai departe.

Numerele coprime

Numerele întregi pozitive care nu au factori primi comuni se numesc coprime . Se poate spune că două numere întregi a și b sunt între prime dacă cel mai mare divizor comun al lor mcd( a , b ) = 1. Dacă două numere întregi nu au factorii lor primi, atunci algoritmul lui Euclid este folosit pentru a determina dacă sunt coprimi ; algoritmul rulează în timp polinomial pe numărul de cifre.

Numărul întreg 1 este coprim pentru orice număr întreg pozitiv, inclusiv pentru el însuși. Cu alte cuvinte, numărul 1 nu are factori primi, este un produs gol . Aceasta înseamnă că mcd(1, b ) = 1 pentru orice b ≥ 1.

Aplicații criptografice

Determinarea factorilor primi ai unui număr este un exemplu de problemă care este adesea folosită pentru a oferi securitate criptografică în sistemele de criptare [4] . Această problemă ar trebui să ia timp super-polinom în numărul de cifre. Aceasta înseamnă că este relativ ușor să construiești o problemă care ar dura mai mult timp de rezolvat decât epoca cunoscută a universului cu dezvoltarea actuală a computerelor și cu ajutorul algoritmilor moderni.

Funcții Omega

Funcția ω ( n ) (omega) este numărul de diferiți factori primi n , în timp ce funcția Ω( n ) (omega mare) este numărul de factori primi n recalculați cu multiplicitatea [2] . În cazul în care un

n=\prod _{i=1}^{\omega (n)}p_{i}^{\alpha _{i)),

apoi

\Omega (n)=\sum _{i=1}^{\omega (n)}\alpha _{i}.

De exemplu, 24 = 2 3 × 3 1. Deci ω (24) = 2 și Ω(24) = 3 + 1 = 4 .

ω ( n ) pentru n = 1, 2, 3, … respectiv 0, 1, 1, 1, 1, 2, 1, 1, 1, … este secvența A001221 în OEIS .
Ω( n ) pentru n = 1, 2, 3, … respectiv 0, 1, 1, 2, 1, 2, 1, 3, 2, … este secvența A001222 în OEIS .

Vezi și

Numar compus
Factorizarea numerelor întregi - problema algoritmică a găsirii factorilor primi ai unui număr dat
Divizibilitate
Tabelul multiplicatorului prim
Sita lui Eratosthenes
Teorema Erdős-Kac
Puterea criptografică

Link -uri

↑ Jensen, Gary R. Aritmetică pentru profesori: cu aplicații și subiecte din geometrie . — Societatea Americană de Matematică, 2004.
↑ 1 2 Riesel, Hans (1994), Numerele prime și metodele computerizate pentru factorizare , Basel, Elveția: Birkhäuser, ISBN 978-0-8176-3743-9
↑ Melvyn B. Nathanson. Teoria numerelor aditive: bazele clasice . - Springer-Verlag , 1996. - Vol. 234. - (Texte de licenţă de matematică). — ISBN 0-387-94656-X .
↑ Menezes, Alfred; van Oorschot, Paul C.; Vanstone, Scott A. Handbook of Applied Cryptography (nedefinit) . - CRC Press , 1996. - ISBN 0-8493-8523-7 .