N.s.d. pre $f(x)=x^7-1$ a $g(x)=x^5-1$

[Martin Sleziak]

Nájdite normovaný najväčší spoločný deliteľ $d(x)$ daných polynómov $f(x)$, $g(x)$ a nájdite $u(x)$, $v(x)$ také, že $d(x)=u(x)f(x)+v(x)g(x)$.
\begin{align*}
f(x)&=x^7-1\\
g(x)&=x^5-1
\end{align*}

Najväčší spoločný deliteľ je $d(x)=x-1$.

Polynómy $u(x)$, $v(x)$ nie sú určené jednoznačne; jedno z možných riešení je $u(x)=-x^3-x$ a $v(x)=x^5+x^3+1$, t.j.
$$x-1=-(x^3+x)(x^7-1)+(x^5+x^3+1)(x^5-1).$$

Spomeniem aj to, že všeobecne platí $\gcd(x^m-1,x^n-1)=x^{\gcd(m,n)}-1$. (Môžete sa nad tým zamyslieť - samozrejme, je to o čosi náročnejšie než zistiť takéto niečo pre konkrétne polynómy, ako to bolo v tejto úlohe.)

Výpočty sa dali robiť napríklad so zadanými polynómami:
$$\begin{array}{|c|c|c|}
\hline
f(x) & g(x) & \\\hline
1 & 0 & x^7-1\\\hline
0 & 1 & x^5-1\\\hline
1 &-x^2 & x^2-1\\\hline
-x^3-x &x^5+x^3+1 & x-1\\\hline
\end{array}$$

Alebo sme si mohli všimnúť, že oba polynómy sú deliteľné $x-1$ a pracovať s polynómami nižšieho stupňa.
\begin{align*}
x^7-1&=(x-1)(x^6+x^5+x^4+x^3+x^2+x+1)\\
x^5+-1&=(x-1)(x^4+x^3+x^2+x+1)
\end{align*}
Ak si označíme $f_1(x)=x^6+x^5+x^4+x^3+x^2+x+1$ a $g_1(x)=x^4+x^3+x^2+x+1$, tak vieme zistiť ich n.s.d a vyjadriť ho pomocou týchto polynómov.
$$\begin{array}{|c|c|c|}
\hline
f_1(x) & g_1(x) & \\\hline
1 & 0 & x^6+x^5+x^4+x^3+x^2+x+1 \\\hline
0 & 1 & x^4+x^3+x^2+x+1 \\\hline
1 &-x^2 & x+1 \\\hline
-x^3-x &x^5+x^3+1 & 1 \\\hline
\end{array}$$

Týmto sme dostali:
\begin{align*}
1&=-(x^3+x)f_1(x)+(x^5+x^3+1)g_1(x)\\
x-1&=-(x^3+x)(x-1)f_1(x)+(x^5+x^3+1)(x-1)g_1(x)\\
x-1&=-(x^3+x)f(x)+(x^5+x^3+1)g(x)
\end{align*}

[Martin Sleziak]

Ešte napíšem trochu iný prístup ako sa táto dá vyriešiť - je špecifický pre tieto konkrétne polynómy, resp. pre polynómy podobného tvaru.

Najprv sa pozrime na n.s.d exponentov.
$$\begin{array}{|c|c|c|}
\hline
7 & 5 & \\\hline
1 & 0 & 7 \\\hline
0 & 1 & 5 \\\hline
1 &-1 & 2 \\\hline
-2 & 3 & 1 \\\hline
\end{array}$$
Zistili sme, že $$3\cdot5-2\cdot7=1.$$

Všimnime si, že z~polynómu $x^4+x^3+x^2+x+1$, ktorý obsahuje 5 po sebe nasledujúcich mocnín, viem vhodným vynásobením vyrobiť polynóm, ktorý ich obsahuje 10, 15, 20, ...
\begin{align*}
(x^5+1)(x^4+x^3+x^2+x+1)&=x^9+x^8+x^7+x^6+x^5+x^4+x^3+x^2+x+1\\
(x^{10}+x^5+1)(x^4+x^3+x^2+x+1)&=x^{14}+x^{13}+x^{12}+x^{11}+x^{10}+x^9+x^8+x^7+x^6+x^5+x^4+x^3+x^2+x+1\\
(x^{15}+x^{10}+x^5+1)(x^4+x^3+x^2+x+1)&=x^{19}+x^{18}+x^{17}+x^{16}+x^{15}+x^{14}+x^{13}+x^{12}+x^{11}+x^{10}+x^9+x^8+x^7+x^6+x^5+x^4+x^3+x^2+x+1
\end{align*}
Podobne to funguje aj pre polynóm $x^6+x^5+x^4+x^3+x^2+x+1$.

Čiže takto viem dostať násobky týchto polynómov, ktoré sa priveľmi nelíšia:
\begin{align*}
(x^7+1)(x^6+x^5+x^4+x^3+x^2+x+1)&=x^{13}+x^{12}+x^{11}+x^{10}+x^9+x^8+x^7+x^6+x^5+x^4+x^3+x^2+x+1\\
(x^{10}+x^5+1)(x^4+x^3+x^2+x+1)&=x^{14}+x^{13}+x^{12}+x^{11}+x^{10}+x^9+x^8+x^7+x^6+x^5+x^4+x^3+x^2+x+1
\end{align*}
resp.
\begin{align*}
(x^8+x)(x^6+x^5+x^4+x^3+x^2+x+1)&=x^{14}+x^{13}+x^{12}+x^{11}+x^{10}+x^9+x^8+x^7+x^6+x^5+x^4+x^3+x^2+x\\
(x^{10}+x^5+1)(x^4+x^3+x^2+x+1)&=x^{14}+x^{13}+x^{12}+x^{11}+x^{10}+x^9+x^8+x^7+x^6+x^5+x^4+x^3+x^2+x+1
\end{align*}

Keď predošlé dve rovnosti od seba odčítam, tak vidím, že platí:
\begin{align*}
1&=-(x^8+x)f_1(x)+(x^{10}+x^5+1)g_1(x)\\
x-1&=-(x^8+x)f(x)+(x^{10}+x^5+1)g(x)
\end{align*}

*****

Resp. veľmi podobné úvahy by som vedel robiť aj polynómami $f(x)$ a $g(x)$.
Tu mám:
\begin{align*}
(x^5+1)(x^5-1)&=x^{10}-1\\
(x^{10}+x^5+1)(x^5-1)&=x^{15}-1\\
(x^{15}+x^{10}+x^5+1)(x^5-1)&=x^{20}-1
\end{align*}
Takže si viem všimnúť rovnosti:
\begin{align*}
(x^7+1)(x^7-1)&=x^{14}-1\\
(x^8+x)(x^7-1)&=x^{15}-x\\
(x^{10}+x^5+1)(x^5-1)&=x^{15}-1
\end{align*}
a z nich opäť viem vyjadriť
$$x-1=-(x^8+x)(x^7-1)+(x^{10}+x^5+1)(x^5-1).$$