Найдите остаток при делений 95! на 97 с обьяснением
Answers & Comments
daniilzhulanov
Привет! Для решения этой задачи мы можем использовать малую теорему Ферма, которая гласит: если p - простое число, а a не кратно p, то a^(p-1) ≡ 1 (mod p).
В нашем случае, p = 97, и поскольку 97 - простое число, то мы можем применить малую теорему Ферма для нахождения остатка при делении 95! на 97.
95! содержит множитель 97, то есть 97 является множителем числителя. Но 97 - простое число, поэтому мы можем разбить 95! на множители, пропуская число 97, и разделить на 97:
daniilzhulanov
Честно, не знаю. Возможно, не проходят в школьной программе вообще, так как эта задачка походит на слабенькую олимпиадную
antonovm
95! содержит множитель 97 ? ; 95! = 1 × 2 × 3 × ... × 96 × 97 - ? Очень странные вещи вы пишете , число 97 не является делителем 95! , так как 95! = 1 × 2 × 3 × ... × 95 и простое число 97 не может быть делителем ни одного из сомножителей 95!
Answers & Comments
Для решения этой задачи мы можем использовать малую теорему Ферма, которая гласит: если p - простое число, а a не кратно p, то a^(p-1) ≡ 1 (mod p).
В нашем случае, p = 97, и поскольку 97 - простое число, то мы можем применить малую теорему Ферма для нахождения остатка при делении 95! на 97.
95! содержит множитель 97, то есть 97 является множителем числителя. Но 97 - простое число, поэтому мы можем разбить 95! на множители, пропуская число 97, и разделить на 97:
95! = 1 × 2 × 3 × ... × 96 × 97
= (1 × 2 × 3 × ... × 96) × 97
≡ (-1)^48 × 97 (mod 97) (по малой теореме Ферма)
≡ 1 (mod 97)
Таким образом, остаток при делении 95! на 97 равен 1.