Skaičių teorija

Įvadas į skaičių teoriją

Skaičių teorija yra matematikos šaka, tirianti sveikųjų skaičių savybes. Nors daugelis jos uždavinių gali atrodyti paprastai suformuluoti, kai kurių iš jų sprendimai yra išskirtinai sudėtingi. Tai sritis, kuri žavi matematikus tūkstančius metų, pradedant nuo tokių asmenų kaip Leonardas Oileris, Karlas Frydrichas Gausas ir Bernardas Rymanas, kurie laikomi vienais garsiausių istorijoje.

Turinys

Diofantinės lygtys

Diofantinės lygtys - teorija

Kas yra diofantinė lygtis?

Diofantinė lygtis – tai polinominė lygtis, kuriai ieškoma tik sveikųjų skaičių (arba kartais tik teigiamų sveikųjų skaičių) sprendinių. Pavyzdžiui, jei turite lygtį $x + y = 5$, joje yra be galo daug realiųjų sprendinių (pvz., $x=2.5, y=2.5$ ir t. t.), bet tik tam tikras skaičius teigiamų sveikųjų sprendinių (pvz., $(1,4), (2,3), (3,2), (4,1)$, ir t.t., priklausomai nuo to, ar leidžiami neigiami skaičiai ar nulis).

Tiesinės lygties forma (tiesinė kombinacija)

Diofantininė lygtis, pateikta forma \( ax+by=c \), vadinama tiesine kombinacija. Jei du tarpusavyje pirminiai sveikieji skaičiai \(a\) ir \(b\) užrašomi šia forma, kai \(c = 1\), lygtis turės begalinį sprendinių skaičių. Apskritai, kai \(dbd(a,b) = 1\), visada bus begalinis skaičius sprendinių. Jei \(dbd(a,b) \nmid c\), tai lygtis neturi sprendinių. Norėdami suprasti, kodėl, panagrinėkime lygtį \(3x - 9y = 3(x - 3y) = 17\). \(3\) yra kairiosios lygybės pusės daliklis (taip pat atkreipkite dėmesį, kad \(x-3y\) visada turi būti sveikasis skaičius). Tačiau \(17\) nėra \(3\) kartotinis, todėl sprendinių nėra. Dabar panagrinėkime atvejį, kai $c=0$. Taigi, $ax=-by$. Jei $a$ ir $b$ yra tarpusavyje pirminiai skaičiai, tai akivaizdu, kad visi sprendiniai visiems sveikiesiems skaičiams $k$ yra $(bk, -ak)$. Jei ne, mes tiesiog dalijame juos iš jų didžiausio bendro daliklio $dbd(a, b)$.

Pitagoro trejetai

Pitagoro trejetas yra trijų sveikųjų skaičių, tenkinančių Pitagoro teoremą ($a^2+b^2=c^2$), aibė. Yra trys pagrindiniai Pitagoro trejetų radimo metodai:

Pitagoro metodas
Jei $m>1$ yra nelyginis skaičius, tai $m, \frac {m^2 -1}{2}, \frac {m^2 + 1}{2}$ yra Pitagoro trejetas.

Platono metodas
Jei $n>1$, tai $2n, n^2 - 1, n^2 + 1$ yra Pitagoro trejetas.

Plačiau apie Pitagoro trejetus

Pelio lygtis

Pelio lygtis yra bet kokia diofantė lygtis, kurios forma yra \( x^2 - ny^2 = 1 \), kur n yra teigiamas nekvadratinis sveikasis skaičius, o x ir y ieškomi sveikieji sprendiniai. Žozefas Lui Lagranžas įrodė, kad tol, kol n nėra tobulas kvadratas, Pelio lygtis turi be galo daug skirtingų sveikųjų skaičių sprendinių.

Paskutinė Ferma teorema

Lygtis $x^n+y^n=z^n$ neturi teigiamų sveikųjų sprendinių - tai yra žinoma kaip paskutinė Ferma teorema sąlygai $n\geq3$. XVII a. Ferma, rašydamas knygą apie diofantines lygtis, iškėlė šią teoremą. Ferma padarė daug spėjimų ir pasiūlė daugybę „teoremų“, bet nebuvo iš tų, kurie užrašydavo įrodymus ar ką nors daugiau, išskyrus savo pilnai neužbaigtas mintis. Po jo mirties visos jo spėlionės buvo iš naujo įrodytos (teisingos arba klaidingos), išskyrus paskutinę Ferma teoremą. Po daugiau nei 350 metų nesėkmingų įrodymų teoremą galiausiai įrodė Andrew Wilesas, daugiau nei 7 metus dirbęs prie 200 puslapių įrodymo ir dar metus taisęs klaidą originaliame įrodyme.

Modulinė aritmetika

Kartais modulinė aritmetika gali būti naudojama įrodyti, kad duotoji diofantinė lygtis neturi jokių sprendinių. Tiksliau, jei parodysime, kad nagrinėjama lygtis niekada nebūna teisinga mod $m$, esant kokiam nors sveikajam skaičiui $m$, tada parodysime, kad lygtis yra klaidinga. Tačiau šis metodas negali būti naudojamas įrodyti, kad diofantinė lygtis turi sprendinių. Plačiau apie tai bus rašoma vėliau.

Kaip sprendžiamos diofantinės lygtys?

Diofantinių lygčių sprendimas dažnai reikalauja kūrybiškumo ir įvairių skaičių teorijos įrankių:


Daugeliui diofantinių lygčių vis dar nėra rasta bendrų sprendimo metodų, ir jos lieka atviromis matematinėmis problemomis, laukiančiomis tyrinėtojų.

Toliau apie diofantines lygtis

Diofantinės lygtys labai dažnai pasitaiko olimpiadiniuose uždaviniuose. Daugiau apie ją pasiskaityti ir paspręsti galite matematikos knygoje, kurią parašė 5 Lietuvos matematikai, ne kartą atstovavę Lietuvą tarptautinėse olimpiadose:
Plačiau apie diofantines lygtis (skyrelis "Diofantinės lygtys" - 35 psl.)

Diofantinės lygtys - uždaviniai

1. Raskite visus sveikųjų skaičių sprendinius lygčiai $2x + 4y = 8$.

Sprendimas

Pirmiausia, pastebime, kad visi koeficientai (2, 4 ir 8) dalijasi iš 2. Galime visą lygtį padalinti iš 2, kad supaprastintume: $$x + 2y = 4$$ Dabar galime išreikšti $x$ per $y$: $$x = 4 - 2y$$ Kadangi $x$ ir $y$ turi būti sveikieji skaičiai, mes galime pasirinkti bet kokį sveikąjį $y$, ir $x$ automatiškai bus sveikas skaičius.
Tarkime, $y = k$, kur $k$ yra bet koks sveikas skaičius ($k \in \mathbb{Z}$). Tada: $$x = 4 - 2k$$ Lygties $2x + 4y = 8$ sveikųjų skaičių sprendiniai yra $x = 4 - 2k$ ir $y = k$, kur $k$ yra bet koks sveikasis skaičius.

2. Raskite visus natūraliųjų skaičių sprendinius lygčiai $x^2 - y^2 = 24$.

Sprendimas

Ši lygtis yra kvadratų skirtumas, todėl ją galime faktorizuoti. $$(x - y)(x + y) = 24$$ Kadangi $x$ ir $y$ yra natūralieji skaičiai (t. y., teigiami sveikieji skaičiai $1, 2, 3, \ldots$), tai:
$x - y$ ir $x + y$ turi būti sveikieji skaičiai.
$x + y > 0$.
Kadangi $x + y > x - y$, tai $(x+y)$ turi būti didesnis faktorius.
Taip pat, $(x+y) - (x-y) = 2y$, o tai yra lyginis skaičius. Vadinasi, $x-y$ ir $x+y$ turi būti arba abu lyginiai, arba abu nelyginiai. Kadangi jų sandauga (24) yra lyginė, abu daugikliai turi būti lyginiai.

Išvardinkime visas 24 skaičiaus lyginių dauginamųjų poras, kur didesnis dauginamasis yra antras:
$x - y = 2$ ir $x + y = 12$
$x - y = 4$ ir $x + y = 6$

Dabar spręskime šias tiesinių lygčių sistemas:

1 atvejis:
$$x - y = 2$$ $$x + y = 12$$ Sudėję lygtis: $(x-y) + (x+y) = 2 + 12 \implies 2x = 14 \implies x = 7$. Įstačius $x=7$ į $x-y=2$: $7-y=2 \implies y=5$. Sprendinys: $(x,y) = (7,5)$. Patikrinimas: $7^2 - 5^2 = 49 - 25 = 24$. Tinka.

2 atvejis:
$$x - y = 4$$ $$x + y = 6$$ Sudėję lygtis: $(x-y) + (x+y) = 4 + 6 \implies 2x = 10 \implies x = 5$. Įstačius $x=5$ į $x-y=4$: $5-y=4 \implies y=1$. Sprendinys: $(x,y) = (5,1)$. Patikrinimas: $5^2 - 1^2 = 25 - 1 = 24$. Tinka.

Lygties $x^2 - y^2 = 24$ natūraliųjų skaičių sprendiniai yra $(7,5)$ ir $(5,1)$.

3. Raskite visus sveikųjų skaičių sprendinius lygčiai $xy - 2x - 3y = 1$.

Sprendimas

Mūsų tikslas yra pridėti tam tikrą konstantą abiem lygties pusėms, kad kairiąją pusę būtų galima faktorizuoti į dviejų skliaustų sandaugą.

Išskiriame $x$ iš pirmų dviejų narių: $$x(y - 2) - 3y = 1$$ Norint, kad atsirastų dar vienas $(y-2)$ narys, pridėsime 6 abiem pusėms (nes $-3 \cdot (-2) = 6$): $$x(y - 2) - 3y + 6 = 1 + 6$$ $$x(y - 2) - 3(y - 2) = 7$$ Dabar galime iškelti $(y-2)$ kaip bendrą dauginamąjį: $$(x - 3)(y - 2) = 7$$ Kadangi $x$ ir $y$ yra sveikieji skaičiai, $(x-3)$ ir $(y-2)$ taip pat turi būti sveikieji skaičiai, o jų sandauga lygi 7. Skaičiaus 7 dalikliai yra $1, -1, 7, -7$. Išvardinkime visas galimas poras:

1 atvejis: $$x - 3 = 1 \implies x = 4$$ $$y - 2 = 7 \implies y = 9$$ Sprendinys: $(4, 9)$. Patikrinimas: $4 \cdot 9 - 2 \cdot 4 - 3 \cdot 9 = 36 - 8 - 27 = 1$. Tinka.

2 atvejis: $$x - 3 = 7 \implies x = 10$$ $$y - 2 = 1 \implies y = 3$$ Sprendinys: $(10, 3)$. Patikrinimas: $10 \cdot 3 - 2 \cdot 10 - 3 \cdot 3 = 30 - 20 - 9 = 1$. Tinka.

3 atvejis: $$x - 3 = -1 \implies x = 2$$ $$y - 2 = -7 \implies y = -5$$ Sprendinys: $(2, -5)$. Patikrinimas: $2 \cdot (-5) - 2 \cdot 2 - 3 \cdot (-5) = -10 - 4 + 15 = 1$. Tinka.

4 atvejis: $$x - 3 = -7 \implies x = -4$$ $$y - 2 = -1 \implies y = 1$$ Sprendinys: $(-4, 1)$. Patikrinimas: $(-4) \cdot 1 - 2 \cdot (-4) - 3 \cdot 1 = -4 + 8 - 3 = 1$. Tinka.

Lygties $xy - 2x - 3y = 1$ sveikųjų skaičių sprendiniai yra $(4, 9)$, $(10, 3)$, $(2, -5)$ ir $(-4, 1)$.

Daugiau uždavinių ir teorijos galite rasti matematikos knygoje, kurią parašė 5 Lietuvos matematikai, ne kartą atstovavę Lietuvą tarptautinėse olimpiadose:
Plačiau apie diofantines lygtis (skyrelis "Diofantinės lygtys" - 35 psl.)

Modulinė aritmetika

Modulinė aritmetika - teorija

Kas yra modulis?

Modulis ($n$) - tai skaičius, pagal kurį mes "apverčiame" skaičiavimą. Tai yra daliklis, iš kurio dalijame, ir mus domina tik dalybos liekana. Modulis $n$ visada yra teigiamas sveikasis skaičius.

Pavyzdys:
$17 \equiv 5 \pmod{12}$, nes ir 17, ir 5, padalinti iš 12, duoda liekaną 5. Taip pat, $17 - 5 = 12$, o 12 dalijasi iš 12.

Prieš pradedant mokytis modulinę aritmetiką, siūloma perskaityti šį įvadą, kad geriau suprasti, kas tai yra:
Įvadas į modulinę aritmetiką

Modulinės aritmetikos veiksmai

Modulinėje aritmetikoje galima atlikti pagrindinius aritmetinius veiksmus: sudėtį, atimtį ir daugybą. Svarbiausia taisyklė yra ta, kad kiekvieno veiksmo rezultatas yra vėlgi redukuojamas iki liekanos pagal nurodytą modulį.

Tarkime, turime du skaičius $a$ ir $b$, ir modulį $n$.

1. Sudėtis:

Jei $a \equiv r_1 \pmod{n}$ ir $b \equiv r_2 \pmod{n}$, tada: $$(a + b) \equiv (r_1 + r_2) \pmod{n}$$ Pavyzdys:
Kokia bus valanda po 5 valandų, jei dabar 10 valanda? $10 + 5 = 15$. $15 \pmod{12} \equiv 3 \pmod{12}$.
Atsakymas: 3 valanda.

2. Atimtis:

Jei $a \equiv r_1 \pmod{n}$ ir $b \equiv r_2 \pmod{n}$, tada: $$(a - b) \equiv (r_1 - r_2) \pmod{n}$$ Pavyzdys:
$20 - 7 \pmod{5}$
$20 \equiv 0 \pmod{5}$
$7 \equiv 2 \pmod{5}$
$(20 - 7) \equiv (0 - 2) \equiv -2 \equiv 3 \pmod{5}$ (nes $-2 + 5 = 3$).
Atsakymas: 3.

3. Daugyba:

Jei $a \equiv r_1 \pmod{n}$ ir $b \equiv r_2 \pmod{n}$, tada: $$(a \cdot b) \equiv (r_1 \cdot r_2) \pmod{n}$$ Pavyzdys:
Apskaičiuokime $4 \cdot 7 \pmod{9}$.
$4 \cdot 7 = 28$.
$28 \pmod{9} \equiv 1 \pmod{9}$ (nes $28 = 3 \cdot 9 + 1$).
Atsakymas: 1.

Kodėl modulinė aritmetika svarbi?

Modulinė aritmetika nėra tik įdomus matematinis žaidimas - ji turi milžinišką praktinę reikšmę.

Kriptografija ir duomenų apsauga: ši sritis yra visų modernių šifravimo algoritmų pagrindas. Viešojo rakto kriptografija, tokia kaip RSA algoritmas, remiasi modulinės aritmetikos ir didelių pirminių skaičių savybėmis. Ši matematika užtikrina, kad internetinės operacijos, el. laiškai ir vartotojų asmeninė informacija būtų saugūs.

Klaidų taisymo kodai: modulinė aritmetika naudojama duomenų perdavime ir saugojime (pvz., CD, DVD, QR kodai), kad būtų galima aptikti ir ištaisyti klaidas, atsirandančias dėl triukšmo ar pažeidimų.

Kompiuterių mokslas: modulinė aritmetika naudojama maišos lentelėse (hash tables), atsitiktinių skaičių generatoriuose, cikliniuose algoritmuose ir daugelyje kitų kompiuterinių programų.

Mažoji Ferma teorema

Jei $p$ yra pirminis skaičius, tai bet kokiam sveikajam skaičiui $a$, kuris nesidalija iš $p$, turime: $$ a^{p-1} \equiv 1 \pmod{p} $$ Plačiau apie Ferma teoremą ir jai panašią Oilerio teoremą (skyrelis "Oilerio teorema" - 14 psl.)

Kinų liekanų teorema

Įsivaizduokite situaciją: žinote, kad ieškomą skaičių, padalijus iš 3, gaunate liekaną 2, padalijus iš 5, gaunate liekaną 3, o padalijus iš 7, gaunate liekaną 2. Ar egzistuoja toks skaičius? Jei taip, tai koks? Būtent į tokius klausimus atsako Kinų liekanų teorema – galingas skaičių teorijos įrankis, leidžiantis rasti sveikąjį skaičių, kuris tenkina keletą sąlygų vienu metu.

Kinų liekanų teorema teigia, kad jei turime kelias sąlygas su liekanomis, kurių moduliai yra tarpusavyje pirminiai (t. y., jų didžiausias bendras daliklis yra 1), tada egzistuoja unikalus sprendinys moduliu šių modulių sandauga.

Tarkime, turime tokią sistemą:

$$x \equiv a_1 \pmod{n_1}$$$$x \equiv a_2 \pmod{n_2}$$$$\ldots$$ $$x \equiv a_k \pmod{n_k}$$ Jei $n_1, n_2, \ldots, n_k$ yra poromis tarpusavyje pirminiai skaičiai (t.y., $\text{DBD}(n_i, n_j) = 1$ bet kuriems $i \ne j$), tada egzistuoja unikalus sprendinys $x$ moduliu $N = n_1 \cdot n_2 \cdot \ldots \cdot n_k$.
Plačiau apie Kinų liekanų teoremą (skyrelis "Kinų liekanų teorema" - 19 psl.)

Toliau apie modulinę aritmetiką

Modulinės aritmetikos triukus galima labai dažnai panaudoti olimpiadiniuose uždaviniuose. Daugiau apie ją pasiskaityti ir paspręsti galite matematikos knygoje, kurią parašė 5 Lietuvos matematikai, ne kartą atstovavę Lietuvą tarptautinėse olimpiadose:
Plačiau apie modulinę aritmetiką (skyrelis "Dalumas" - 2 psl.)

Modulinė aritmetika - uždaviniai

1. Kokia savaitės diena bus po 100 dienų, jei šiandien yra trečiadienis?

Sprendimas

Savaitė turi 7 dienas, todėl tai yra modulinės aritmetikos problema su moduliu 7. Trečiadienis yra trečia savaitės diena, tad galime jam priskirti skaičių 3 (pradedant nuo sekmadienio = 0, pirmadienio = 1, antradienio = 2 ir t.t. arba tiesiog trečiadienis = 3). Mums reikia rasti $3 + 100 \pmod{7}$.

Apskaičiuojame 100 liekaną moduliu 7: $$100 = 14 \cdot 7 + 2$$ Taigi, $100 \equiv 2 \pmod{7}$.

Dabar pridėsime šią liekaną prie trečiadienio dienos skaičiaus: $$3 + 100 \equiv 3 + 2 \pmod{7}$$ $$3 + 2 = 5$$ Taigi, $5 \pmod{7}$.

Jei trečiadienis yra 3, ketvirtadienis yra 4, tai penktadienis bus 5. Po 100 dienų bus penktadienis.

2. Koks yra skaičiaus $13^{20}$ paskutinysis skaitmuo?

Sprendimas

Rasti skaičiaus paskutinįjį skaitmenį reiškia rasti to skaičiaus liekaną dalijant iš 10. Taigi, mes ieškome $13^{20} \pmod{10}$.

Pirmiausia, pastebime, kad $13 \equiv 3 \pmod{10}$. Todėl $13^{20} \equiv 3^{20} \pmod{10}$.

Apskaičiuojame laipsnius moduliu 10 (ieškome ciklo):

$3^1 \equiv 3 \pmod{10}$
$3^2 \equiv 9 \pmod{10}$
$3^3 \equiv 3^2 \cdot 3^1 \equiv 9 \cdot 3 = 27 \equiv 7 \pmod{10}$
$3^4 \equiv 3^3 \cdot 3^1 \equiv 7 \cdot 3 = 21 \equiv 1 \pmod{10}$

Pastebime, kad $3^4 \equiv 1 \pmod{10}$. Ciklo ilgis yra 4. Dabar galime suskaidyti $20$ laipsnį pagal ciklo ilgį: $20 = 4 \cdot 5$. $$3^{20} = (3^4)^5 \pmod{10}$$ Kadangi $3^4 \equiv 1 \pmod{10}$, $$(3^4)^5 \equiv 1^5 \pmod{10}$$ $$1^5 \equiv 1 \pmod{10}$$ Taigi, skaičiaus $13^{20}$ paskutinysis skaitmuo yra 1.

3. Žinant, kad $x \equiv 2 \pmod{5}$ ir $x \equiv 3 \pmod{7}$, raskite mažiausią teigiamą sveikąjį skaičių $x$.

Sprendimas

Šis uždavinys yra klasikinė Kinų liekanų teoremos taikymo problema, kai modulių (5 ir 7) didžiausias bendras daliklis yra 1 (jie yra tarpusavyje pirminiai).

Turime dvi sąlygas:

$x \equiv 2 \pmod{5}$
$x \equiv 3 \pmod{7}$

Iš pirmosios galime užrašyti $x$ kaip $x = 5k + 2$, kur $k$ yra sveikas skaičius. Dabar šią išraišką įstatome į antrąją sąlygą: $$5k + 2 \equiv 3 \pmod{7}$$ Atsimame 2 iš abiejų pusių: $$5k \equiv 1 \pmod{7}$$ Dabar mums reikia rasti skaičių, kuris, padaugintas iš 5, duotų liekaną 1 moduliu 7. Galime išbandyti $k$ reikšmes:

Jei $k=1$, $5 \cdot 1 = 5 \not\equiv 1 \pmod{7}$
Jei $k=2$, $5 \cdot 2 = 10 \equiv 3 \pmod{7}$
Jei $k=3$, $5 \cdot 3 = 15 \equiv 1 \pmod{7}$
Taigi, radome, kad $k \equiv 3 \pmod{7}$. Tai reiškia, kad $k$ gali būti $3, 10, 17, \ldots$ (t.y., $k = 7m + 3$, kur $m$ yra sveikas skaičius).

Kadangi mums reikia mažiausio teigiamo $x$, imame mažiausią $k$ reikšmę, t.y., $k=3$.
Dabar įstatome $k=3$ atgal į $x = 5k + 2$: $$x = 5(3) + 2$$$$x = 15 + 2$$$$x = 17$$ Patikrinkime atsakymą:

$17 \div 5 = 3$ su liekana $2$ (t.y., $17 \equiv 2 \pmod{5}$). Tinka.
$17 \div 7 = 2$ su liekana $3$ (t.y., $17 \equiv 3 \pmod{7}$). Tinka.

Mažiausias teigiamas sveikasis skaičius $x$, tenkinantis duotas sąlygas, yra 17.

Daugiau uždavinių ir teorijos galite rasti matematikos knygoje, kurią parašė 5 Lietuvos matematikai, ne kartą atstovavę Lietuvą tarptautinėse olimpiadose:
Plačiau apie modulinę aritmetiką (skyrelis "Dalumas" - 2 psl.)

Pirminiai skaičiai

Pirminiai skaičiai - teorija

Skaidymas pirminiais dauginamaisiais

Kiekvienas natūralusis skaičius, didesnis už 1, gali būti vieninteliu būdu išreikštas kaip pirminių skaičių sandauga, neatsižvelgiant į dauginamųjų tvarką.

Pavyzdys:
Skaičius 30 gali būti užrašytas tik kaip $2 \cdot 3 \cdot 5$. Jokių kitų pirminių dauginamųjų derinių, kurie sudarytų 30, nėra. Skaičius 12 gali būti užrašytas tik kaip $2 \cdot 2 \cdot 3$ arba $2^2 \cdot 3$.

Pirminių skaičių savybės

Pirminis skaičius yra natūralusis skaičius, didesnis už 1, turintis lygiai du teigiamus daliklius: save patį ir vienetą. Pavyzdžiui, 2, 3, 5, 7, 11, 13 yra pirminiai skaičiai.

Skaičius 1 nėra nei pirminis, nei sudėtinis.

Pirminių skaičių yra be galo daug (tai įrodė Euklidas daugiau nei prieš 2000 metų).

Nėra paprastos formulės, kuri generuotų visus pirminius skaičius, ir jie atrodo paskirstyti tarp natūraliųjų skaičių gana atsitiktinai, tačiau su tam tikrais dėsningumais, kuriuos nagrinėja pirminių skaičių teorema. Apie ją daugiau pasiskaityti galite čia:
Plačiau apie pirminių skaičių teoremą

Egzistuoja daugybė neišspręstų ar neįrodytų problemų, susijusių su pirminiais skaičiais, pavyzdžiui:

Goldbacho hipotezė: ar kiekvienas lyginis skaičius, didesnis už 2, gali būti užrašytas kaip dviejų pirminių skaičių suma? (pvz., $10 = 3 + 7$, $20 = 3 + 17$ ir t. t.).

Pirminių dvynių hipotezė: ar yra be galo daug pirminių skaičių porų, kurios skiriasi 2 (pvz., 3 ir 5, 11 ir 13, 17 ir 19)?

Skaidymo pirminiais dauginamaisiais sunkumai

Kol kas nėra žinomo efektyvaus algoritmo, kuris leistų greitai faktorizuoti labai didelius skaičius. Būtent šiuo sunkumu remiasi daugelis šiuolaikinių kriptografinių algoritmų, tokių kaip RSA.

RSA algoritmas remiasi tuo, kad lengva sudauginti du didelius pirminius skaičius, bet be galo sunku (užtrunka milžiniškai daug laiko net galingiems kompiuteriams) išskaidyti jų sandaugą atgal į tuos du pirminius skaičius. Tai užtikrina viešojo rakto šifravimo saugumą.

Daugiau apie pirminius skaičius

Jeigu norite sužinoti daugiau apie pirminius skaičius, galite pasiskaityti čia:
Plačiau apie pirminius skaičius

Pirminiai skaičiai - uždaviniai

1. Išskaidykite skaičių 72 pirminiais dauginamaisiais.

Sprendimas

Norėdami išskaidyti skaičių į pirminius dauginamuosius, sistemingai dalijame jį iš mažiausių pirminių skaičių (2, 3, 5, 7, ...) tol, kol gausime 1.

Dalijame iš 2: $$72 \div 2 = 36$$ Vėl dalijame iš 2: $$36 \div 2 = 18$$ Dar kartą dalijame iš 2: $$18 \div 2 = 9$$ Dabar dalijame iš 3 (nes iš 2 jau nesidalija): $$9 \div 3 = 3$$ Dar kartą dalijame iš 3: $$3 \div 3 = 1$$ Surinkus visus daliklius: $72 = 2 \cdot 2 \cdot 2 \cdot 3 \cdot 3$. Tai galime užrašyti laipsnių pavidalu: $72 = 2^3 \cdot 3^2$.

Skaičiaus 72 skaidymas pirminiais dauginamaisiais yra $2^3 \cdot 3^2$.

2. Nustatykite, ar skaičius 137 yra pirminis skaičius.

Sprendimas

Norėdami patikrinti, ar skaičius $N$ yra pirminis, mums pakanka išbandyti daliklius iš visų pirminių skaičių, kurie yra mažesni arba lygūs $\sqrt{N}$. Jei $N$ nesidalija iš nė vieno iš šių pirminių skaičių, tada $N$ yra pirminis. $$11^2 \lt 137 \lt 12^2$$ $$11 \lt \sqrt{137} \lt 12$$ Taigi, mums reikia patikrinti pirminius skaičius, mažesnius arba lygius 11: tai yra 2, 3, 5, 7, 11.

Iš 2: 137 yra nelyginis skaičius, tad nesidalija iš 2.
Iš 3: Skaitmenų suma yra $1+3+7 = 11$, o 11 nesidalija iš 3, tad 137 irgi nesidalija iš 3.
Iš 5: Skaičiaus paskutinis skaitmuo nėra 0 arba 5, tad nesidalija iš 5.
Iš 7: $137 \div 7 = 19$ su liekana $4$ (nes $7 \cdot 19 = 133$). Nesidalija iš 7.
Iš 11: $137 \div 11 = 12$ su liekana $5$ (nes $11 \cdot 12 = 132$). Nesidalija iš 11.

Kadangi 137 nesidalija iš nė vieno pirminio skaičiaus, mažesnio už $\sqrt{137}$, skaičius 137 yra pirminis.

137 yra pirminis skaičius.

3. Du natūralieji skaičiai $A$ ir $B$ yra tokie, kad $A \cdot B = 180$ ir jų didžiausias bendras daliklis (DBD) yra 6. Raskite visas galimas poras $(A, B)$.

Sprendimas

Žinome, kad $A \cdot B = 180$ ir $\text{DBD}(A, B) = 6$. Mes taip pat žinome formulę, siejančią DBD, MBK (mažiausią bendrą kartotinį) ir skaičių sandaugą: $$A \cdot B = \text{DBD}(A, B) \cdot \text{MBK}(A, B)$$Įstatykime žinomas reikšmes:$$180 = 6 \cdot \text{MBK}(A, B)$$ Tada $\text{MBK}(A, B) = \frac{180}{6} = 30$.

Dabar, jei $\text{DBD}(A, B) = 6$, tai reiškia, kad $A$ ir $B$ gali būti užrašyti kaip:
$A = 6x$
$B = 6y$
kur $x$ ir $y$ yra tarpusavyje pirminiai skaičiai (t.y., $\text{DBD}(x, y) = 1$). Jei jie nebūtų tarpusavyje pirminiai, didžiausias bendras daliklis būtų didesnis nei 6.

Įstatykime šias išraiškas į $A \cdot B = 180$: $$(6x) \cdot (6y) = 180$$ $$36xy = 180$$Padalijame iš 36:$$xy = \frac{180}{36}$$ $$xy = 5$$ Dabar ieškome visų porų teigiamų sveikųjų skaičių $(x, y)$, kurių sandauga yra 5 ir kurios yra tarpusavyje pirminės. Kadangi 5 yra pirminis skaičius, jo vienintelės natūraliųjų skaičių dauginamųjų poros yra $(1, 5)$ ir $(5, 1)$. Abi šios poros yra tarpusavyje pirminės.

1 atvejis: $x = 1, y = 5$
Tada $A = 6x = 6 \cdot 1 = 6$
Ir $B = 6y = 6 \cdot 5 = 30$
Patikrinimas: $6 \cdot 30 = 180$. $\text{DBD}(6, 30) = 6$.

2 atvejis: $x = 5, y = 1$
Tada $A = 6x = 6 \cdot 5 = 30$
Ir $B = 6y = 6 \cdot 1 = 6$
Patikrinimas: $30 \cdot 6 = 180$. $\text{DBD}(30, 6) = 6$.

Yra dvi galimos poros $(A, B)$: $(6, 30)$ ir $(30, 6)$.

Daugiau uždavinių ir teorijos galite rasti matematikos knygoje, kurią parašė 5 Lietuvos matematikai, ne kartą atstovavę Lietuvą tarptautinėse olimpiadose:
Plačiau apie nelygybes (skyrelis "Nelygybės" - 42 psl.)

Apibendrinimas

Praėję šį skyrių, jūs įgavote pagrindus ir esate pasiruošę toliau gilintis bei spręsti olimpiadinės skaičių teorijos uždavinius. Sėkmės!

Papildomi ištekliai