reszty z dzielenia przez prosty wielomian Adamm: załóżmy że mamy jakiś wielomian postaci P(x)=x^k−a oraz jakiś wielomian W(x) i chcemy obliczyć resztę z W(x) przez x^k−a piszemy x^k=a i podstawiamy do jednomianów W(x) stopni wyższego lub równego k, tak dostajemy wielomian stopnia <k ten wielomian będzie naszą resztą przykład, nie jestem pewien czy to co napisałem jest zrozumiałe niech np. P(x)=x³−8 i W(x)=x¹⁰⁰+3x⁶⁷−x³+1 wtedy jeśli x³=8 to reszta=(8³³+3*8²²)x−7 inny przykład niech P(x)=x⁸−3 i W(x)=x²⁰⁰⁰⁰⁰+x¹²³⁴+x to reszta=3¹⁵⁴x²+x+3²⁵⁰⁰⁰

Adamm: to taki trick który wymyśliłem mam nadzieję że się podoba

Adamm: no i, to samo rozumowanie działa, nawet jeśli w liczbach R równość nigdy nie zajdzie przykład W(x)=x¹²³+x¹³+x³ i P(x)=x⁴+3 x⁴=−3 to reszta=[(−3)³⁰+1]x³+(−3)³x http://www.wolframalpha.com/input/?i=%5Bx%5E(123)%2Bx%5E(13)%2Bx%5E3%5D%2F%5Bx%5E4%2B3%5D

Mila: Sprawdziłam na kilku obliczonych wcześniej przykładach − działa. To z teorii liczb? Zobacz, czy dobrze zinterpretowałam

Mila: https://matematykaszkolna.pl/forum/358185.html Podobne rozwiązanie prezentował ICSP, ale mniej klarownie.

Milo: A mógłbyś to jakoś udowodnić? Tzn. wiadomo, że reszta z dzielenia W(x) przez (x−a) wynosi W(a). Więc kiedy dzielimy przez P(x) = x^k − a, to możemy podstawić x^k = t Po wykonaniu tego samego podstawienia dla W(x), gdyby akurat udało się "podstawić" wszystkie x, tzn. w otrzymanym w ten sposób wielomianie W₁(t) nie byłoby żadnego x, a jedynie zmienna t, to oczywiste byłoby, że ta reszta wynosi W₁(a). Nie rozumiem jednak do końca, dlaczego to działa także, gdy x zostanie (Z tym "niezostaniem" x chodzi mi np. o dzielenie W(x) = x²⁵ + x¹⁰ − 5x⁵ przez x⁵ − 4 po podstawieniu x⁵ = t otrzymamy W₁(t) = t⁵ + t² − 5t, czyli nie będzie żadnego x Wtedy oczywiście ta reszta wynosi W₁(4) Inaczej byłoby np. dla dzielenia tego wielomianu przez x⁴ − 4) Tzn. ja rozumiem ideę, ale męczy mnie to, że nie do końca pojmuję, jakim cudem to radzi sobie z tymi "zostaniętymi" x−ami Pomógłbyś to zrozumieć?

Adamm: tak, dobrze wpadłem na to przy tamtym zadaniu bazowałem na liczbach zespolonych

Mila: Zobacz Milo w linku który podałam. Też będę myśleć nad dowodem. Pozdrawiam

Mila: Dobranoc

Adamm: x^4k+3 − taka sama reszta przez x⁴−4 jak x^4k+3−x^4k−1(x⁴−4)=4x^4k−1 myślę że jakoś tak to działa, tak bardziej "elementarnie"

Adamm: Dobranoc

Mila: Bardzo mi się podoba ta METODA .

Milo: Jak tylko ktoś udowodni proszę dać mi znać, bo tu umrę z ciekawości Dobranoc

Adamm: to znaczy, ja mam taki pseudo−dowód niech R(x) to będzie wielomian po tym procesie (stopnia oczywiście <k) jeśli x^k−a=0 to W(x)=R(x) i teraz dla a≠0 x^k−a ma zawsze k różnych pierwiastków i dla każdego z nich W(x)=R(x) więc x^k−a dzieli W(x)−R(x) czyli W(x)−R(x)=(x^k−a)*P(x) W(x)=(x^k−a)*P(x)+R(x) − R(x) to reszta

zombi: Jutro pomyśle nad całą teorią pierścieni i ciał i wtedy pomyślimy nad dowodem wspólnie

zombi: Zasada działania jest taka, jeśli się nie mylę. Niech W(x) = xⁿ + a_n−1xⁿ⁻¹ + ... + a₁x + a₀ (zakładam, że a_n = 1 dla uproszczenia). Dzielimy przez wielomian postaci (Adamma ), czyli P(x) = x^k − a (k ≤ n). Poszukujemy wielomianu R(x), który spełnia zależność: W(x) = P(x)*Q(x) + R(x), gdzie R(x) = c_k−1x^k−1 + ... + c₁x + c₀. W celu znalezienia wielomianu R wyzerujemy wielomian P(x), czyli dla x = a^1/k(zesp. lub rzecz.), mamy zależność: W(x) = R(x). Wiedząc jaką postać ma W(x), uzyskujemy część reszty wydzielając: a₀ + a₁x + ... +a_k−1x^k−1 (bo łapią się pod postać reszty). Co robimy z pozostałą częścią od k do n? Dla każdego i ze zbioru {k, k+1, ..., n} uzyskujemy kolejne współczynniki: Jako a_i*(a^1/k)ⁱ = a_i*(a^1/k)^{(i%k)*k+i mod k}= a_i*a^i%k*x^{i mod k}, gdzie i%k to całość z dzielenia i przez k, a i mod k to reszta z tego dzielenia. Pogrubienie to natomiast przedstawienie postaci i = i%k*k + (i mod k) [i = q*k + r]. I to by się sprawdzało w twoich przykładach: P(x) = x³−8, W(x) = x¹⁰⁰+3x⁶⁷−x³+1. k=3, n=100, wtedy współczynniki przy potęgach wyższych od k−1=2 wyznaczamy: 2¹⁰⁰ = 2^3*33+1 = 8³³*2 = 8³³*x. 3*2⁶⁷ = 3*2^22*3+1 = 3*2²²*x no i ostatni x³ = 8 po prostu bo takie założenie przyjęliśmy. Coś takiego wyskrobałem.

zombi: Chociaż jak tak myślę, ten wielomian P(x) może być jakiejkolwiek postaci a_kx^k + ... a₁x+a₀.

Adamm: a rozumiesz co napisałem 01:15?

zombi: Tak

Adamm: osobiście uważam że nic nowego nie napisałeś chociaż przyznam że nie wiem o co ci chodzi z tym co napisałeś 01:06

zombi: Wobec tego to wygląda tajemniczo, ale to po prostu wyciąganie na siłe z w(x) czynników postaci całego p(x) i uzupełnianiu o ostatni wyraz rozwnięcia w następujący sposób: dajmy na to st(w) = n, st(p) = k (k<=n) i n = qk+r. Zapisujemy jedynie xⁿ = (x^k−a)^q*x^r i uzupelniamy o jedyny niezależny od x^k czynnik, czyli +a^qx^r: Czyli dla przykładu, nie osłaniając tego nie wiadomo jaką magią: w(x) = x⁴ − 7x³ + 4x² + x − 1 dzielimy przez p(x) = x³−4. w(x) = (x³−4)*x +4x −7(x³−4) + 7*4 + 4x² + x −1. Nic nowego wyglądało po prostu tajemniczo, ale to znany trik wyciągania na pałę i dopisywania. Imo wielomiany w szkole najszybciej się tak dzieliło.

zombi: −7*4 oczywiście

zombi: i oczywiście czynnik postaci −(−a)^qx^r

zombi: A ten czynnik dokładniej jeszcze idąc wynika z tego faktu (wezmę na tapetę twój przykład gdzie występuje x¹²³⁴) x¹²³⁴ = x^8*1234+2 = (x⁸−3)¹⁵⁴*x² − trzeba się pozbyć tego co nadto, czyli

	154 k
−∑		(x8)154−k(−3)kx2 tyle, że sumowane od k=1 do k=154, po prostych

przekształceniach otrzymujemy faktycznie −3¹⁵⁴*(−1)x² (druga minus jedynka wynika z własności rozwinięcia dwumianu)

zombi: po pierwszej równości ma być 8*154+2.

kot felix: jestem średni z matmy i chciałbym nauczyć się tego sposobu. mógłby ktoś rozpisać na jakimś przykładzie krok po kroku?

Milo: Dzięki zombi, pomogło mi to

Jack: No proszę, zainteresowało mnie to znajdywanie reszty.