Trīs teorēmas no skaitļu teorijas priekš olimpiādēm

Šī ir daļa no rakstu sērijas, kas balstās uz manu 2021. gadā uzrakstīto ZPD, kurā aplūkotas nestandarta pieejas olimpiāžu uzdevumu risināšanai. Rakstā minētos Atklātās matemātikas olimpiādes uzdevumus var atrast LU NMS arhīvā.

Kā pēdējo šajā rakstu sērijā aplūkosim kopumu ar skaitļu teorijas idejām. Šīs trīs idejas savstarpēji nav diez ko saistītas, taču katra no tām ir diezgan īsa, tāpēc aplūkosim visas uzreiz. Pēc tam, izmantosim katru teorēmu kādā olimpiādes uzdevumā, tā apgūstot, kad katra teorēma varētu būt noderīga.

Teorēmas

Divu kvadrātu teorēma

Pirmā teorēma nosaka, kad skaitli var izteikt kā divu skaitļu kvadrātu summu.

Naturālu skaitli $n$ var izteikt kā divu kvadrātu summu tad un tikai tad, ja katram skaitļa $n$ pirmreizinātājam, kura bāzes atlikums, dalot ar $3,$ ir $4,$ ir pāra kāpinātājs.

Vienkāršības labad, šajā rakstā šos pirmreizinātājus (ar bāzēm $3,7,11,15$ un tā tālāk) sauksim par īpašajiem pirmreizinātājiem. Šis ir izdomāts termins, kas olimpiādē būtu jāpaskaidro.

Piemēram, skaitli $22=2^1\cdot11^1$ nevar izteikt kā divu kvadrātu summu, jo $11^1$ ir īpašais pirmreizinātājs ar nepāra kāpinātāju. Tikmēr, $242=2^1\cdot11^2$ var izteikt kā divu kvadrātu summu, jo vienīgais īpašais pirmreizinātājs ir $11^2,$ un tā kāpinātājs ir pāra. Pie tam, šajā gadījumā summu varam uzreiz ievērot: $242=11^2+11^2.$

“Tad un tikai tad” nozīmē, ka šis darbojas arī otrādi. Piemēram, skaitļa $3^2+6^2$ īpašajiem pirmreizinātājiem visi kāpinātāji noteikti būs pāra. Un tik tiešām, $3^2+6^2=45=3^2\cdot5.$

Eilera teorēma

Otrā teorēma arī ir saistīta ar pirmskaitļiem un kāpinātājiem. Tā ir Eilera teorēma.

Ja lielākais kopīgais skaitļu $a$ un $n$ dalītājs ir $1,$ tad $a^{\phi(n)}-1$ dalās ar $n,$ kur \[\phi(n)=n(1-\frac1{p_1})(1-\frac1{p_2})\ldots(1-\frac1{p_k})\] un $p_1,p_2,\ldots,p_k$ ir visi pirmskaitļi, ar kuriem dalās $n.$

Piemēram, aplūkosim $a=2$ un $n=45=3^2\cdot5.$ Redzams, ka $LKD(2,45)=1,$ tātad varam izmantot teorēmu. Vispirms iegūstam \[\phi(45)=45(1-\frac13)(1-\frac15)=45\cdot\frac23\cdot\frac45=30\cdot\frac45=24.\] Tātad, $2^{24}-1$ dalās ar $45.$ Esam ļoti īsi pierādījuši šo sarežģīto apgalvojumu.

Ležandra formula

Visbeidzot, Ležandra formula mums nedaudz pastāstīs par skaitļa $n$ faktoriālu $n!=1\cdot2\cdot3\cdot\ldots\cdot n.$

Augstākā pirmskaitļa $p$ pakāpe, ar ko dalās $n!,$ ir \[\left\lfloor\frac{n}{p}\right\rfloor+\left\lfloor\frac{n}{p^2}\right\rfloor+\left\lfloor\frac{n}{p^3}\right\rfloor+\cdots.\]

Īpatnējās iekavas $\lfloor\,\rfloor$ apzīmē noapaļošanu uz leju. Tas nozīmē, ka šī bezgalīgā summa patiesībā ir galīga, jo uzreiz, kā $p$ pakāpes pārsniedz $n,$ visi atlikušie saskaitāmie ir vienādi ar $0.$

Piemēram, ja $p=2$ un $n=30,$ tad \begin{aligned} \left\lfloor\frac{30}{2}\right\rfloor&=\lfloor15\rfloor=15&\, \\ \left\lfloor\frac{30}{2^2}\right\rfloor&=\lfloor7.5\rfloor=7&\, \\ \left\lfloor\frac{30}{2^3}\right\rfloor&=\lfloor3.75\rfloor=3&\, \\ \left\lfloor\frac{30}{2^4}\right\rfloor&=\lfloor1.875\rfloor=1&\, \\ \left\lfloor\frac{30}{2^5}\right\rfloor&=\lfloor0.9375\rfloor=0&\, \end{aligned} un visi nākamie saskaitāmie arī būs $0.$ Summa ir $26,$ tātad $30!$ dalās ar $2^{26},$ bet ne $2^{27}.$

Piemēri no olimpiādēm

Divu kvadrātu teorēma

Atklātās matemātikas olimpiādes 2015./2016.m.g. 10. klases 3. uzdevums.
Aritmētiskās progresijas četri pēc kārtas ņemti locekļi ir veseli skaitļi $A$, $B$, $C$ un $D$. Pierādīt, ka $A^{2} +2B^{2} +3C^{2} +4D^{2}$ var izteikt kā divu veselu skaitļu kvadrātu summu!

Tā kā dota aritmētiskā progresija, ieviešam $B=A+d,C=A+2d,D=A+3d.$ Tad, \begin{aligned} &\,A^2+2B^2+3C^2+4D^2 \\ =&\,A^2+2(A+d)^2+3(A+2d)^2+4(A+3d)^2 \\ =&\,10A^2+40Ad+50d^2 \\ =&\,10(A^2+4Ad+5d^2) \\ =&\,10((A+2d)^2+d^2). \end{aligned} Pēc divu kvadrātu teorēmas, skaitļa $(A+2d)^2+d^2$ īpašajiem pirmreizinātājiem ir pāra kāpinātāji. Šo skaitli reizinot ar $10=2\cdot5,$ īpašie pirmreizinātāji nemainās, jo ne $2,$ ne $5$ atlikums, dalot ar $4,$ nav $3.$

Tātad, arī skaitlim $10((A+2d)^2+d^2)$ visiem īpašajiem pirmreizinātājiem ir pāra kāpinātāji, un divu kvadrātu teorēma nosaka, ko šo skaitli var izteikt kā divu kvadrātu summu, kas bija jāpierāda.

Šis uzdevums neprasa izteikt $A^2+2B^2+3C^2+4D^2$ kā divu kvadrātu summu, bet tikai pierādīt, ko to ir iespējams paveikt. Tas nozīmē, ka ar šo risinājumu pilnībā pietiek!

Eilera teorēma

Atklātās matemātikas olimpiādes 2017./2018.m.g. 10. klases 4. uzdevums.
Pierādīt, ka, ja $x $ ir naturāls skaitlis, tad $x^8-x^2$ dalās ar $252.$

Esmu centies izvairīties no kongruencēm šajā rakstā, taču šo risinājumu bez tām uzrakstīt ir daudz sarežģītāk. Tiem, kas nav pazīstami ar kongruencēm, iesaku aplūkot teoriju uzdevumi.lv. Kongruences ir diezgan intuitīvas, un tās ir ļoti svarīgas skaitļu teorijas uzdevumos, tāpēc ar tām vērts iepazīties tāpat.

Vispirms veicam divus novērojumus:

• Tā kā $252=2^2\cdot3^2\cdot7,$ atliek pierādīt, ka $x^8-x^2$ dalās ar $4,$ ar $7$ un ar $9.$
• Tā kā $x^8-x^2=x^2(x^6-1),$ lai pierādītu dalāmību ar $m,$ pietiek ar to, ka $x^2$ dalās ar $m$ vai $x^6-1$ dalās ar $m,$ jeb $x^2\equiv 0\pmod m$ vai $x^6\equiv 1\pmod m.$

Tad, dalāmību ar $4$ var pamatot ar tabulu:

Ja…	Tad…
$x\equiv0\pmod4$	$x^2\equiv0^2\equiv0\pmod 4$
$x\equiv1\pmod4$	$x^6\equiv1^2\equiv1\pmod 4$
$x\equiv2\pmod4$	$x^2\equiv2^2\equiv4\equiv0\pmod 4$
$x\equiv3\pmod4$	$x^6\equiv3^6\equiv(-1)^6\equiv1\pmod 4$

Dalāmībai ar $7$ apsveram divus gadījumus:

• Ja $LKD(x,7)=1,$ tad $\phi(7)=7(1-\frac1{7})=7\cdot\frac67=6$ un $x^6-1$ dalās ar $7$ pēc Eilera teorēmas.
• Ja $LKD(x,7)\neq1,$ tad $x$ dalās ar $7.$ No $\equiv 0\pmod 7$ izriet $x^2\equiv 0\pmod 7.$

Visbeidzot, arī dalāmībai ar $9$ apsveram divus gadījumus:

• Ja $LKD(x,9)=1,$ tad $\phi(9)=9(1-\frac1{3})=9\cdot\frac23=6$ un $x^6-1$ dalās ar $9$ pēc Eilera teorēmas.
• Ja $LKD(x,9)\neq1,$ tad $x$ noteikti dalās ar $3.$ Izsakot $x=3k,$ iegūstam $x^2=(3k)^2=9k^2,$ tātad $x^2\equiv0\pmod9.$

Ležandra formula

Atklātās matemātikas olimpiādes 2018./2019.m.g. 12. klases 4. uzdevums.
Sporta nometnē ir $100$ skolēni. Ar $N$ apzīmējam, cik veidos šos $100$ skolēnus var sadalīt $50$ pāros (pāru secība un arī skolēnu secība pārī nav svarīga). Ar kādu lielāko trijnieka pakāpi dalās $N?$

Skolēnus rindā var sakārtot $100!$ veidos. Tad pirmos divus skolēnus varam nodēvēt par 1. pāri, nākamos divus par 2. pāri, un tā tālāk līdz 50. pārim.

Taču, tā kā pāru secība un arī skolēnu secība pārī nav svarīga, nepieciešams koriģēt šo rezultātu, dalot ar attiecīgi $50!$ un $2^{50}.$ Iegūstam, ka $N=\dfrac{100!}{50!\cdot2^{50}}.$

Pēc Ležandra formulas, augstākā trijnieka pakāpe, ar kuru dalās $100!,$ ir \[\left\lfloor\frac{100}{3}\right\rfloor+\left\lfloor\frac{100}{9}\right\rfloor+\left\lfloor\frac{100}{27}\right\rfloor+\left\lfloor\frac{100}{81}\right\rfloor=33+11+3+1=48\] un augstākā trijnieka pakāpe, ar kuru dalās $50!,$ ir \[\left\lfloor\frac{50}{3}\right\rfloor+\left\lfloor\frac{50}{9}\right\rfloor+\left\lfloor\frac{50}{27}\right\rfloor=16+5+1=22.\]

Tātad, varam izteikt $100!$ un $50!$ attiecīgi kā $3^{48}\cdot r$ un $3^{22}\cdot s,$ kur garantēts, ka $r$ un $s$ nedalās ar $3.$ Tad, \[N=\dfrac{3^{48}\cdot r}{3^{22}\cdot s\cdot2^{50}}=3^{26}\cdot\frac{r}{s\cdot2^{50}}.\] Daļa $\dfrac{r}{s\cdot2^{50}}$ nedalās ar $3,$ tātad augstākā trijnieka pakāpe, ar ko dalās $N,$ ir $26.$

Nobeiguma domas

No šīm trim teorēmām, Eilera teorēma ir visplašāk sastopamā, jo ir iespējams izveidot grūtus uzdevumus, kur tās lietderība nav uzreiz acīmredzama. Ar divu kvadrātu teorēmu vai Ležandra formulu tas ir sarežģītāk - kā redzējām uzdevumos, tajos bija skaidri pieminēta vai nu divu kvadrātu summa, vai arī lielākā dalītāja pakāpe, kas uzreiz nodod, ka attiecīgās teorēmas varētu būt noderīgas.

Tāpēc noteikti iesaku aplūkot vairāk uzdevumus tieši par kongruencēm un Eilera teorēmu. Veiksmi skaitļu teorijas uzdevumos!