Найти остаток 67! , когда оно поделено на 71.
Ответы
Ответ: остаток от деления 67! на 71 равен 12
Объяснение:
Заметим что число 71 является простым.
Запишем теорему Вильсона:
Число p является простым тогда и только тогда , когда (p-1)! +1 делится на p.
В нашем случае имеем:
(71-1)!+1 делится на 71
Или: 70!=71*k-1 или 71*k+70 дает остаток (70 или -1) при делении на 71
Теперь найдем остаток от деления на 71 произведения:
68*69*70=(71-3)*(71-2)*(71-1) в этом произведении все члены кроме свободного от 71 члены помножены на 71 ,таким образом остаток от деления: (71-3)*(71-2)*(71-1) на 71 равен остатку от деления на 71 числа:-3*(-2)*(-1)=-6 (или 65)
68*69*70=71*n-6 или 71*n+65
70!=67!*68*69*70
Пусть остаток от деления 67! на 71 равен x. ( 0<=x<=70)
67!=(71*r+x)
71*k-1= (71*r+x)*(71*n-6)
То есть 6*x-1 должно делится на 71.
6x-1=71*f
Минимальное : x=12
6*12-1=72-1=71 делится на 71. (f=1)
Покажем теперь ,что других кандидатов на роль остатка нет.
Заметим ,что тк:
Наибольшее x=70.
6*70-1=419.
6x-1<=419<71*6=426
f=2;3;4;5
6*x=71*k+1
Если f-четное (f=2,4) , то 71*k четно →71*f+1 нечетно , но 6*x четно значит такое невозможно.
Если f=3 , то 71*f делится на 3, то тогда 71*f+1 не делится на 3,но 6x делится на 3. То есть такое невозможно.
f=5
6*x=71*5+1=71*6-71+1=71*6-70
71*6 делится на 6, но 70 не делится на 6, а значит 71*5+1 не делится на 6.
Вывод: остаток от деления 67! на 71 равен 12