Seminár 7: Teória čísel I – úlohy o deliteľnosti

Keďže je číslo \(N\) deliteľné \(72=8\cdot 9\), musí byť súčasne deliteľné ôsmimi aj deviatimi. Z pravidla pre deliteľnosť ôsmimi vyplýva, že číslo \(\overline{79b}\) musí byť násobkom ôsmich a teda \(b=2\). Pravidlo pre deliteľnosť deviatimi diktuje, že ciferný súčet hľadaného čísla \(a+6+7+9+2=a+24\) je násobkom deviatich, dostávame tak \(a=3\). Hľadaným číslom je \(N=36792\).

Komentár

Úloha nie je náročná a je zaradená ako zahrievacie cvičenie a ukážka práce s deliteľnosťou zloženým číslom.

Prvé číslo v nekonečnom rade je číslo 6. Dokazujeme tak, že všetky výrazy tvaru \(n(n+1)(n+2)\), kde \(n\geq 2\) je prirodzené číslo, sú deliteľné šiestimi. To ale zjavne platí, keďže z troch po sebe idúcich čísel je vždy práve jedno deliteľné tromi a minimálne jedno z nich je tiež párne. Deliteľnosť dvomi a tromi zároveň nám tak zaručí deliteľnosť šiestimi a požadované tvrdenie je dokázané.

Komentár

Táto jednoduchá úloha zoznámi žiakov s poznatkom často využívaným v úlohách zameraných na dokazovanie deliteľnosti číslom, ktoré je násobkom troch: z troch po sebe idúcich prirodzených čísel je vždy práve jedno deliteľné tromi.

Každé prirodzené číslo \(n\) je tvaru \(n=3k\), \(n=3k+1\) alebo \(n=3k+2\), kde \(k\) je prirodzené číslo alebo 0. Dokazované tvrdenie overíme pre každú z týchto možností zvlášť.

a) \(n=3k\): \(n^3+2n=(3k)^3+2\cdot 3k=27k^3+6k=3k(9k^2+2)\), tvrdenie platí.

b) \(n=3k+1\): \(n^3+2n=(3k+1)^3+2(3k+1)=(27k^3+27k^2+9k+1)+(6k+2)=27k^3+27k^2+15k+3=3(9k^3+9k^2+5k+1)\), tvrdenie platí.

c) \(n=3k+2\): \(n^3+2n=(3k+2)^3+2(3k+2)=(27k^3+54k^2+36k+8)+(6k+4)=27k^3+54k^2+42k+12=3(9k^3+18k^2+14k+4)\), a preto \(3\mid n^3+2n\) aj v tomto prípade.

Iné riešenie. Môžeme sa inšpirovať predchádzajúcou úlohou a opäť využiť poznatok, že súčin troch po sebe idúcich čísel je vždy deliteľný tromi. Číslo \(n^3+2n\) môžeme napísať ako \(n^3-n+3n\). Číslo \(n^3-n\) je deliteľné tromi pre každé prirodzené \(n\), keďže ide o súčin troch po sebe idúcich čísel: \(n^3-n=n(n^2-1)=n(n-1)(n+1)\). \(3\mid 3n\) a preto aj \(3\mid n^3+2n\).

Komentár

Úloha zoznamuje študentov s ďalším možným postupom pri dokazovaní deliteľnosti výrazu daným prirodzeným číslom \(m\): rozdelenie na \(m\) možností podľa zvyšku po delení číslom \(m\) a dokázanie tvrdenia pre každú z týchto možností zvlášť. Je vhodné diskutovať so študentmi o výhodnosti tejto metódy pre (ne)veľké \(m\).

V druhom prístupe k riešeniu sme využili to, že sme číslo \(2n\) zapísali v na prvý pohľad zložitejšom tvare \(-n+2n\), čo nám však v konečnom dôsledku pomohlo úlohu elegantne vyriešiť. Táto myšlienka nájde uplatnenie aj v iných úlohách (o.ı. aj v úlohe 7.10), preto ak s ňou študenti neprídu sami, je vhodné na ňu upozorniť.

Úlohu je možné dokázať použitím matematickej indukcie, avšak tá nie je štandardnou náplňou osnov nematematických gymnázií, preto sme toto riešenie nezvolili ako vzorové. Ak sa však študenti s dôkazom použitím indukcie stretli, je vhodné s nimi rozobrať aj tento spôsob riešenia.

Výraz \(n^2-1\) upravíme na súčin \((n-1)(n+1)\). To je súčin dvoch po sebe idúcich párnych čísel, keďže \(n\) je nepárne. Preto práve jedno z čísel \(n-1\) a \(n+1\) je deliteľné 4 a druhé z nich je nepárnym násobkom čísla 2. Celkovo je teda súčin \((n-1)(n+1)\) deliteľný ôsmimi.

Komentár

Posledná úloha zo série jednoduchých dôkazov deliteľnosti využíva podobnú myšlienku ako úloha 7.2, navyše však vyžaduje upravenie výrazu \(n^2-1\) do vhodného tvaru. Následná diskusia o riešení je už jednoduchá.

a) Číslo \(n = m^6 -m^2 = m^2 (m^2-1)(m^2 +1)\) je vždy deliteľné štyrmi, pretože pri párnom \(m\) je \(m^2\) deliteľné štyrmi a pri nepárnom \(m\) sú čísla \(m^2-1\), \(m^2 +1\) obe párne, jedno z nich je dokonca deliteľné štyrmi a ich súčin je teda deliteľný ôsmimi. Z troch po sebe idúcich prirodzených čísel \(m^2-1\), \(m^2\), \(m^2 + 1\) je práve jedno deliteľné tromi, a preto je aj číslo \(n\) deliteľné tromi. Ak je \(m\) deliteľné piatimi, je \(m^2\) deliteľné piatimi, dokonca dvadsiatimi piatimi. V opačnom prípade je \(m\) tvaru \(5k + r\), kde \(r\) je rovné niektorému z čísel 1, 2, 3, 4 a \(k\) je prirodzené alebo 0. Potom \(m^2 = 25k^2 + 10kr + r^2\) a \(r^2\) sa rovná niektorému z čísel 1, 4, 9, 16. V prvom a v poslednom prípade je číslo \(m^2-1\) deliteľné piatimi, v ostatných dvoch prípadoch je číslo \(m^2 + 1\) deliteľné piatimi. Teda číslo \(n\) je vždy deliteľné nesúdeliteľnými číslami 4, 3 a 5, a teda aj ich súčinom 60.
b) Už sme ukázali, že v prípade nepárneho \(m\) je súčin \((m^2-1)(m^2 + 1)\) deliteľný ôsmimi a číslo \(n = m^6- m^2\) je teda deliteľné číslom \(120 = 8 \cdot 3 \cdot 5\). Ak je však číslo \(m\) párne, sú čísla \(m^2 -1\), \(m^2 + 1\) nepárne, žiadne nie je deliteľné dvoma. Číslo \(n\) je potom deliteľné ôsmimi iba v prípade, že \(m^2\) je deliteľné ôsmimi, teda \(m\) je deliteľné štyrmi. Číslo \(n\) je potom deliteľné šestnástimi, tromi a piatimi, a preto dokonca číslom 240.

Záver. Naše výsledky môžeme zhrnúť. Číslo \(n = m^6 - m^2\) je deliteľné číslom 120 práve vtedy, keď \(m\) je nepárne alebo deliteľné štyrmi.

Komentár

Sada dvoch na seba nadväzujúcich úloh využíva poznatky získané pri riešení jednoduchších prípravných úloh zo začiatku seminára a vyžaduje sústredené a starostlivé aplikovanie všetkých z nich.

Vzhľadom na to, že \(12 = 3 \cdot 4\), stačí ukázať, že číslo \(a = n^{k+2} - {n^k} = n^k (n^2 - 1) = (n - 1)n(n + 1)n^{k-1}\) je deliteľné tromi a štyrmi. Prvé tri činitele posledného výrazu sú tri po sebe idúce prirodzené čísla, takže práve jedno z nich je deliteľné tromi, a preto aj číslo \(a\) je deliteľné tromi. Je deliteľné aj štyrmi, lebo pri párnom \(n\) je v poslednom výraze druhý a štvrtý činiteľ párny, zatiaľ čo pri nepárnom \(n\) je párny prvý a tretí činiteľ. Tým je dôkaz hotový.

Iné riešenie*. Položme \(a = n^{k+2} - n^k = n^k (n^2 - 1) = (n - 1)n^k (n + 1)\). Opäť ukážeme, že \(a\) je deliteľné štyrmi a tromi. Ak je \(n\) párne, je \(n^k\) deliteľné štyrmi pre každé celé \(k \geq 2\). Ak je \(n\) nepárne, sú činitele \(n - 1\) a \(n + 1\) párne čísla, takže \(a\) je deliteľné štyrmi pre každé celé \(n = 2\).

Deliteľnosť tromi je zrejmá pre \(n = 3l\). Ak \(n = 3l + 1\), pričom \(l\) je celé kladné číslo, je tromi deliteľný činiteľ \(n - 1\) (a teda aj číslo \(a\)). Ak \(n = 3l + 2\) (\(l\) je celé nezáporné), je tromi deliteľný činiteľ \(n + 1\). Keďže iné možnosti pre zvyšok čísla \(n\) po delení tromi nie sú, je číslo \(a\) deliteľné tromi. Tým je požadovaný dôkaz ukončený.

Komentár

Deliteľnosť štyrmi je tiež možné dokázať aj rozborom možností \(n=4l\), \(n=4l+1\), \(n=4l+2\) a \(n=4l+3\), pre \(l\) celé a nezáporné. Kľúčovým krokom v riešení bolo vhodné rozloženie čísla \(a\) na súčin. To však súdiac podľa priemerného počtu bodov udelených za túto úlohu v krajských kolách¹ na Slovensku bola úloha pre riešiteľov neľahká.

Pre hľadané prirodzené čísla \(x\) a \(y\) sa dá podmienka zo zadania vyjadriť rovnicou \[\label{eq:58S3} (x + y) + (x - y) +\frac{x}{y}+ (x \cdot y) = 2 009,\] v ktorej sme čiastočné výsledky jednotlivých operácií dali do zátvoriek.

Vyriešme rovnicu [eq:58S3] vzhľadom na neznámu \(x\) (v ktorej je, na rozdiel od neznámej \(y\), rovnica lineárna): \[\begin{aligned} \label{eqs:58S3} 2x +\frac{x}{y}+ xy &= 2 009, \nonumber \\ 2xy + x + xy^2 &= 2 009y, \nonumber\\ x(y + 1)^2 &= 2 009y, \nonumber \\ x &= \frac{2009y}{(y + 1)^2}.\end{aligned}\] Hľadáme práve tie prirodzené čísla \(y\), pre ktoré má nájdený zlomok celočíselnú hodnotu, čo možno vyjadriť vzťahom \((y + 1)^2 \mid 2009y\). Keďže čísla \(y\) a \(y + 1\) sú nesúdeliteľné, sú nesúdeliteľné aj čísla \(y\) a \((y +1)^2\), takže musí platiť \((y +1)^2 \mid 2009 = 7^2 \cdot 41\). Keďže \(y +1\) je celé číslo väčšie ako 1 (a činitele 7, 41 sú prvočísla), poslednej podmienke vyhovuje iba hodnota \(y = 6\), ktorej po dosadení do [eqs:58S3] zodpovedá \(x = 246\). (Skúška nie je nutná, lebo rovnice [eq:58S3] a [eqs:58S3] sú v obore prirodzených čísel ekvivalentné.)

Hľadané čísla v uvažovanom poradí sú 246 a 6.

Komentár

Úloha je zaujímavá v tom, že na prvý pohľad nemusí riešiteľ tušiť, že ide o problém využívajúci poznatky z deliteľnosti. Zároveň vyžaduje netriviálnu zručnosť a nápad pri upravovaní počiatočnej rovnice do vhodného tvaru, nadväzuje tým na predchádzajúce semináre o algebraických výrazoch a rovniciach. Úloha je tak peknou ukážkou toho, že v matematike (a nielen tam) nie sú znalosti a koncepty nesúvisiace, ale často sú vzájomne prepojené.

Hľadané \(d\) sú práve tie, ktoré delia rozdiel \(U(n) - V~(n) = 13n^2 - 13 = 13(n - 1)(n + 1)\) pre každé celé \(n\). Tento rozdiel je tak určite deliteľný 13. Aby sme ukázali, že (zrejme vyhovujúce) \(d = 13\) je jediné, dosaďme do rozdielu \(U(n) - V~(n)\) hodnotu \(n = d\): číslo \(d\) je s číslami \(d - 1\) a \(d + 1\) nesúdeliteľné, takže delí súčin \(13(d - 1)(d + 1)\) jedine vtedy, keď delí činiteľ 13, teda keď \(d = 13\). Vyhovuje jedine \(d = 13\).

Komentár

Úloha stavia na myšlienke deliteľnosti rozdielu \(U(n)\) a \(V(n)\) hľadaným \(d\), čo je ďalší užitočný nástroj: namiesto upravovania výrazov \(U(n)\) a \(V(n)\) ich odčítať. Taktiež je vhodné upozorniť študentov, že druhá časť riešenia – dokázanie, že nájdené riešenie je jediné – je taktiež podstatnou súčasťou riešenia (nielen) tejto úlohy.

Upravme výraz \(V(n)\) do tvaru súčinu: \(V (n) = (n^2-1)(n^2+12)=(n-1)(n+1)(n^2+12)\). Vidíme, že \(V(n)\) je určite násobkom ôsmich v prípade nepárneho \(n\) (viď. tretia úloha tohto seminára). Keďže pre párne \(n\) je súčin \((n-1)(n+1)\) nepárny, hľadáme práve tie \(n\) tvaru \(n = 2k\), pre ktoré nie je deliteľný ôsmimi výraz \(n^2+ 12 = 4(k^2+ 3)\), čo nastane práve vtedy, keď \(k\) je párne. Hľadané \(n\) sú teda práve tie, ktoré sú deliteľné štyrmi.

Komentár

Úloha využíva vhodnú úpravu výrazu \(V\) na súčin. Tu študenti zúročia zručnosti nadobudnuté v algebraických seminároch. Zároveň využijú skôr dokázané tvrdenie o deliteľnosti ôsmimi a napokon, úloha ich pripraví na nasledujúci komplexnejší problém.

Vypočítajme najskôr hodnoty \(V (n)\) pre niekoľko najmenších prirodzených čísel \(n\) a ich rozklady na súčin prvočísel zapíšme do tabuľky:

\(n\)	\(V (n)\)
1	0
2	\(48 = 2^4 \cdot 3\)
3	\(168 = 2^3 \cdot 3 \cdot 7\)
4	\(420 = 2^2 \cdot 3 \cdot 5 \cdot 7\)

Z toho vidíme, že hľadaný deliteľ \(d\) všetkých čísel \(V (n)\) musí byť deliteľom čísla \(2^2 \cdot 3 = 12\), spĺňa teda nerovnosť \(d \leq 12\). Preto ak ukážeme, že číslo \(d = 12\) zadaniu vyhovuje, t. j. že \(V (n)\) je násobkom čísla 12 pre každé prirodzené \(n\), budeme s riešením hotoví.

Úprava \[V (n) = n^4+ 11n^2 - 12 = (12n^2 - 12) + (n^4 - n^2),\] pri ktorej sme z výrazu \(V (n)\) ”vyčlenili“ dvojčlen 1\(2n^2 -12\), ktorý je zrejmým násobkom čísla 12, redukuje našu úlohu na overenie deliteľnosti číslom 12 (teda deliteľnosti číslami 3 a 4) dvojčlena \(n^4 - n^2\) . Využijeme na to jeho rozklad \[n^4 - n^2 = n^2(n^2 - 1) = (n - 1)n^2(n + 1).\] Pre každé celé \(n\) je tak výraz \(n^4 - n^2\) určite deliteľný tromi (také je totiž jedno z troch po sebe idúcich celých čísel \(n - 1\), \(n\), \(n + 1\)) a súčasne aj deliteľný štyrmi (zaručuje to v prípade párneho \(n\) činiteľ \(n^2\), v prípade nepárneho \(n\) dva párne činitele \(n-1\) a \(n+1\)).

Dodajme, že deliteľnosť výrazu \(V (n)\) číslom 12 možno dokázať aj inými spôsobmi, napríklad môžeme využiť rozklad \(V (n) = n^4+ 11n^2 - 12 = (n^2+ 12)(n^2 - 1)\) z predchádzajúcej úlohy alebo prejsť k dvojčlenu \(n^4 + 11n^2\) a podobne.

Záver. Hľadané číslo \(d\) je rovné 12.

Komentár

Úloha je okrem využitia všetkých doterajších poznatkov zaradená aj z dôvodu prvého kroku riešenia. Je vhodné študentom ukázať, že preskúmanie výrazu pre niekoľko malých hodnôt \(n\) nám môže pomôcť utvoriť si predstavu o tom, ako sa bude výraz správať ďalej, príp. vytvoriť hypotézu, ktorú sa neskôr pokúsime dokázať. Táto metóda nájde uplatnenie nielen v tejto konkrétnej úlohe, ale aj v ďalších partiách matematiky.

Najskôr vypočítame prislúchajúce hodnoty výrazu \(V\) pre niekoľko prvých nepárnych čísel:

\(n\)	\(V (n)\)
1	0
3	\(168 = 3 \cdot 48 + 24\)
5	\(888 = 18 \cdot 48 + 24\)
7	\(2928 = 61 \cdot 48\)
9	\(7440 = 155 \cdot 48\)

Medzi hľadané zvyšky teda patria čísla 0 a 24. Ukážeme, že iné zvyšky už možné nie sú. Na to stačí dokázať, že pre každé nepárne číslo \(n\) platí \(24 \mid V~(n)\). Z školskej časti seminára vieme, že pre každé prirodzené číslo \(n\) platí \(12 \mid V~(n)\), teda aj \(3 \mid V~(n)\). Keďže čísla 3 a 8 sú nesúdeliteľné, stačí ukázať, že pre každé nepárne číslo \(n\) platí \(8 \mid V~(n)\). Využijeme pritom rozklad daného výrazu na súčin \[\label{eq:66S2} V (n) = n^4+ 11n^2 - 12 = (n^2 - 1)(n^2+ 12) = (n - 1)(n + 1)(n^2+ 12).\] Ľubovoľné nepárne prirodzené číslo \(n\) možno zapísať v tvare \(n = 2k - 1\), pričom \(k \in \NN\) . Pre také \(n\) potom dostávame \[V (2k - 1) = [(2k - 1) - 1][(2k - 1) + 1][(2k - 1)^2 + 12] = 4(k - 1)k(4k^2 - 4k + 13),\] a keďže súčin \((k - 1)k\) dvoch po sebe idúcich celých čísel je deliteľný dvoma, je celý výraz deliteľný ôsmimi.

Záver. Daný výraz môže dávať po delení číslom 48 práve len zvyšky 0 a 24.

Poznámka. Poznatok, že \(8 \mid V~(n)\) pre každé nepárne \(n\), možno dokázať aj inak, bez použitia rozkladu [eq:66S2]. Ak je totiž \(n = 2k - 1\), pričom \(k \in \NN\) , tak číslo \[n^2= (2k - 1)^2= 4k^2 - 4k + 1 = 4k(k - 1) + 1\] dáva po delení ôsmimi (vďaka tomu, že jedno z čísel \(k\), \(k - 1\) je párne) zvyšok 1, a teda rovnaký zvyšok dáva aj číslo \(n^4\) (ako druhá mocnina nepárneho čísla \(n^2\)). Platí teda \(n^2 = 8u + 1\) a \(n^4 = 8v + 1\) pre vhodné celé \(u\) a \(v\), takže hodnota výrazu \[V (2k - 1) = (8v + 1) + 11(8u + 1) - 12 = 8(v + 11u)\] je naozaj násobkom ôsmich.

Pripojme aj podobný dôkaz poznatku \(3 \mid V~(n)\) zo seminárneho stretnutia. Pre čísla \(n\) deliteľné tromi je to zrejmé, ostatné \(n\) sú tvaru \(n = 3k \pm 1\), takže číslo \[n^2= (3k \pm 1)^2= 9k^2 \pm 6k + 1 = 3k(3k \pm 2) + 1\] dáva po delení tromi zvyšok 1, rovnako tak aj číslo \(n^4 = (n^2)^2\). Dosadenie \(n^2 = 3u + 1\) a \(n^4 = 3v + 1\) do výrazu \(V (n)\) už priamo vedie k záveru, že \(3 \mid V~(n)\).

Predpokladajme, že pre dvojicu prirodzených čísel \(x, y\) platí \(50 \mid 23x + y\). Potom pre nejaké prirodzené číslo \(k\) platí \(23x + y = 50k\). Z tejto rovnosti dostaneme \(y = 50k - 23x\), čiže \(19x + 3y = 19x + 3(50k - 23x) = 150k - 50x = 50(3k - x)\), takže číslo \(19x + 3y\) je násobkom čísla 50.

Podobne to funguje aj z druhej strany. Ak pre nejakú dvojicu prirodzených čísel \(x,y\) platí \(50 \mid 19x + 3y\), tak \(19x + 3y = 50l\) pre nejaké prirodzené číslo \(l\). Z tejto rovnosti vyjadríme číslo \(y\); dostaneme \(y = (50l - 19x)/3\) (ďalší postup by bol podobný, aj keby sme vyjadrili \(x\) namiesto \(y\)). Po dosadení dostaneme \[23x + y = 23x + \frac{50l - 19x}{3}=\frac{69x + 50l - 19x}{3}=\frac{50 \cdot (x + l)}{3}.\] O výslednom zlomku vieme, že je to prirodzené číslo. Čitateľ tohto zlomku je deliteľný číslom 50. V menovateli je len číslo 3, ktoré je nesúdeliteľné s 50, preto sa číslo 50 nemá s čím z menovateľa vykrátiť a teda číslo \(23x + y\) je deliteľné 50.

Iné riešenie*. Zrejme \(3 \cdot (23x + y) - (19x + 3y) = 50x\), čiže ak 50 delí jedno z čísel \(23x + y\) a \(19x + 3y\), tak delí aj druhé z nich.