10. príklad - Vzorové riešenie

Kľúčová myšlienka v tomto príklade bola pozrieť sa na prvočíselné rozklady čísel a, b, c. Nech p_1, p_2, \dots, p_k sú všetky (rôzne) prvočísla, ktoré sú v prvočíselnom rozklade aspoň jedného z a, b. Teraz vieme čísla a, b jednoznačne zapísať ako prvočíselný rozklad:

​a=p_1^{a_1}p_2^{a_2}\dots p_k^{a_k} a b=p_1^{b_1}p_2^{b_2}\dots p_k^{b_k},

kde a_1,\dots , a_k, b_1, \dots, b_k sú nezáporné celé čísla.

Každé vyhovujúce c sa bude tiež skladať len z týchto prvočísel. Ak by obsahovalo aj nejaké iné prvočíslo p, nemohlo by platiť, že c|ab​ (c delí ab), pretože potom by p muselo deliť aj ab a to vieme, že nedelí. Teda hľadáme c tiež v tvare c=p_1^{c_1}p_2^{c_2}\dots p_k^{c_k}, kde c_1,\dots,c_k sú opäť nezáporné celé čísla.

Podmienky zo zadania sa dajú vyjadriť aj tak, že \frac{ab}{c}, \frac{ac}{b}, \frac{bc}{a}majú všetky byť všetky celé čísla. Keď to prepíšeme pomocou našich prvočíselných rozkladov dostaneme:

​p_1^{a_1+b_1-c_1}p_2^{a_2+b_2-c_2}\dots p_k^{a_k+b_k-c_k},

​p_1^{a_1+c_1-b_1}p_2^{a_2+c_2-b_2}\dots p_k^{a_k+c_k-b_k},

​p_1^{b_1+c_1-a_1}p_2^{b_2+c_2-a_2}\dots p_k^{b_k+c_k-a_k}.

Tieto čísla budú celé práve vtedy, ak každý exponent bude nezáporný. Z toho vyplýva, že c bude vyhovujúce práve vtedy, ak platia nasledujúce nerovnosti:

a_i+b_i \ge c_i,

​a_i+c_i \ge b_i,

​b_i+c_i \ge a_i.

pre každé 1 \le i \le k.

Pre konkrétne i môžeme bez újmy na všeobecnosti predpokladať, že a_i \le b_i. Z prvých dvoch nerovníc dostávame a_i + b_i \ge c_i \ge b_i-a_i. Ľahko sa dá vidieť, že každé c_i z tohto intervalu bude spĺňať aj tretiu nerovnosť.

Keďže b_i \ge a_i tak c_i \ge b_i - a_i \ge 0. To znamená, že b_i+c_i \ge b_i \ge a_i. Takže možnosti pre c_i sú všetky celé čísla od b_i-a_i do a_i+b_i. To je (a_i+b_i)-(b_i-a_i)+1=2a_i+1 možností, čo je nepárne číslo.

Takže vidíme, že máme nepárny počet možností pre každý exponent. Keďže každý exponent môžeme vybrať úplne nezávisle, celkový počet možností bude iba súčin počtov možností pre každý z nich. No a súčin nepárnych čísel je vždy nepárny.​

Iné riešenie

Nech d je najväčší spoločný deliteľ a, b. Potom vieme nájsť nesúdeliteľné celé čísla f,g také, že a=df a b=dg. Podľa zadania má platiť:

1. a|bc, teda df|dgc čo je ekvivalentné s f|gc. Keďže f,g sú nesúdeliteľné, znamená to, že f|c.
2. ​b|ac, teda dg|dfc. Podobným spôsobom dostaneme g|c.
3. c|ab, teda c|d^2fg.

Keďže f,g sú nesúdeliteľné, 1. a 2. nám dokopy dávajú fg|c. To môžeme zapísať ako c=kfg a dosadiť do 3.:

​kfg|d^2fg,​

​k|d^2.

Môžeme vidieť, že všetky takéto c spĺňajú všetky podmienky:

1. a|bc \iff df|dg\cdot kfg \iff 1|kg^2 platí.
2. ​b|ac \iff dg|df\cdot kfg \iff 1|kf^2 platí.
3. c|ab \iff kfg|d^2fg \iff k|d^2 platí.

Teda nám stačí nájsť počet možností pre k, čo je iba počet deliteľov d^2. Konkrétne teda ukázať, že tento počet je nepárny.

Toto sa dá ukázať viacerými spôsobmi. Vieme napríklad ukázať, že máme rovnako veľa deliteľov menších ako d a väčších ako d. Ku každému deliteľu t\lt d môžeme priradiť deliteľ \frac{d^2}{t}\gt d. Týmto pokryjeme všetky delitele väčšie ako d, pretože každý z nich sa dá zapísať ako \frac{d^2}{t} pre nejaké t\lt d. Takže máme niekoľko deliteľov menších ako d a rovnako veľa väčších ako d. To nám dokopy dáva párny počet, ale ešte sme nazapočítali d, ktorý je tiež deliteľ. Spolu s ním máme nepárne veľa deliteľov.

Týmto sme ukázali, že máme nepárny počet možností pre c.​​