wielomiany jednej zmiennej
MalWas:
Udowodnić że wielomian (x+1)n + xn + 1 jest podzielny przez x2+x+1 wtedy i tylko wtedy gdy
2 (dzieli) n i 3 (nie dzieli) n.
17 mar 15:09
jc: Niech = oznacza przystawanie modulo 1+x+x2
P=(x+1)n+xn+1
x2=−1−x
x3=−x−x2=1
(1+x)2=x4=x
Rozpatrujemy przypadki.
n=6k, P=x3k+x6k+1=3
n=6k+1, P=(x+1)x3k+x6k+1+1=(x+1) +x+1
n=6k+2, P=x3k+1+x6k+2+1=x+x2+1=0
n=6k+3, ... tu nie mamy zera
n=6k+4 , ... jeszcze to mamy zero
n=6k+5, ... tu nie mamy zera
Inny sposób: podstaw pierwiastki zespolone 1+x+x2.
17 mar 16:14
Adamm:
(x−1)(x2+x+1) = x3−1
(x+1)n+xn+1 ≡ (−1)nx2n+xn+1 ≡ (−1)nx2n mod 3+xn mod 3+1 (mod x2+x+1)
jeśli 3|n, to stopień (−1)nx2n mod 3+xn mod 3+1 = (−1)n+2 jest < 2, więc
jest (niezerową) resztą z dzielenia przez x2+x+1.
Załóżmy więc, że n nie jest podzielne przez 3. Zatem {n mod 3, 2n mod 3} = {1, 2}.
Wtedy (−1)nx2n mod 3+xn mod 3+1∊{(−1)nx2+x+1, x2+(−1)nx+1}.
W każdym razie, żeby to było podzielne przez x2+x+1, warunkiem koniecznym
i wystarczającym, jest by 2|n.
17 mar 23:12