Pateiksime kelias pagrindines teoremas iš skaičių teorijos, susijusias su pirminiais skaičiais.


Pagrindinė aritmetikos teorema

Taip pat skaitykite: Fundamentaliosios matematikos teoremos

Bet kuris sveikas skaičius, didesnis už 1, gali būti tik vieninteliu būdu išreikštas pirminių skaičių sandauga.

Pvz., 6926 = 23 x 3 x 172

Faktiškai, ši teorema išreiškia teiginį, kad pirminiai skaičiai yra svarbiausi skaičiai, blokai, iš kurių sudaromi visi skaičiai (1 nelaikomas pirminiu skaičiumi).

Skaičiaus sudarymas pirminių skaičių sandauga (faktorizacija) įrodomas nesunkiai, o tokio sudarymo unikalumas reikalauja kiek daugiau pastangų. Kai kurie įrodymai remiasi Euklido lema, teigiančia, kad jei pirminis skaičius p dalija dviejų skaičių sandaugą a x b, tai jis tikrai dalija arba a, arba b. Kadangi sveikų skaičių sandauga yra tiek komutatyvi, tiek asociatyvi, tai visai nesvarbu, kokia eilės tvarka surašysime daugiklius, - paprastai jie surašomi nuo mažiausio link didžiausio (kaip pavyzdyje).

Žinant dviejų skaičių faktorizacijas nesunku surasti bendrą didžiausią jų daliklį. Tačiau jei faktorizacija nežinoma, naudojant Euklido algoritmą dažniausiai atliekama mažiau skaičiavimų.

Pagrindinė aritmetikos teorema yra apibendrinama įvairiems kitiems kontekstams, pvz., žiedų teorijoje.

Įdomu, kad senovės egiptiečiai praktiškai naudojo kai kuriuos daugybos aspektus, pvz., mažiausią bendrą daugiklį (žr. Rindo papirusas).

Faktorizacijos įrodymas

Teoremą praktiškai įrodė dar Euklidas („Elementai“, 7 kn., teiginiai 30 ir 32), nors pilną ir teisingą jos įrodymą pirmąkart pateikė K.F. Gausas.

Tarkime, kad yra mažiausias teigiamas sveikas skaičius n (didesnis už 1), kurio negalima išreikšti pirminių skaičių sandauga. Jis negali būti pirminiu skaičiumi, nes tada jį galima būtų išreikšti pirminiais skaičiais, t.y. juo pačiu.

Vadinasi, n galima užrašyti kaip dviejų skaičių (didesnių nei 1) sandauga, t.y. n = a x b. Čia a ir b yra mažesni už n. Kadangi n buvo mažiausias skaičius, neišreiškiamas pirminių skaičių sandauga, tai a ir b turi būti taip išreiškiami. Tačiau tada ir n gali būti išreiškiamas pirminių skaičių, kuriais išreiškiami a ir b, sandauga, o tai prieštarauja pirminei prielaidai.

Unikalumo įrodymas

Tegu s yra mažiausias teigiamas sveikas skaičius (didesnis už 1), kuris gali būti užrašytas dviejų skirtingų pirminių skaičių sekų sandaugomis: t.y., s = p1 x p2 x ... pm ir s = q1 x q2 x ... qn.

Tada, pagal Euklido lemą, p1 dalija arba q1, arba q2 x ... qn. Bet kadangi tiek q1 , tiek q2 x ... qn yra mažesni už s, tai kiekvieno jų faktorizacija yra unikali (t.y., išreiškiama vieninteliu būdu), nes s yra mažiausias skaičius, kuriam tai, pagal mūsų prielaidą, tai negalioja. Todėl p1 turi sutapti su kažkuriuo qj. Tačiau pašalinę p1 ir qj ir pradinių lygybių, gausime mažesnį skaičių nei s, išreiškiamą dviem skirtingomis pirminių skaičių sandaugomis, kas prieštarauja mūsų prielaidai (kad s yra mažiausias toks skaičius).

Pastaba: tai galima įrodyti ir kitais būdais.

Euklido lema

Jei pirminis skaičius p dalija dviejų sveikų skaičių sandaugą a x b, tai jis tikrai dalija arba a, arba b.

Ši svarbi lema susijusi su dalumu ir pirminiais skaičiais. Lema suformuluota 30-tu teiginiu Euklido “Elementų“ 7-oje knygoje. Gana netikėtai jos įrodymas yra pakankamai sudėtingas.

Pavyzdys. Tarkim N=154=14x11, o p=7. Tada arba dx7=14, arba dx7=3. Aišku, kad mūsų pavyzdžio atveju 14 dalijasi iš 7 (t.y., d=2).

Įrodymas

Šiuolaikinis įrodymas remiasi E. Bezout lema.

Tegu a x b yra dalus iš p, tačiau a nėra dalus iš p. Tada a ir p yra tarpusavyje pirminiai, todėl, pagal Bezout lemą, atsiras tokie sveiki skaičiai u ir v, kad
axu+pxv=1

Padauginę abi lygybės puses iš b, gausime
(axb)xu+pxvxb=b

Abu lygybės kairiosios pusės nariai dalūs iš p (nes pagal sąlygą axb dalus iš p), todėl ir dešinioji pusė (t.y., b) yra dali iš p – ką ir reikėjo įrodyti.

Analogiškai samprotaudami įrodome, kad, kai b nėra dalus iš p, tada a yra dalus iš p.

Alternatyvus įrodymas

Šiame įrodyme nebus remiamasi Bezout lema – tik, paprastumo dėlei, laikysime, kad a ir b yra teigiami.

Tarkim, kad teiginys yra klaidingas ir p yra mažiausias pirminis skaičius dalantis axb, tačiau nedalantis nei a, nei b. Tokiam p, paimkime ir a bei b mažiausiais, kokie tik galimi – tada lema turi būti teisinga visiems mažesniems skaičiams.

Pirmiausia nustatome, kad a>1. Kai a=0, tada p dalo a, - prieštaravimas. Kai a=1, tada axb=b, o tada p dalo b pagal prielaidą.

Tada įrodome, kad a yra pirminis skaičius. Jei taip nebūtų, galėtume užrašyti a=cxd, kur c<a. Kadangi paėmėme a mažiausią, kuriam mūsų p negalioja teiginys, tai teiginys turi galioti skaičiams c ir dxb (nes axb=(cxd)xb=cx(dxb)), t.y., p dalo c arba dxb. Jei jis dalo c, tada jis turi dalyti ir a, nes a=cxd - o tai prieštaravimas prielaidai. Taigi p dalo dxb. O kadangi d<a, vėl pritaikome prielaidą, pagal kurią p dalo arba d, arba b. p negali dalinti b pagal hipotezę, todėl jis dalo d. Tačiau tada jis turi dalinti ir a=cxd - ir vėl turime prieštaravimą.

Toliau įrodome, kad a<p. Kitaip būtų teisinga z=a-p>=0, o iš čia zxb=(a-p)xb=axb-pxb. Kadangi pagal hipotezę p dalo axb, tai, iš to, kad akivaizdžiai dalo pxb, turi dalyti ir skirtumą, kuris yra zxb. Bet z<a, todėl, pagal prielaidą, p dalo arba z arba b. b dalinti negali pagal prielaidą, tad p dalo z. Tad p dalo z+p=a - o tai yra prieštaravimas.

Kadangi a yra pirminis skaičius, a<p ir p yra mažiausias pirminis skaičius, kuriam teiginys yra klaidingas, darome išvadą, kad teiginys teisingas a, t.y., jei a dalo bet kokią sandaugą fxg, tai a dalo arba f arba g.

Dabar, kadangi p dalo axb, galima rasti sveiką skaičių k, kad axb=kxp. Tai rodo, kad a dalo kxp. Kadangi teiginys teisingas a, tai a dalo arba k, arba p. Tačiau p yra pirminis, todėl a dalo k. Tad galime kažkokiam sveikam skaičiui q užrašyti k=axq, taigi axb=kxp=axqxp. Padaliję lygybę iš a, gauname b=qxp. O tai reiškia, kad p dalo b, kas prieštarauja mūsų hipotezei (dėl p pasirinkimo). Taigi, įrodyta, kad teiginys teisingas.

Euklido teorema

Yra be galo daug pirminių skaičių.

Įrodymas

Euklido įrodymas (IX 20): Imkime bet kokį baigtinį pirminių skaičių sąrašą: p1, p2, p3, ... pn. Įrodysime, kad egzistuoja ir daugiau pirminių skaičių.

Tegu P yra visų šių pirminių skaičių sandauga. Paimkime q = P + 1. q gali būti arba pirminis, arba ne.

Jei q būtų pirminis, tada mūsų sąrašas būtų nepilnas, nes q nėra jame, kadangi yra didesnis už bet kurį sąrašo elementą.

Jei q nėra pirminis, tada egzistuoja kuris nors pirminis skaičius p, kuris dalo q. Tačiau tada jis negali būti mūsų sąraše. Mat tada jis dalytų ir P+1, ir P. Taigi turėtų dalyti ir jų skirtumą, t.y. (P+1) – P = 1. Tačiau joks pirminis skaičius nedalo 1.

Taigi įrodėme, kad bet kokiam baigtiniam pirminių skaičių sąrašui galime rasti pirminį skaičių, kuris nėra tame sąraše.

Oilerio įrodymas: šveicarų matematikas L. Euleris įrodė teoremą remdamasis pagrindine aritmetikos teorema, kad bet kurį sveiką skaičių galima vieninteliu išreikšti pirminių skaičių sandauga.

Tegu P yra visų pirminių skaičių aibė. Tada
Euler formula for Euclid theorem

Pirma lygybė gaunama iš sandaugos kiekvieno nario geometrinėje sekoje formulės. Antrajai lygybei – paskirstykite sandaugą per sumą: tada kiekviena pirminių skaičių sandauga bus tik kartą, tad pagal pagrindinę aritmetikos teoremą, suma yra lygi visų skaičių sumai.

Suma dešinėje yra harmoninė eilutė, kuri diverguoja, kad ir sandauga kairėje diverguoja. Kadangi kiekvienas sandaugos narys yra baigtinis, jos narių skaičius turi būti begalinis, taigi pirminių skaičių yra be galo daug.

Taip pat skaitykite: Fundamentaliosios matematikos teoremos

Pastaba: Yra ir daugiau šios teoremos įrodymų.Ateityje bus galima pateikti ir juos.

Skaičiaus daliklių kiekis

Iš karto kyla klausimas – o ar galim nuspėti, kiek teigiamų daliklių turi sveikas skaičius n?

Šis skaičius žymimas d(n) arba t(n), o w(n) yra žymimas skaičiaus pirminių daliklių kiekis. Pavyzdžiui d(14) = 4, nes 14 dalo 1, 2, 7, 14;  o w(14)=2, nes tik 2 ir 14 yra pirminiai.

Pirmiausia pastebėsime, kad aišku, kad d(n) <= n
Bet ar galima įrodyti tiksliau? Aišku, ir grubus įvertinimas, kai n yra gana didelis, yra d(n)= log n

O 1838 m. Dirichlė pateikė tikslesnę įverčio formulę visiems sveikiems skaičiams nuo 1 iki n, kuri panaudoja konstantą g:
Daliklių skaičius
kuri apytiksliai reiškia ln n+0,15443…

Toji konstanta g pavadinta L. Oilerio ir Lorenco Maskeronio (1750-1800) vardu (t.y. Oilerio-Maskeroni). Ji dar vadinama ir Oilerio konstanta. Ji pirmąkart pasirodė 1734 m. L. Oilerio straipsnyje, o 1790 m. ją naudojo italas L. Maskeronis. Tačiau nė vienas jų nežymėjo kaip g. Šis žymėjimas atsirado vėliau dėl ryšio su gama funkcija (pvz., taip ją 1835 m. žymėjo vokiečių matematikas K.A. Bretšneideris, o kiek vėliau savo vadovėlyje ir A. de Morganas). Ji pasirodo daugelyje matematikos vietų, tačiau vis dar nenustatyta, ar g yra algebrinis ar transcendentinis skaičius – ir net ar jis iracionalus.

Pirminių daliklių skaičius

Pirmiausia atkreipsime dėmesį, kad w funkcija yra adityvi, t.y. w(ab)= w(a)+ w(b), kai a ir b yra tarpusavyje pirminiais.

1917 m. G.H. Hardis ir S. Ramanudžanas įrodė, kad w(n) asimptotiškai lygi ln ln n
1933 m. Paulis Turanas (1910-1976) pateikė naują įrodymą, sutelpantį į vieną puslapį.

Plačiau žr. J. Havil. Gamma: Exploring Euler's Constant, 2003

Dalyba iš nulio
Pirminiai skaičiai
Pitagoro teorema
Kvadratinė lygtis
Aritmetikos pagrindai
Santykis ir proporcija
Didžioji Ferma teorema
Kokiu greičiu skriejame?
Euklidas iš Aleksandrijos
Matematikai: Pjeras Ferma
Didžiausias bendras daliklis
Iniciatyva: Matematikos keliu
Gauso skaičių teorijos kursas
Skaičiai – apžvalga/ pradmenys
Fundamentaliosios matematikos teoremos
Kaip Pitagoro teoremą įrodė Einšteinas
Kai kurios pirminių skaičių formos
Alef paslaptis: begalybės paieškos
Matematika Egipte: Rindo papirusas ir kt.
Naujas pirminių skaičių dėsningumas
Pagrindinės algebrinės struktūros
A. Puankarė. Mokslas ir hipotezė
Kaip supakuoti standžiau?
Harmoninės eilutės
Ar viskas čia taip?
Hiparchas iš Rodo
Algebros istorija
Beal'o hipotezė
Erdvės formos
Vartiklis