2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Остаток от деления двух многочленов
Сообщение20.07.2014, 10:47 
Аватара пользователя
Здравствуйте, уважаемые друзья!

Пусть $n>1$ и $n\mid p-1$, где $p$ - простое число. Доказать, что остаток от деления $x^p-x$ на $x^n-A$ есть $x(A^{\frac{p-1}{n}}-1)$

Попытка доказательства: Напишем это в таком виде $$x^p-x=x(x^{p-1}-1)=x(x^{p-1}-A^{\frac{p-1}{n}}+A^{\frac{p-1}{n}}-1)=x(x^{p-1}-A^{\frac{p-1}{n}})+x(A^{\frac{p-1}{n}}-1)$$так как $n\mid p-1$ и $n>1$, то $p-1=ns$ и первую скобку можно написать так: $$x^{p-1}-A^{\frac{p-1}{n}}=x^{ns}-A^{s}=(x^n-A)(x^{n(s-1)}+\dots+A^{s-1})$$ и отсюда понятно, что $x^{p-1}-A^{\frac{p-1}{n}}\equiv 0 \pmod {x^n-A}$ Итого получаем, что $$x^p-x\equiv x(A^{\frac{p-1}{n}}-1) \pmod{x^n-A}$$ Т.е. остаток от деления $x^p-x$ на $x^n-A$ есть $x(A^{\frac{p-1}{n}}-1) $ (условие $n>1$ играет существенную роль).

Скажите пожалуйста, является ли мое доказательство верным?
П.С. проверил при некоторых значениях и это действительно верно.

С уважением, Whitaker.

 
 
 
 Re: Остаток от деления двух многочленов
Сообщение20.07.2014, 11:34 
Whitaker в сообщении #888885 писал(а):
Итого получаем, что $$x^p-x\equiv x(A^{\frac{p-1}{n}}-1) \pmod{x^n-A}$$ Т.е. остаток от деления $x^p-x$ на $x^n-A$ есть $x(A^{\frac{p-1}{n}}-1) $
Полученное сравнение верно, а вывод - нет. Из того, что $8\equiv 5\pmod 3$ не следует, что $5$ - остаток от деления $8$ на $3$.
Если $a\equiv r\pmod m$ и $0\leqslant r<m$, то тогда $r$ - остаток от деления $a$ на $m$.

Или Вы имеете ввиду остаток - в смысле кольца многочленов? Если так, то верно и доказывается технически проще: $x^{p-1}\equiv (x^n)^{\frac{p-1}{n}}\equiv A^{\frac{p-1}{n}}$

 
 
 
 Re: Остаток от деления двух многочленов
Сообщение20.07.2014, 11:41 
Аватара пользователя
Sonic86
Да я с Вами согласен. Когда мы делим многочлен $f(x)$ на многочлен $g(x)$ мы получаем: $f(x)=g(x)h(x)+r(x)$, где $\text{deg}r(x)<\text{deg}f(x)$
В нашем случае $f(x)=x^n-A$ и степень нашего остатка меньше чем $n$.

-- Вс июл 20, 2014 11:51:56 --

Если $f(x)\equiv r(x) \pmod{g(x)}$ и $\text{deg}r(x)<\text{deg}g(x)$ тогда $r(x)$ будет остатком. Вы согласны с этим?

 
 
 
 Re: Остаток от деления двух многочленов
Сообщение20.07.2014, 12:03 
Whitaker в сообщении #888896 писал(а):
Если $f(x)\equiv r(x) \pmod{g(x)}$ и $\text{deg}r(x)<\text{deg}g(x)$ тогда $r(x)$ будет остатком. Вы согласны с этим?
Да.
Это меня просто чего-то переклинило на константы.

 
 
 
 Re: Остаток от деления двух многочленов
Сообщение20.07.2014, 12:05 
Аватара пользователя
Sonic86
Ну вот у меня точно такие же рассуждения и тут.
Спасибо Вам за помощь! :D

 
 
 [ Сообщений: 5 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group