Algorytm Euklidesa
Otrzymałeś(aś) rozwiązanie do zamieszczonego zadania? - podziękuj autorowi rozwiązania! Kliknij
- Jerry
- Expert
- Posty: 3534
- Rejestracja: 18 maja 2009, 09:23
- Podziękowania: 51 razy
- Otrzymane podziękowania: 1940 razy
Re: Algorytm Euklidesa
Dla liczb
\(a=6n^6+10n^5+4n^3+n,\\ b=3n^3+5n^2+2\)
gdzie \(n\in\nn_+\) mamy, z algorytmu Euklidesa i mojego poprzedniego posta,:
\[NWD(a,b)=NWD(b,n)=NWD(n,2)=\begin{cases}2&\text{jeżeli}&2\mid n\\ 1&\text{jeżeli}&2\nmid n\end{cases} \]
Pozdrawiam
\(a=6n^6+10n^5+4n^3+n,\\ b=3n^3+5n^2+2\)
gdzie \(n\in\nn_+\) mamy, z algorytmu Euklidesa i mojego poprzedniego posta,:
\[NWD(a,b)=NWD(b,n)=NWD(n,2)=\begin{cases}2&\text{jeżeli}&2\mid n\\ 1&\text{jeżeli}&2\nmid n\end{cases} \]
Pozdrawiam
-
- Fachowiec
- Posty: 1587
- Rejestracja: 01 sty 2021, 09:38
- Podziękowania: 2 razy
- Otrzymane podziękowania: 418 razy
Re: Algorytm Euklidesa
Największy wspólny dzielnik wielomianów \( f, g, \ \ NWD(f, g).\)
jest to taki niezerowy wielomian \( h \) maksymalnego stopnia, który posiada tę własność, że \( h|f, \ \ h|g.\)
\( f(n) = 6n^6 +10n^5 +4n^3+n , \ \ g(n) = 3n^3 +5n^2 + 2.\)
Algorytm Euklidesa
\( 1. \ \ f(n): g(n) \):
\( (6n^6 +10n^5 +4n^3 +n):(3n^3+5n^2+2) = 2n^3 \\ \)
\( -6n^6-10n^5-4n^3 \\ \)
----------------------------
\( \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ n \)
\( f(n) = 2n^3 \cdot g(n) + n \)
Stopień wielomianu reszty jest mniejszy od wielomianu dzielnika \( g \), ale nie równy zero.
Dzielimy dzielnik przez resztę
\( ( 3n^3 +5n^2 +2): n = 3n^2 +5n \)
\( -3n^3 \)
-----------------------
\( \ \ \ \ 5n^2 +2 \)
\( -5n^2 \)
--------------------
\( \ \ \ \ \ \ \ \ \ \ \ \ 2 \)
\( g(n) = (3n^2 +5)h(n)+2 = (3n^2 +5)n + 2 \)
Dzielimy dzielnik - wielomian \( h(n) \) przez resztę
\( h(n) : 2 = \frac{n}{2} \neq 0 . \)
Wielomiany \( f(n) = 6n^6 +10n^5 +4n^3+n, \ \ g(n) = 3n^3 +5n^2 + 2.\) są względem pierwsze \( NWD(f, g) \equiv 1.\)
jest to taki niezerowy wielomian \( h \) maksymalnego stopnia, który posiada tę własność, że \( h|f, \ \ h|g.\)
\( f(n) = 6n^6 +10n^5 +4n^3+n , \ \ g(n) = 3n^3 +5n^2 + 2.\)
Algorytm Euklidesa
\( 1. \ \ f(n): g(n) \):
\( (6n^6 +10n^5 +4n^3 +n):(3n^3+5n^2+2) = 2n^3 \\ \)
\( -6n^6-10n^5-4n^3 \\ \)
----------------------------
\( \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ n \)
\( f(n) = 2n^3 \cdot g(n) + n \)
Stopień wielomianu reszty jest mniejszy od wielomianu dzielnika \( g \), ale nie równy zero.
Dzielimy dzielnik przez resztę
\( ( 3n^3 +5n^2 +2): n = 3n^2 +5n \)
\( -3n^3 \)
-----------------------
\( \ \ \ \ 5n^2 +2 \)
\( -5n^2 \)
--------------------
\( \ \ \ \ \ \ \ \ \ \ \ \ 2 \)
\( g(n) = (3n^2 +5)h(n)+2 = (3n^2 +5)n + 2 \)
Dzielimy dzielnik - wielomian \( h(n) \) przez resztę
\( h(n) : 2 = \frac{n}{2} \neq 0 . \)
Wielomiany \( f(n) = 6n^6 +10n^5 +4n^3+n, \ \ g(n) = 3n^3 +5n^2 + 2.\) są względem pierwsze \( NWD(f, g) \equiv 1.\)