Выбор модуля для доказательства делимости / простоты / степени
Ошибка.
Попробуйте повторить позже
Миша выписал все остатки от деления некоторого числа 
на 
. При этом оказались выписаны в каком-то порядке все
числа от 
до 
. Докажите, что число 
составное.
Подсказка 1
Введите переменные, обозначающие остатки от деления N на 120 и 160. Это два числа, у которых общий множитель 40 — поэтому остатки должны быть одинаковы и при делении на 40. Какими числами они могут быть из остатков из условия?
Подсказка 2
Да, это 43 и 83 в каком-то порядке. А что мы можем сказать об остатке при делении N на 140? 120, 140, 160… Что между ними общего?
Подсказка 3
Конечно, 120, 140, 160 делятся на 20. Надо, чтобы остаток по делении на 120 отличался от 43 и 83 только на 20k, где k - целое число. Такой только 63. Отлично, получилось, что N = 140k + 63. Составное ли это число?
Рассмотрим остатки при делении на 
. Заметим, что они сами должны давать одинаковый остаток при делении 
,
поскольку
То есть числа 
дают тот же остаток при делении на 
, что и само число 
. Отсюда делаем вывод, что это обязательно числа 
и 
в каком-то порядке (все остальные остатки при делении на 
встречаются в единственном экземпляре). Теперь рассмотрим остаток
при делении на 
. Заметим, что
из доказанного выше. В каждом из случаев первое слагаемое кратно 
, как и 
, то есть числа 
и 
(или, что
то же самое, 
) дают один и тот же остаток при делении на 
. Получили, что 
даёт остаток 
при делении на
.
Отсюда 
, то есть остаток 
при делении на 
может быть равен только 
(другие остатки, дающие 
при
делении на 
, уже закончились). Итак, 
и кратно 
. Поскольку оно, очевидно, больше 
, то является
составным.
Замечание. Про заключительную делимость 
можно было догадаться, если придумать несложный пример 
, откуда
становится понятно, что мы хотим думать именно про 
.
что и требовалось доказать
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
