Opravovatelia

M&M; [email protected]

Lukáš [email protected]

Chceme zistiť, či existuje také $x$, že $x^2$ dáva po delení dvanástimi zvyšok $5$. Matematicky¹ 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.²

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 symbol³.

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ú.