Aritmētikas fundamentālā teorēma — unikālā faktorizācija un nozīme
Aritmētikas fundamentālā teorēma: unikālā faktorizācija, pirmskaitļu loma un pielietojums — no teorijas pamatiem līdz kriptogrāfijas nozīmīgai praktiskai lietošanai.
Aritmētikas fundamentālā teorēma (saukta arī par unikālās faktorizācijas teorēmu) ir teorēma skaitļu teorijā. Teorēma nosaka, ka katru veselu pozitīvu skaitli, kas lielāks par 1, var uzrakstīt kā pirmskaitļu reizinājumu (vai arī pats vesels skaitlis ir pirmskaitlis). Turklāt šī faktorizācija ir viennozīmīga: ja divi cilvēki iegūst divas pirmskaitļu reizinājuma izteiksmes tam pašam skaitlim, tad tās atšķiras tikai ar pirmskaitļu secību. Par pirmskaitļu atrašanu sauc faktorizāciju.
Piemēri
Daži piemēri ar sava veida "kanonisko" faktorizāciju (pirmskaitļu eksponentu formā):
- 6936 = 23 · 3 · 172
- 1200 = 24 · 3 · 52
Ja kāds atrastu citu veidu, kā 6936 vai 1200 uzrakstīt kā pirmskaitļu reizinājumu, mēs varam sakārtot pirmskaitļus un eksponentus, un pierādīsies, ka faktorizācijas sakrīt. Faktorizācijas problēma ir centrāla arī praktiskā ziņā — liela skaitļa faktorizēšana var būt grūta, un šī grūtība tiek izmantota kriptogrāfijā.
Pierādījuma ideja
Parasti teorēmu pierāda divos soļos: eksistence un unikālums.
Eksistence. To var pierādīt ar (stipru) indukciju. Ja n ir pirmskaitlis, tad faktorizācija jau ir atrasta. Ja n nav pirmskaitlis, tad n = a · b ar 1 < a, b < n. Pēc indukcijas pieņēmuma gan a, gan b ir izsakāmi kā pirmskaitļu reizinājumi, tāpēc arī n ir izsakāms kā pirmskaitļu reizinājums.
Unikālums. Pieņemsim, ka skaitlim ir divas faktorizācijas p1 · p2 · … · pk = q1 · q2 · … · ql, kur p_i un q_j ir pirmskaitļi. Izmantojot Eiklīda lemmu (ja primes skaitlis p dala reizinājumu a · b, tad p dala a vai p dala b), secīgi redzams, ka p1 dalīs kādu no q_j, bet, tā kā q_j ir pirmskaitlis, jāmā p1 = q_j. Var šo elementu "izdot" no abām pusēm un turpināt ar atlikušajiem pirmskaitļiem; līdz ar to faktorizācijas sakrīt līdz kārtības labad. Eiklīda lemma pati par sevi var tikt pierādīta, izmantojot lielāko kopīgo dalītāju vai Bezūta identitāti.
Nozīme un pielietojumi
Aritmētikas fundamentālā teorēma ir pamats daudzām skaitļu teorijas apakšnozarēm. Konkrēti:
- Kriptogrāfijā, piemēram, RSA algoritmā, drošība balstās uz grūtību faktorizēt lielus semipirņus (skaitļus, kas ir divu lielu pirmskaitļu reizinājums), kombinācijā ar faktu, ka faktorizācija, ja tā būtu viegli izdarāma, lauztu drošību.
- Teorija nodrošina, ka veseli skaitļi ir "rīkojami" pēc pirmskaitļu saturu; tas ļauj definēt tādas invariantes kā dalāmība, funkcijas (π(x), tau(n), φ(n) utt.) un analizēt to īpašības.
- Algebraiskā skaitļu teorija izmanto šo ideju, pārnesot to uz plašākiem struktūru klāstu (piemēram, unikālās faktorizācijas domēni — UFD).
Papildus piezīmes
- Teorēma skaidri attiecas uz naturālajiem skaitļiem (>1). Visiem veselajiem skaitļiem faktorizāciju uzskata par viennozīmīgu tikai līdz signāla (±1) reizināšanai: piemēram, -30 = -1 · 2 · 3 · 5.
- Izpētē ir svarīgi saprast, ka unikāla faktorizācija nav pašsaprotama citās skaitļu sistēmās. Piemēram, kompleksā skaitļu apakšringā Z[√-5] nav unikālas faktorizācijas: 6 = 2 · 3 = (1 + √-5) · (1 − √-5), kur abas faktorizācijas nav savstarpēji atkarīgas ar vienkāršu "pirmu reizinātāju pārkārtošanu". Šādas struktūras motivēja abstraktākas definīcijas, piemēram, unikālas faktorizācijas domēni (UFD) un ideālu klasiskās teorijas attīstību.
- Vēsturiskas piezīmes: ideja par pirmskaitļu reizinājumu kā "atomiem" veselajā skaitļu sistēmā ir sena, bet mūsdienu formas un skaidrā pierādījuma formulējumi attīstījās pakāpeniski kopš Eiklīda laikiem.
Šī teorēma ir viens no skaitļu teorijas stūrakmeņiem — gan kā elementārs instruments problēmu risināšanā, gan kā orientieris modernajām teorētiskajām un praktiskajām pielietošanām.
Pierādījums
Pirmais, kurš pierādīja šo teorēmu, bija Eiklīds. Pirmais detalizētais un pareizais pierādījums bija Kārļa Frīdriha Gausa "Disquisitiones Arithmeticae".
Daži cilvēki var domāt, ka teorēma ir patiesa visur. Tomēr teorēma nav patiesa vispārīgākās skaitļu sistēmās, piemēram, algebriskos veselos skaitļos. Pirmo reizi to minēja Ernsts Kummers 1843. gadā savā darbā par Fermā pēdējo teorēmu. Lai uzzinātu vairāk par to, izlasiet algebrisko skaitļu teoriju.
Pierādījums sastāv no divām daļām: pirmkārt, mēs parādām, ka katru skaitli var pierakstīt kā pirmskaitļu reizinājumu; otrkārt, mēs parādām, ka, ja skaitli otrreiz pierakstām kā pirmskaitļu reizinājumu, tad abiem pirmskaitļu sarakstiem jābūt vienādiem.
Pierādījuma pirmā daļa
Mēs parādīsim, ka, ja ne katru skaitli, kas lielāks par 1, var uzrakstīt kā pirmskaitļu reizinājumu, mēs nonākam līdz kaut kādai neiespējamībai. Pēc tam mēs secinām, ka ir jābūt patiesībai, ka katru skaitli var uzrakstīt kā pirmskaitļu reizinājumu.
Tagad paskatieties, kas notiek, ja kāds saka, ka zina veselu pozitīvu skaitli, kas lielāks par 1 un ko nevar uzrakstīt kā pirmskaitļu reizinājumu. Šādā gadījumā mēs lūdzam viņam/viņai nosaukt visus skaitļus, kas lielāki par 1 un ko nevar uzrakstīt kā pirmskaitļu reizinājumu. Vienam no šiem skaitļiem jābūt mazākajam: sauksim to n. Protams, šis skaitlis n nevar būt 1. Turklāt tas nevar būt pirmskaitlis, jo pirmskaitlis ir viena pirmskaita "reizinājums" - tas ir pats par sevi. Tātad tam jābūt skaitļu reizinājumam. Tādējādi -
n = ab
kur gan a, gan b ir veseli pozitīvi skaitļi, kas, protams, ir mazāki par n. Bet: n bija mazākais skaitlis, ko nevar uzrakstīt kā pirmskaitļu reizinājumu. Tātad ir jābūt iespējai a un b uzrakstīt kā pirmskaitļu reizinājumus, jo tie abi ir mazāki par n. Bet tad reizinājums
n = ab
var arī rakstīt kā pirmskaitļu reizinājumu. Tas ir neiespējami, jo mēs teicām, ka n nevar rakstīt kā pirmskaitļu reizinājumu.
Tagad mēs esam parādījuši neiespējamību, kas pastāv, ja teorēmas pirmā daļa nebūtu patiesa. Šādā veidā mēs esam pierādījuši teorēmas pirmo daļu.
Pierādījuma otrā daļa
Tagad mums ir jāpierāda, ka ir tikai viens veids, kā pozitīvu skaitli, kas lielāks par 1, ierakstīt kā pirmskaitļu reizinājumu.
Lai to izdarītu, mēs izmantojam šādu lemu: ja pirmskaitlis p dala reizinājumu ab, tad tas dala a vai dala b (Eiklīda lema). Vispirms mēs pierādīsim šo lemu. Pieņemsim, ka p nedala a. Tad p un a ir kopmēri, un mums ir Bezuta identitāte, kas saka, ka ir jābūt veseliem skaitļiem x un y tādiem, ka
px + ay = 1.
Visu reizinot ar b, iegūst
pbx + lai = b,
Atcerieties, ka ab var dalīties ar p. Tātad tagad kreisajā pusē ir divi locekļi, kas dalās ar p. Tātad arī loceklis labajā pusē ir dalāms ar p. Tagad esam pierādījuši, ka, ja p nedala a, tad tam jādala b. Tas pierāda lemu.
Tagad mēs pierādīsim, ka veselu skaitli, kas lielāks par 1, kā pirmskaitļu reizinājumu varam ierakstīt tikai vienā veidā. Ņemiet divus pirmskaitļu A un B reizinājumus, kuriem ir vienāds rezultāts. Tātad mēs zinām, ka šo reizinājumu iznākums ir A = B. Paņemsim jebkuru pirmskaitli p no pirmā reizinājuma A. Tas dala A, tātad tas dala arī B. Izmantojot vairākas reizes nupat pierādīto lemu, redzam, ka p tad jādala vismaz viens B reizinātājs b. Bet visi reizinātāji paši ir pirmskaitļi, tātad arī b ir pirmskaitlis. Bet mēs zinām, ka arī p ir pirmskaitlis, tātad p ir jābūt vienādam ar b. Tātad tagad dalām A ar p un arī B ar p. Un iegūstam tādu rezultātu kā A* = B*. Atkal varam paņemt pirmskaitli p no pirmā reizinājuma A* un noskaidrot, ka tas ir vienāds ar kādu skaitli reizinājumā B*. Šādi turpinot, beigās redzam, ka abu reizinājumu pirmreizinātājiem jābūt tieši vienādiem. Tas pierāda, ka pozitīvu veselu skaitli kā pirmreizinātāju reizinājumu varam ierakstīt tikai vienā vienīgā veidā.
Jautājumi un atbildes
J: Kas ir aritmētikas fundamentālā teorēma?
A: Aritmētikas fundamentālā teorēma ir skaitļu teorijas teorēma, kas nosaka, ka katru veselu pozitīvu skaitli, kas lielāks par 1, var pierakstīt kā pirmskaitļu reizinājumu, un ir tikai viens veids, kā šo skaitli pierakstīt.
J: Kā šo teorēmu var izmantot?
A: Šo teorēmu var izmantot kriptogrāfijā.
J: Kas notiek, ja divi cilvēki atrod divus dažādus veidus, kā uzrakstīt vienu un to pašu skaitli?
A: Ja divi cilvēki atrod divus dažādus veidus, kā uzrakstīt vienu un to pašu skaitli, tad vienīgais, kas var atšķirties, ir pirmskaitļu rakstīšanas secība.
J: Kas ir faktorizācija?
A: Faktorializācija ir visu pirmskaitļu, kas veido doto skaitli, atrašana.
J: Vai 6936 ir pirmskaitļa piemērs?
A: Nē, 6936 nav pirmskaitlis; to var uzrakstīt kā 23 - 3 - 172.
Nē, 6936 nav pirmskaitlis; to var uzrakstīt kā 23 - 3 - 172.
Meklēt