Pagrindinė aritmetikos teorema (dar vadinama unikalios faktorizacijos teorema) yra skaičių teorijos teorema. Teorema teigia, kad kiekvienas teigiamas sveikasis skaičius, didesnis už 1, gali būti užrašytas kaip pirminių skaičių sandauga (arba pats sveikasis skaičius yra pirminis skaičius). Teorema taip pat teigia, kad tokia faktorizacija yra unikali: jei skaičius užrašomas kaip pirminių sandauga dviem skirtingais būdais, vienintelis skirtumas gali būti pirminių skaičių tvarka.

Teoremos turinys ir detalės

Konkrečiau, užrašymas reiškia, kad bet kuriam n > 1 egzistuoja pirminiai skaičiai p1, p2, ..., pk ir teigiamos eilinės reikšmės a1, a2, ..., ak tokios, kad

n = p1a1 · p2a2 · ... · pkak

Unikalumas reiškia, kad jei taip pat n = q1b1 · q2b2 · ... · qmbm, kur qi taip pat yra pirminiai, tai k = m ir po perrikiavimo pi = qi bei ai = bi visiems i.

Pastabos:

  • Vienetai (pvz., 1 arba −1) nėra laikomi pirminiais, todėl jų įtraukimo ar ištrynimo nevaržo unikalumo sąvokos.
  • Dažnai sakoma, kad faktorizacija unikali "iki eilės", t. y. iki pirminių sandaugos tvarkos pakeitimo.

Pavyzdžiai

6936 = 23 · 3 · 172 arba 1200 = 24 · 3 · 52

Jeigu kas nors rastų kitą užrašą šiems skaičiams, tai po pirminių skaičių sutvarkymo paaiškėtų, jog tai yra tas pats užrašymas (pirminių sandauga su atitinkamais laipsniais).

Trumpas įrodymo eskizas

Teorija paprastai įrodoma dviem žingsniais:

  • Egsistencijos dalis. Rodoma, kad kiekvienas n > 1 turi pirminių sandaugą. Tai galima padaryti naudojant stipriąją indukciją: jeigu n yra pirminis, tai jau faktorizuota; jei sudėtinis, tada n = ab, kur 1 < a,b < n, o pagal indukcinę prielaidą abu a ir b turi pirminių faktorizacijas, todėl n turi pirminių faktorizaciją.
  • Unikalumo dalis. Unikalumą įrodo naudojant Euklido lemtį: jei pirminis p dalija sandaugą ab, tai p dalija a arba p dalija b. Tarkime, kad n turi dvi faktorizacijas į pirminius: p1p2...pr = q1q2...qs. Tada p1 dalija dešinę pusę ir pagal Euklido lemtį dalins kai kurį qi. Iš čia gaunamas prieštaravimas, jei pirminiai būtų skirtingi; iteruojant gaunama, kad visos dalys sutampa kartais po perrikiavimo.

Taikymas ir reikšmė

Kriptografijoje pagrindinė aritmetikos teorema yra itin svarbi: daugelis viešojo rakto algoritmų, pvz., RSA, remiasi sudėtingumu faktorizuoti didelius sveikuosius skaičius į pirmines dalis. Nors teorema garantuoja, kad faktorizacija yra unikali, ji neduoda greito būdo ją rasti; todėl faktorizacijos skaičiavimo sudėtingumas suteikia kriptografinei apsaugai saugumo.

Algoritmai ir skaičiavimo aspektai

Praktiniam faktorizavimui naudojami įvairūs algoritmai, priklausomai nuo skaičiaus dydžio:

  • mažiems skaičiams – paprastas dalijimas (trial division);
  • vidutinio dydžio – Pollardo rho, ECM (elliptic curve method);
  • labai dideliems – GNFS (General Number Field Sieve), šiuo metu efektyviausias žinomas metodas labai dideliems sveikiesiems.

Išplėtimai ir apribojimai

Pagrindinė aritmetikos teorema galioja sveikųjų skaičių srityje Z. Matematikai taip pat domisi panašiomis savybėmis kitose struktūrose: svarbus bendrinimas yra unikalaus faktorizavimo domenai (UFD – unique factorization domains), kur kiekvienas elementas turi unikalią faktorizaciją iki eilės ir asociatų. Tačiau ne visi integriniai domenai turi šią savybę — pvz., žiniasklaidoje dažnai minimas pavyzdys Z[√−5], kur faktorizacija nėra unikali (5 = 2 · (1 + √−5) = (1 − √−5) · (1 + √−5)).

Pirminių skaičių radimas vadinamas faktorizavimu.

Ši teorema gali būti naudojama kriptografijoje, taip pat ji yra fundamentali sąvoka daugelyje skaičių teorijos teiginių ir tolesnių tyrimų.