Участник:Темирлан/Вероятностная проверка тождеств/Задачи/Простая задача — различия между версиями
Материал из DISCOPAL
Темирлан (обсуждение | вклад) (Новая страница: «*Вероятностная_проверка_тождеств/Задачи/Простая_задача Числа <latex>1,2, \ldots p-1</latex> взаимн…») |
StasFomin (обсуждение | вклад) (Массовая правка: замена :Проблемы в решении]] на :Уже не исправить]]) |
||
| (не показана одна промежуточная версия этого же участника) | |||
| Строка 3: | Строка 3: | ||
Числа <latex>1,2, \ldots p-1</latex> взаимно просты с <latex>p</latex>. Домножим эти числа на <latex>a</latex> и возьмем остатки по модулю <latex>p</latex>. Получим опять ту же систему остатков. Иначе: есть два разных числа: <latex>am \equiv an ~(mod~ p) \Rightarrow a(m-n) \vdots p \Rightarrow (m-n)\vdots p - </latex> противоречие. Значит, если перемножить все числа в обеих системах, получим сравнимые числа: <latex>a^{p-1}(p-1)! \equiv (p-1)!~ (mod p) \Rightarrow a^{p-1} \equiv 1 ~ (mod p)</latex>, что и требовалось | Числа <latex>1,2, \ldots p-1</latex> взаимно просты с <latex>p</latex>. Домножим эти числа на <latex>a</latex> и возьмем остатки по модулю <latex>p</latex>. Получим опять ту же систему остатков. Иначе: есть два разных числа: <latex>am \equiv an ~(mod~ p) \Rightarrow a(m-n) \vdots p \Rightarrow (m-n)\vdots p - </latex> противоречие. Значит, если перемножить все числа в обеих системах, получим сравнимые числа: <latex>a^{p-1}(p-1)! \equiv (p-1)!~ (mod p) \Rightarrow a^{p-1} \equiv 1 ~ (mod p)</latex>, что и требовалось | ||
| − | [[Категория: | + | |
| + | [[Участник:StasFomin|StasFomin]] ([[Обсуждение участника:StasFomin|обсуждение]]) 21:13, 22 марта 2017 (UTC): Сорри, это задача вообще не задача, а копипаст какой-то фигни, чисто для демонстрации кому-то как оформляются задачи. Баллы зачту, но тут решать нечего... | ||
| + | |||
| + | [[Категория:Уже не исправить]] | ||
Текущая версия на 23:50, 20 мая 2020
Числа взаимно просты с . Домножим эти числа на и возьмем остатки по модулю . Получим опять ту же систему остатков. Иначе: есть два разных числа: противоречие. Значит, если перемножить все числа в обеих системах, получим сравнимые числа: , что и требовалось
StasFomin (обсуждение) 21:13, 22 марта 2017 (UTC): Сорри, это задача вообще не задача, а копипаст какой-то фигни, чисто для демонстрации кому-то как оформляются задачи. Баллы зачту, но тут решать нечего...