Найти остаток 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