Задача 35537

Темы:    [ Малая теорема Ферма ] [ Доказательство от противного ]

Сложность: 4 Классы: 9,10

Условие

Докажите, что ни при каком целом k число  k² + k + 1  не делится на 101.

Подсказка

Рассуждайте от противного; можно воспользоваться малой теоремой Ферма.

Решение

Предположим, что для некоторого k число  k² + k + 1  делится на 101. Тогда  (k – 1)(k² + k + 1) = k³ – 1  также делится на 101, то есть  k³ ≡ 1 (mod 101).  Поэтому
k¹⁰⁰(k – 1) = k¹⁰¹ – (k³)³³k ≡ k – k = 0 (mod 101). Значит, k даёт остаток 0 или 1 при делении на 101, и  k² + k + 1  не делится на 101. Противоречие.

Источники и прецеденты использования

web-сайт

задача