Zadanie

Krtko mu celý natešený ukáže kruh, ktorý vystrihol. Avšak František ho počastuje: „Veď z toho ja šaty spraviť neviem!“ A hneď začne Krtkovi vysvetľovať, že kružnica musí mať vhodné parametre: \[x^2 = 12n + 5.\] Načo sa hneď Krtko zarazí, že veď taká kružnica neexistuje. Ukážte, že mal Krtko pravdu a pre \(x, n \in \mathbb{N}\) nemá rovnica žiadne riešenie.

Chceme zistiť, či existuje také \(x\), že \(x^2\) dáva po delení dvanástimi zvyšok \(5\). Matematicky1 to vieme zapísať aj ako \(x^2\equiv5\pmod{12}\).

Nech \(x=12r+s\). Potom \(x^2=(12r+s)^2=144r^2+24rs+s^2\). Všimnime si, že prvé dva členy sú deliteľné dvanástkou, a preto zvyšok mocniny závisí iba od zvyšku umocňovaného čísla. Inými slovami \(x^2\equiv s^2\pmod{12}\).

Výraz \(s^2\) pre \(s\in\{0,1,2,\dots, 11\}\) má zvyšky \(0,1,4,9,4,1,0,1,4,9,4,1\), a teda skutočne neobsahuje \(5\).

Čo ak by sme však mali ukázať, že rovnica \(x^2=1287n+5\) nemá žiadne riešenie pre \(x,n\in\mathbb N\)? Potom by vypisovanie všetkých možností zvyškov modulo 1287 neprichádzalo v úvahu. Pozerať sa na zvyšky sa nám ale zjavne oplatilo, skúsme to teda znova, ale s menším modulom – a to nejakým malým deliteľom toho pôvodného.

Iné riešenie

Pozrime sa teda zvlášť na deliteľnosť \(3\) a \(4\). Pravá strana dáva po delení štyrmi zvyšok \(1\). Ľavá strana \(x^2\) dáva pre zvyšky \(0,1,2,3\) čísla \(x\) postupne zvyšky \(0,1,0,1\). Zatiaľ žiaden spor nevidíme. Avšak po delení tromi dáva pravá strana zvyšok \(2\), kdežto tá ľavá pre zvyškové triedy \(0,1,2\) dáva postupne zvyšky \(0,1,1\). Ak sa ale obe strany majú rovnať, musia sa rovnať aj ich zvyšky, čo je spor. Môžete si premyslieť, že zvyškami po delení trojkou by sa dal odargumentovať aj variant úlohy s číslom \(1287\).

Riešenie pre fajnšmekrov

Zadanie je ekvivalentné s tvrdením, že \(5\) je kvadratickým zvyškom modulo \(12\) Vytiahneme preto teóriu kvadratickej reciprocity.2

Keďže \(12 = 2^2\cdot 3\) a číslo \(5\) je nesúdeliteľné s oboma činiteľmi, podľa čínskej zvyškovej vety stačí overiť, či \(5\) je kvadratickým zvyškom po delení \(4\) a \(3\).

Teda treba zistiť, čomu sú rovné \(\left(\dfrac{5}{4}\right)\) a \(\left(\dfrac{5}{3}\right)\), kde \(\left(\dfrac{a}{b}\right)\) je Jacobiho symbol3.

Síce prvý výraz je zrejme \(\left(\dfrac{5}{4}\right)=1\), pretože \(5^2 = 25 \equiv 5 \equiv 1 \pmod{4}\), ale druhý výraz \(\left(\dfrac{5}{3}\right)= \left(\dfrac{2}{3}\right) = -1\), pretože \((3x+1)^2 = 9x^2+6x+1 \equiv 1 \pmod{3}\) a \((3x+2)^2 = 9x^2+12x+4 \equiv 1 \pmod{3}\).

Ak by nám náhodou toto prišlo stále veľmi jednoduché, mohli by sme použiť Eulerovo kritérium, na základe ktorého \(\left(\dfrac{2}{3}\right)\equiv2^{\frac{3-1}2}\equiv-1\).

Preto také čísla \(x\) a \(n\) neexistujú.

  1. Takýto typ zápisu nazývame kongruencia.↩

  2. http://thales.doa.fmph.uniba.sk/sleziak/vyuka/tc2006/tc.pdf, kapitola 4.↩

  3. Jacobiho symbol nadobúda hodnotu \(-1\), keď \(a\) nie je kvadratickým zvyškom modulo \(b\), \(1\) ak je a \(0\) ak \(b\mid a\).↩

Diskusia

Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.

Pre pridávanie komentárov sa musíš prihlásiť.