2014 dxdy logo

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

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


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему
 
 Сравнения произвольной степени по простому модулю
Сообщение17.12.2022, 14:53 


24/01/22
61
Есть такая теорема, что сравнение $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 
Заслуженный участник
Аватара пользователя


11/01/06
3835
Если $p|a$, то $a^p\equiv0\equiv a\pmod{p}$.

 Профиль  
                  
 
 Re: Сравнения произвольной степени по простому модулю
Сообщение17.12.2022, 18:14 
Админ форума


02/02/19
2858
 i  XeuTeP_KoLLIu, пожалуйста, оформляйте все формулы и обозначения. Не f(x), а $f(x)$. Вы же знаете, как это делается. В Карантин в этот раз не понесу, просто заметка на будущее.

 Профиль  
                  
 
 Re: Сравнения произвольной степени по простому модулю
Сообщение17.12.2022, 18:20 
Заслуженный участник
Аватара пользователя


18/01/13
12065
Казань
XeuTeP_KoLLIu
Какой "этой теоремы"? Малой Ферма? У нее есть две формулировки.

 Профиль  
                  
 
 Re: Сравнения произвольной степени по простому модулю
Сообщение17.12.2022, 18:33 


24/01/22
61
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 
Заслуженный участник
Аватара пользователя


18/01/13
12065
Казань
Имеем $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 


24/01/22
61
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 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: Skipper


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group