2014 dxdy logo

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

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




 
 Сравнения произвольной степени по простому модулю
Сообщение17.12.2022, 14:53 
Есть такая теорема, что сравнение $f(x) \equiv 0(\mod p)$, где f(x) - многочлен с целыми коэффициентами степени n, а p простое число, эквивалентно сравнению
$R(x) \equiv 0(\mod p)$, где R(x) тоже многочлен с целыми коэффициентами но уже степени не больше p-1.
В доказательстве многочлен f(x) делится на $x^{p} - x$. Получается, что $f(x) = (x^{p} - x)Q(x) + R(x)$. А дальше говорится, что по малой теореме Ферма
$x^{p} \equiv x (\mod p)$. Но одно из условий этой теоремы - неделимость x на p. Почему это выполняется?

 
 
 
 Re: Сравнения произвольной степени по простому модулю
Сообщение17.12.2022, 17:55 
Аватара пользователя
Если $p|a$, то $a^p\equiv0\equiv a\pmod{p}$.

 
 
 
 Re: Сравнения произвольной степени по простому модулю
Сообщение17.12.2022, 18:14 
 i  XeuTeP_KoLLIu, пожалуйста, оформляйте все формулы и обозначения. Не f(x), а $f(x)$. Вы же знаете, как это делается. В Карантин в этот раз не понесу, просто заметка на будущее.

 
 
 
 Re: Сравнения произвольной степени по простому модулю
Сообщение17.12.2022, 18:20 
Аватара пользователя
XeuTeP_KoLLIu
Какой "этой теоремы"? Малой Ферма? У нее есть две формулировки.

 
 
 
 Re: Сравнения произвольной степени по простому модулю
Сообщение17.12.2022, 18:33 
provincialka в сообщении #1574193 писал(а):
XeuTeP_KoLLIu
Какой "этой теоремы"? Малой Ферма? У нее есть две формулировки.

Да, малой теоремы Ферма. Нам давали такую формулировку:
Если число $a$ не делится на простое число $p$, то $a^{p-1} \equiv 1(\mod p)$

-- 17.12.2022, 18:40 --

Это понятно, что
Цитата:
Если $p|a$, то $a^p\equiv0\equiv a\pmod{p}$

Но тогда деление $f(x)$ на $(x^{p}-x)$ ничего не даст. Нужно доказать, что $f(x) \equiv R(x)(\mod p)$

 
 
 
 Re: Сравнения произвольной степени по простому модулю
Сообщение17.12.2022, 19:05 
Аватара пользователя
Имеем $a^{p}-a=a(a^{p-1}-1)$. Либо один, либо другой множитель делится на $p$.
XeuTeP_KoLLIu в сообщении #1574196 писал(а):
Но тогда деление $f(x)$ на $(x^{p}-x)$ ничего не даст.

Почему? Первая часть равенства $f(x) = (x^{p} - x)Q(x) + R(x)$ делится на $p$ и не влияет на остаток.

 
 
 
 Re: Сравнения произвольной степени по простому модулю
Сообщение17.12.2022, 19:58 
provincialka в сообщении #1574201 писал(а):
Имеем $a^{p}-a=a(a^{p-1}-1)$. Либо один, либо другой множитель делится на $p$.
XeuTeP_KoLLIu в сообщении #1574196 писал(а):
Но тогда деление $f(x)$ на $(x^{p}-x)$ ничего не даст.

Почему? Первая часть равенства $f(x) = (x^{p} - x)Q(x) + R(x)$ делится на $p$ и не влияет на остаток.

А, точно.

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


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