Малая теорема Ферма гласит, что для любого простого числа и натурального числа , где , справедливо равенство:
Найдем:
Заметим, что число 13 простое, причем 7<13, тогда можно применить малую теорему Ферма:
Другими словами:
, где - натуральное число
Заметим, что в биноме Ньютона все члены, кроме члена , помножены на некоторую степень числа 13, а значит данное выражение дает при делении на 13 остаток 1.
Найдем:
Число 11 простое, и 7<11, тогда рассуждая аналогично имеем:
OneGyrus
Согласна, нашла формулировку не в том источнике.
Guerrino
ну и последнее утверждение сомнительно (то есть неверно). если вы хотите перейти от системы сравнений по модулю 11 и 13 к произведению 11*13=143, то следует использовать китайскую теорему об остатках
OneGyrus
Почему же ? 7^60 -1 делится на 11 и на 13, а поскольку 11 и 13 взаимнопростые, то 7^60 -1 делится на 11*13 = 143 , а значит 7^60 дает при делении на 143 остаток 1
Guerrino
аа, так у них одинаковые остатки от деления на 11 и 13... не заметил строчки 7^60 equiv 1 mod 13
OneGyrus
Ну да, а вот если будут разные, тоже не беда, тогда остаток это ,очевидно, наименьшее общее кратное остатков.
Guerrino
это не так. взять хотя бы число 7 и рассмотреть его под модулем 5 и 6. на самом деле, если даны сравнения {x=r1 mod a, x=r2 mod b}, то решением будет x=r1*a*a^{-1}+r2*b*b^{-1}, где a^{-1} мультипликативно обратный к a по модулю r1, то есть такой, что a*a^{-1}=1 mod r1
Answers & Comments
Ответ: 1
Объяснение:
Добрый вечер!
Заметим, что
Малая теорема Ферма гласит, что для любого простого числа
и натурального числа 
, где 
, справедливо равенство:
Найдем:
Заметим, что число 13 простое, причем 7<13, тогда можно применить малую теорему Ферма:
Другими словами:
Заметим, что в биноме Ньютона
все члены, кроме члена 
, помножены на некоторую степень числа 13, а значит данное выражение дает при делении на 13 остаток 1.
Найдем:
Число 11 простое, и 7<11, тогда рассуждая аналогично имеем:
Таким образом :