Pagrindinė aritmetikos teorema: unikali pirminių skaičių faktorizacija
Sužinokite Pagrindinę aritmetikos teoremą: kaip kiekvienas skaičius turi unikalią pirminių faktorizaciją, faktorizavimo ypatumai ir pritaikymas kriptografijoje.
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ų.
Įrodymas
Pirmasis šią teoremą įrodė Euklidas. Pirmasis išsamus ir teisingas įrodymas buvo pateiktas Karlo Frydricho Gauso veikale "Disquisitiones Arithmeticae".
Kai kurie žmonės gali manyti, kad teorema teisinga visur. Tačiau teorema nėra teisinga bendresnėse skaičių sistemose, pavyzdžiui, algebrinėse sveikųjų skaičių sistemose. Pirmą kartą tai paminėjo Ernstas Kummeris 1843 m. savo darbe apie Fermato paskutinę teoremą. Daugiau informacijos apie tai: skaitykite algebrinių skaičių teorija.
Įrodymą sudaro dvi dalys: pirma, parodome, kad kiekvieną skaičių galima užrašyti kaip pirminių skaičių sandaugą; antra, parodome, kad jei antrą kartą skaičių užrašome kaip pirminių skaičių sandaugą, tai abu pirminių skaičių sąrašai turi sutapti.
Pirmoji įrodymo dalis
Parodysime, kad jei ne kiekvieną skaičių, didesnį už 1, galima užrašyti kaip pirminių skaičių sandaugą, atsidursime tam tikros rūšies neįmanomybėje. Po to darome išvadą, kad turi būti tiesa, jog kiekvieną skaičių galima užrašyti kaip pirminių skaičių sandaugą.
Pažiūrėkite, kas nutiks, kai kas nors pasakys, kad žino teigiamą sveikąjį skaičių, didesnį už 1, kurio negalima užrašyti kaip pirminių skaičių sandaugos. Tokiu atveju paprašysime, kad jis išvardytų visus skaičius, didesnius už 1, kurių negalima užrašyti kaip pirminių skaičių sandaugos. Vienas iš šių skaičių turi būti mažiausias: pavadinkime jį n. Žinoma, šis skaičius n negali būti lygus 1. Be to, jis negali būti pirminis skaičius, nes pirminis skaičius yra vieno pirminio skaičiaus - savęs paties - "sandauga". Taigi tai turi būti skaičių sandauga. Taigi -
n = ab
kur a ir b yra teigiami sveikieji skaičiai, kurie, žinoma, yra mažesni už n. Bet: n buvo mažiausias skaičius, kurio negalima užrašyti kaip pirminių skaičių sandaugos. Taigi a ir b turi būti įmanoma užrašyti kaip pirminių skaičių sandaugas, nes jie abu yra mažesni už n. Bet tada sandauga
n = ab
taip pat galima užrašyti kaip pirminių skaičių sandaugą. Tai neįmanoma, nes sakėme, kad n negalima užrašyti kaip pirminių skaičių sandaugos.
Dabar parodėme, kad neįmanoma, jei pirmoji teoremos dalis nebūtų teisinga. Taip įrodėme pirmąją teoremos dalį.
Antroji įrodymo dalis
Dabar turime įrodyti, kad yra tik vienas būdas teigiamą skaičių, didesnį už 1, užrašyti kaip pirminių skaičių sandaugą.
Tam naudojame šią lemą: jei pirminis skaičius p dalijasi sandaugą ab, tai jis dalijasi a arba b (Euklido lema). Dabar pirmiausia įrodysime šią lemą. Tarkime, kad p nesidalija a. Tuomet p ir a yra dvireikšmiai ir turime Bezout tapatybę, kuri sako, kad turi būti sveikieji skaičiai x ir y tokie, kad
px + ay = 1.
Visa tai padauginus iš b gaunama
pbx + aby = b,
Prisiminkite, kad ab gali būti dalijamas iš p. Taigi dabar kairėje pusėje turime du narius, kurie dalijasi iš p. Taigi dešinėje pusėje esantis narys taip pat dalijasi iš p. Dabar įrodėme, kad jei p neskirsto a, jis turi dalyti b. Tai įrodo lemą.
Dabar įrodysime, kad sveikąjį skaičių, didesnį už 1, kaip pirminių skaičių sandaugą galime užrašyti tik vienu būdu. Paimkite dvi pirminių skaičių A ir B sandaugas, kurių rezultatas vienodas. Taigi sandaugų rezultatui žinome, kad A = B. Paimkime bet kurį pirminį skaičių p iš pirmosios sandaugos A. Jis dalijasi su A, taigi dalijasi ir su B. Keletą kartų pasinaudoję ką tik įrodyta lema, matome, kad tada p turi dalytis bent su vienu B veiksniu b. Tačiau visi veiksniai patys yra pirminiai, taigi ir b yra pirminis. Tačiau žinome, kad p taip pat yra pirminis, todėl p turi būti lygus b. Taigi dabar dalijame A iš p ir taip pat dalijame B iš p. Ir gauname tokį rezultatą kaip A* = B*. Vėl galime paimti pirmavardį p iš pirmosios sandaugos A* ir sužinoti, kad jis lygus kuriam nors sandaugos B* skaičiui. Taip tęsdami, galiausiai matome, kad abiejų sandaugų pirminiai veiksniai turi būti lygiai tokie patys. Tai įrodo, kad teigiamąjį sveikąjį skaičių kaip pirminių skaičių sandaugą galime užrašyti tik vienu unikaliu būdu.
Klausimai ir atsakymai
Klausimas: Kas yra pagrindinė aritmetikos teorema?
A: Pagrindinė aritmetikos teorema yra skaičių teorijos teorema, teigianti, kad kiekvienas teigiamas sveikasis skaičius, didesnis už 1, gali būti užrašytas kaip pirminių skaičių sandauga, ir yra tik vienas būdas užrašyti skaičių.
K: Kaip galima panaudoti šią teoremą?
A: Šią teoremą galima panaudoti kriptografijoje.
K: Kas atsitinka, jei du žmonės randa du skirtingus būdus tam pačiam skaičiui užrašyti?
A: Jei du žmonės randa du skirtingus būdus tam pačiam skaičiui užrašyti, tuomet vienintelis dalykas, kuris gali skirtis, yra pirminių skaičių užrašymo tvarka.
K: Kas yra faktorizacija?
A: Faktorizavimas - tai visų pirminių skaičių, sudarančių tam tikrą skaičių, suradimas.
K: Ar 6936 yra pirminio skaičiaus pavyzdys?
Atsakymas: Ne, 6936 nėra pirminis skaičius; jį galima užrašyti kaip 23 - 3 - 172.
Ne, 6936 nėra pirminis skaičius; jį galima užrašyti kaip 23 - 3 - 172.
Ieškoti