Skaitļu teorija

1. daļa: Izlases nodarbību tēmas

Lekcijas tēmaUzdevumiTests
[2017-09-16] Baltic Way: Skaitļu teorija (nt-baltic-way-preparation.pptx) Dažas tēmas Baltic Way 2015.g. un 2016.g. atlases sacensībās un olimpiādē: Par pirmskaitļu izvietojumu (2 uzdevumi), par pretrunas moduli (3 uzdevumi), kombinatoriskas metodes (3 uzdevumi), kāpinātāja pacelšanas lemmas (3 uzdevumi). Apskatām teoriju un analizējam BW uzdevumus. Zemāk dotas atsauces, kam pieskārāmies lekcijā:
(1) 2015. un 2016.g. atlases sacensību uzdevumu atrisinājumi atjaunots 2017-09-15.
(2) Baltic Way uzdevumi un atrisinājumi - Art of Problem Solving forums.
(3) Lifting the Exponent (LTE) Lemma by Amir Hossein Parvardi
(4) Terry Tao, Yitang Zhang et. al. Populāra lekcija par pirmskaitļu izvietojumu (nav nepieciešams, gatavojoties BW, bet dod zināmu perspektīvu).
(5) Mining bitcoin - Kriptovalūtas iegūšana skaitļošanas centrā, Iekšējā Mongolija (skaitļu teorijas praktisks lietojums Quartz žurnālista skatījumā).
TBD TBD
(1) Dalāmības attiecība (nt-part3-01-divisibility.pptx). Veselo skaitļu dalāmība kā režģis. Dalāmības attiecība un dalīšana kā operācija. Dalīšana ar atlikumu. Pirmskaitļi, to bezgalīgais skaits un izvietojums. Aritmētikas pamatteorēma. Algebriskas identitātes, nosakot saliktus skaitļus un pirmskaitļus. Lielākais kopīgais dalītājs un mazākais kopīgais dalāmais, to sakarības. Eiklīda algoritms skaitļiem un polinomiem. Uzdevumi #1 TBD
(2) Dalāmības pazīmes (nt-part3-02-divisibility-rules.pptx). Dalāmība skaitļa decimālpierakstā. Dalāmības pazīmes ar $10^k-1$ un tā dalītājiem. Dalāmības pazīmes, kas saglabā vai nesaglabā atlikumu. Citi secinājumi no skaitļa decimālpieraksta; stāvokļu automāti, kas pārbauda dalāmību vai ģenerē skaitļus, kuri ar kaut ko dalās. Nedecimālas skaitīšanas sistēmas. Pirmskaitļu un saliktu skaitļu noteikšanas algoritmi. Uzdevumi #2 TBD
(3) Skaitļu kongruences (nt-part3-03-congruences.pptx - 49). Aritmētiskas operācijas ar atlikumiem, to īpašības. Kongruenču klases pēc $n$ moduļa. Periodiskas atlikumu virknes. Kongruenču vienādojumi. Pamatojumi ar atlikumu virkņu periodiskumu. Skaitļa pēdējais cipars (vai cipari) kā kongruenču klase. Mazā Fermā teorēma. Eilera teorēma. Interpretāciju metode Mazās Fermā teorēmas pierādījumā. Kāpināšana lielā pakāpē pēc moduļa. TBD TBD
(4) Pretrunas modulis (YYYY-MM-DD). Kongruences vienādojumu neatrisināmībā. Pretrunas moduļa izvēle. Dalāmības pazīmju izmantošana. Modulis pēc pirmskaitļa. Mainīgs modulis. Vairāku moduļu izmantošana vienam vienādojumam. Kvadrātiskas kongruences. TBD TBD
(5) Pirmskaitļa kārta (nt-part3-05-valuations.pptx - 33). Lielākā pirmskaitļa $p$ pakāpe, ar kuru dalās dotais skaitlis $n$: $\nu_p(n)$. Faktoriāli u.c. kombinatoriskas funkcijas; to dalāmība ar pirmskaitļiem. Lūkas teorēma. Kummera teorēma. Ležandra teorēma. Interpretāciju metode, pamatojot kombinatorisku funkciju dalāmību. Henzela lemma. Pakāpes pacelšanas lemmas. Fermā skaitļi un Mersena skaitļi. Viferiha pirmskaitļi (Wieferich primes). Karmaikla skaitļi (Carmichael numbers). TBD TBD
(6) ${\mathbb{Z}/m\mathbb{Z}}$ aritmētika (YYYY-MM-DD). Primitīvās saknes eksistence pēc $p$ moduļa. Saskaitīšana, atņemšana un reizināšana gredzenā $(\operatorname{mod}\,n)$, kur $n \in \mathbb{N}$. Kad eksistē inversie elementi. Lineāras kongruences un kongruenču sistēmas. Ķīniešu atlikumu teorēma. Kad atlikumu gredzens kļūst par lauku (t.i. kad var dalīt ar katru $d \neq 0$). RSA kriptosistēma un šifrēšana ar publisko atslēgu. TBD TBD
(7) Polinomi ar veseliem koeficientiem (nt-part3-07-integer-polinomials.pptx - 40). Algebras pamatteorēma. Kompleksie skaitļi un to saistītie. Polinomi ar racionāliem koeficientiem. Lagranža interpolāciju formula. Polinomu atvasināšana. Racionāli punkti polinomu grafikos. Vispārinātā Vjeta teorēma. $\mathbb{Z}[x]$ īpašības: Kad polinomiem ar veseliem (racionāliem) koeficientiem ir veselas (racionālas) saknes; polinomu dalāmība un nedalāmība reizinātājos (irreducibility); Lagranža teorēma par polinoma saknēm pēc $p$ moduļa. Racionāli punkti uz līknēm; Pitagora trijnieki. Uzdevumi (25) TBD
(8) Veselo skaitļu gredzena vispārinājumi (YYYY-MM-DD). Gredzeni, kur izpildās (neizpildās) aritmētikas pamatteorēma. Gredzeni un lauki ar kvadrātsaknēm. Skaitļu teorijas uzdevumi ar trigonometriskajām funkcijām. Konstruējamība ar cirkuli un lineālu. Algoritmi dažādu skaitļu konstruēšanai. Kvadrātsaknes un ģeometriskais vidējais. Regulāra $17$-stūra konstruēšana. Dažu konstrukciju neiespējamība. TBD TBD
(9) Veselu skaitļu funkcijas (YYYY-MM-DD). Aritmētiskas funkcijas (jeb funkcijas, kas definētas veseliem/naturāliem skaitļiem). Multiplikatīvas funkcijas. Eilera funkcija, Mēbiusa funkcija. Dalītāju skaita funkcija. Dalītāju summas funkcija. Aditīvas funkcijas. Funkcijas par pirmskaitļu dalītājiem $\Omega(n)$ un $\omega(n)$. Algoritmi aritmētisku funkciju aprēķināšanai. TBD TBD
(10) Veselā daļa un tuvināšana (nt-part3-10-floor-and-approximation.pptx - 7). Augšējā un apakšējā veselā daļa, noapaļošana. (Apakšējās) veselās daļas īpašības. Uzdevumi ar kvadrātsaknēm un veselo daļu. Veselu skaitļu virkņu "pārlēkšana" vērtībām. Fareja daļas, Šterna-Broko koki, reālu skaitļu tuvināšana ar racionāliem skaitļiem, kur saucējs ir minimāls. Racionalitātes/iracionalitātes pierādīšana. Senlaga (Sainte-Laguë) un Donta (D'Honte) noapaļošanas algoritmi. TBD TBD
(11) Nevienādības un ekstrēmais elements (YYYY-MM-DD). Atrisinājumu neesamības pamatošana ar nevienādību. Pamatojumi ar ekstrēmo elementu. Spriedumi "mazos" intervālos (piemēram, vienādojumam neeksistē atrisinājums veselos skaitļos, jo funkcija vajadzīgajai vērtībai pārlec pāri). Konstrukcijas ar ļoti lieliem skaitļiem; vajadzīgo virkņu atrašana ar Ķīniešu atlikumu teorēmu, lieliem faktoriāliem, u.c. Veselu skaitļu nevienādību pamatošana ar algebriskām metodēm. Ekstrēmā elementa izvēle; mazākais pirmskaitlis u.c. Optimizācijas uzdevumi veselos skaitļos. Nevienādību pamatošana ar atvasinājumu. TBD TBD
(12) Matemātiskā indukcija (YYYY-MM-DD). Induktīvās hipotēzes pastiprināšana. Dažādas indukcijas shēmas. Veselu skaitļu virknes vispārīgais loceklis. Bezgalīgā nokāpiena metode. Spēles ar veseliem skaitļiem; uzvarošā stratēģija kā invariants. TBD TBD

2. daļa: Ģimnāzijas matemātiķu tēmas

Tālāk izklāstītās skaitļu teorijas tēmas ir domātas pasniegšanai fakultatīvajās nodarbībās. Nodarbības attīsta kritisko domāšanu kā arī valodas prasmes, it īpaši lasot olimpiāžu uzdevumus un pierakstot pierādījumus. Šo materiālu var uzskatīt kā priekšnoteikumu izlases nodarbību tēmām (sk. augšējo tabulu). Katrā uzdevumu kopā atrodam kādu lasīšanas vingrinājumu (uzdevumu atstāsta; atbild uz jautājumiem par tā tekstu). Logaritmus (atskaitot vienkāršus spriedumus, kur vajag tikai definīciju vai meklēšanas koka dziļumu) pārceļam uz priekšpēdējo tēmu.

Lekcijas tēmaUzdevumiTests
(1) Dažas vispārīgas metodes (nt-part1-01-general-methods.pptx ). Matemātikas olimpiāžu 4 nozares (algebra, kombinatorika, ģeometrija, skaitļu teorija). Skaitļu teorija kā naturālo skaitļu aritmētika. Uzdevuma uzmanīga lasīšana; G.Poijas 4 soļi. Eksperimentēšana. Pierādāmā apgalvojuma vienkāršošana. Pilnā pārlase (exhaustive search). Pamatojumi no pretējā. Domā globāli, rīkojies lokāli (think globally, act locally). Invariantu metode. Pierādījumi ar indukciju. Uzdevumi TBD
(2) Naturālu skaitļu aritmētika (nt-part1-02-arithmetic-of-natural-numbers.pptx). Kas ir naturālie skaitļi; pamatjēdzieni un aksiomas. Citas skaitļu kopas un bijekcijas starp tām. Bezgalīgas summas - ģeometriskas progresijas u.c. Kad summa ir racionāls un kad - iracionāls skaitlis. Bezgalīgas decimāldaļas pārveidošana par racionālu skaitli. Kad un kādiem skaitļiem var izpildīt katru no aritmētiskām darbībām. Aritmētisko darbību secība. Kāpināšana veselās pakāpēs, atlikumi. (Rūpīgāk jāuzraksta par aritmētiskām un ģeometriskām progresijām. Ramanudžana bezgalīgās summas jāpārceļ tuvu beigām, kur ir virknes.) Uzdevumi TBD
(3) Skaitļu un izteiksmju struktūra (nt-part1-03-structure-of-numbers-and-expressions.pptx). Pirmskaitļi un skaitļu dalīšana pirmreizinātājos. LKD un MKD. Eiklīda algoritms. Sintakses koki. Darbību secība un asociativitāte. Neviennozīmīgas izteiksmes - arī programmēšanā un valodā. Uzdevumi TBD
(4) Decimālpieraksts un dalāmības pazīmes (nt-part1-04-rules-of-divisibility.pptx ). Kāds rezultāts var rasties, saskaitot, atņemot, reizinot, dalot $n$-ciparu skaitli ar $m$-ciparu skaitli. Spriedumi par skaitļa pēdējo ciparu. Dalāmības pazīmes ar $3$, ar $9$. Dalāmības pazīmes divnieka un piecinieka pakāpēm. Dalāmības pazīme skaitlim $11$. Uzdevumi TBD
(5) Pozicionāls skaitļa pieraksts. Kādēļ racionālie skaitļi ir periodiski. Kad tiem ir priekšperiods. Decimāli pierakstīta skaitļa izteikšana ar cipariem kā mainīgajiem burtiem. Skaitīšanas sistēmas ar bāzi $n \neq 10$. Ciparu pierakstā balstīti spriedumi, meklējot skaitļus ar noteiktām īpašībām, arī pamatojot neiespējamību. Algebriski pārveidojumi ar skaitļiem, kas izteikti ar cipariem kā mainīgajiem burtiem. TBD TBD
(6) Periodiski procesi. Kādēļ determinētiem procesiem ar galīgu stāvokļu skaitu iestājas periods. Vienvirziena un divvirzienu pārejas; kad rodas tīri periodi un kad - periodi ar priekšperiodu. Decimālpieraksta pēdējo ciparu (vai citu atlikumu) atkārtošanās, veselu skaitli reizinot vai saskaitot ar vienu un to pašu. Noteikt, kas notiks pēc daudzām darbībām, atmetot pilnos periodus. Pamatojumi, izmantojot to, ka periods nevar pārsniegt stāvokļu skaitu procesā. TBD TBD
(7) Gadījumu pārlase. Kurus uzdevumus risināt ar pilno pārlasi; sistemātiska (alfabētiska utml.) gadījumu pārlase. Skaitļi, kuru pierakstā piedalās noteikti cipari, vai arī to atkārtošanās kaut kā ierobežota (katrs cipars tieši vienu reizi, utml.). Spēja tos sistemātiski pārlasīt. TBD TBD
(8) Invarianti un spēles. Atlikums kā invariants. Atrast dalītāju, ar kuru atlikumi nemainās, ja ar skaitļiem veic noteiktus "gājienus" (piemēram, ja drīkst pieskaitīt 9 un atņemt 15, tad nemainās atlikums, dalot ar 3). Summa kā invariants. Summa nemainās, ja saskaitāmos pārgrupē (teiksim, vienreiz saskaita pa rindiņām, otrreiz - pa kolonnām). Reizinājums kā invariants. Atļautas noteiktas darbības ar skaitļiem uz tāfeles; parādīt ka var/nevar no vienas konfigurācijas iegūt citu. Permutācijas un spēle "15". TBD TBD
(9) Lineāras kongruences. Skaitļu lielākais kopīgais dalītājs. Bezū lemma. Kādos gadījumos ar $2$ (vai vairāk) skaitļiem, tos piereizinot ar koeficientiem, var izteikt visus veselos skaitļus. Eiklīda algoritms, lai risinātu lineāras kongruences. Uzdevumi, kuros lineārām kongruencēm ir papildu ierobežojumi (pozitīvi koeficienti utml.) un galīgs atrisinājumu skaits. TBD TBD
(10) Skaitļu virknes. Aritmētiskas un ģeometriskas progresijas. Rekurentas virknes. Virkņu summēšana un reizināšana. Galīgas un bezgalīgas ģeometriskas progresijas summa. Rekurentas sakarības izteikšana ar vispārīgu formulu. Polinomu vērtību 1., 2. un augstāku kārtu diferences. Virkņu īpašību pierādīšana ar indukciju. Algoritmiski procesi, $3n+1$ problēma, bezgalīgi augošas, periodiskas un fiksētas virknes. TBD TBD
(11) Veselu skaitļu funkcijas. Kāpināšana, saknes un logaritmi (logaritms ieviešams rūpīgi, jo skolā to vēl nemāca). Kāpināšana kombinatorikā - reizināšanas likums. Kvadrātsaknes aprēķināšanas "stabiņa" algoritms. Veselu skaitļu kvadrāttrinomu īpašības. Logaritms kā kodējuma garums, informācijas daudzums, koka dziļums. Veselu skaitļu funkcionālvienādojumi. TBD TBD
(12) Dirihlē princips. Dirihlē princips atlikumu kopā. Citu kombinatorisku lielumu salīdzināšana. Galīgu fragmentu salīdzināšana bezgalīgām virknēm. Kādēļ ar iracionālu $\alpha$, virknes $n\alpha$ locekļu daļveida daļas nonāk patvaļīgi tuvu jebkuram skaitlim. Kādēļ jebkuru $n$, kas dod atlikumu $1$ dalot ar $4$, var izteikt kā divu veselu skaitļu kvadrātu summu. TBD TBD

Bibliogrāfija