Witam, jak wyznaczyć liczby \(\displaystyle{ p,q}\) w rozszerzonym algorytmie Euklidesa dla wielomianów?
Umiem obliczyć że \(\displaystyle{ NWD(x^{3}-1,x^{2}-1)=x-1}\) ale co z tym potem zrobić? Nie umiem tego tak przełożyć jak robi się to na liczbach..
NWD wielomianów (rozszerzony algorytm Euklidesa)
-
JakimPL
- Użytkownik
- Posty: 2401
- Rejestracja: 25 mar 2010, o 12:15
- Płeć: Mężczyzna
- Lokalizacja: Katowice
- Podziękował: 43 razy
- Pomógł: 459 razy
NWD wielomianów (rozszerzony algorytm Euklidesa)
Szukamy takich wielomianów \(\displaystyle{ p}\) i \(\displaystyle{ q}\), by zachodziła równość \(\displaystyle{ x-1=p(x^3-1)+q(x^2-1)}\). Jeżeli umiesz obliczyć \(\displaystyle{ NWD}\), z małą modyfikacją możesz wyznaczyć również wspomniane wielomiany, tworząc poniższą tabelę:
\(\displaystyle{ \begin{array}{ccc}x^3-1 & 1 & 0 \\ x^2-1 & 0 & 1\end{array}}\)
By wyznaczyć najwyższy wspólny dzielnik, dzielimy z resztą \(\displaystyle{ x^3-1}\) przez \(\displaystyle{ x^2-1}\), uzyskując iloraz \(\displaystyle{ x}\) oraz resztę \(\displaystyle{ x-1}\). Utworzymy kolejny wiersz powyższej tabeli: będzie to
\(\displaystyle{ \text{pierwszy wiersz} - \text{iloraz}\cdot\text{drugi wiersz}}\)
dzięki czemu pierwszym elementem utworzonego wektora będzie dokładnie reszta z powyższego dzielenia:
\(\displaystyle{ [x-1, 1, -x] = [x^3-1,1,0]-x \cdot[x^2-1,0,1]}\)
Powyższe operacje odejmowania wektorów odbywają się po współrzędnych. Nasza tabela jest teraz takiej postaci:
\(\displaystyle{ \begin{array}{ccc}x^3-1 & 1 & 0 \\ x^2-1 & 0 & 1 \\ x-1 & 1 & -x\end{array}}\)
Proces kontynuujemy, tj. dzielimy z resztą \(\displaystyle{ x^2-1}\) przez \(\displaystyle{ x-1}\). Jeżeli wielomian dzieli się bez reszty - a tak jest w tym przypadku - algorytm kończymy. Jak możesz się domyślać, współczynniki w drugiej i trzeciej kolumnie w ostatniej linii będą dokładnie szukanymi wielomianami \(\displaystyle{ p}\) oraz \(\displaystyle{ q}\). Tutaj \(\displaystyle{ p = 1}\), natomiast \(\displaystyle{ q=-x}\). Jak łatwo przeliczyć, możesz sprawdzić, że:
\(\displaystyle{ x-1 = (x^3-1)\cdot 1 - (x^2-1) x}\)
\(\displaystyle{ \begin{array}{ccc}x^3-1 & 1 & 0 \\ x^2-1 & 0 & 1\end{array}}\)
By wyznaczyć najwyższy wspólny dzielnik, dzielimy z resztą \(\displaystyle{ x^3-1}\) przez \(\displaystyle{ x^2-1}\), uzyskując iloraz \(\displaystyle{ x}\) oraz resztę \(\displaystyle{ x-1}\). Utworzymy kolejny wiersz powyższej tabeli: będzie to
\(\displaystyle{ \text{pierwszy wiersz} - \text{iloraz}\cdot\text{drugi wiersz}}\)
dzięki czemu pierwszym elementem utworzonego wektora będzie dokładnie reszta z powyższego dzielenia:
\(\displaystyle{ [x-1, 1, -x] = [x^3-1,1,0]-x \cdot[x^2-1,0,1]}\)
Powyższe operacje odejmowania wektorów odbywają się po współrzędnych. Nasza tabela jest teraz takiej postaci:
\(\displaystyle{ \begin{array}{ccc}x^3-1 & 1 & 0 \\ x^2-1 & 0 & 1 \\ x-1 & 1 & -x\end{array}}\)
Proces kontynuujemy, tj. dzielimy z resztą \(\displaystyle{ x^2-1}\) przez \(\displaystyle{ x-1}\). Jeżeli wielomian dzieli się bez reszty - a tak jest w tym przypadku - algorytm kończymy. Jak możesz się domyślać, współczynniki w drugiej i trzeciej kolumnie w ostatniej linii będą dokładnie szukanymi wielomianami \(\displaystyle{ p}\) oraz \(\displaystyle{ q}\). Tutaj \(\displaystyle{ p = 1}\), natomiast \(\displaystyle{ q=-x}\). Jak łatwo przeliczyć, możesz sprawdzić, że:
\(\displaystyle{ x-1 = (x^3-1)\cdot 1 - (x^2-1) x}\)