Тема . Остатки и сравнения по модулю

Китайская теорема об остатках

Вспоминай формулы по каждой теме
Решай новые задачи каждый день
Вдумчиво разбирай решения
ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!
Подтемы раздела остатки и сравнения по модулю
Решаем задачу:

Ошибка.
Попробуйте повторить позже

Задача 1#80910

Сколько четырёхзначных чисел подходит под условие x2 ≡x (mod 10000)?

Подсказки к задаче

Подсказка 1

Условие означает, что x(x-1) делится на 10000. Может ли x или x-1 делится на 10000?

Подсказка 2

Верно, не может, поскольку x — четырехзначное число. Тогда x делится на 2⁴ и x - 1 делится на 5⁴ или наоборот. Тогда в качестве x или x - 1 нужно подобрать четырехзначное число, делящееся на 625. Как это сделать?

Подсказка 3

Верно! Можно перебрать все числа, делящиеся на 625, начиная с 1250 и заканчивая 9375, попутно проверяя условие делимости одного из чисел x или x-1 на 16.

Показать ответ и решение

Нетрудно понять, что если x2− x ≡0 (mod 10000),  то x(x− 1)  должно делиться на 24  и 54.  Очевидно, что x  и x − 1  взаимно просты. Также понятно, что ни x,  ни x − 1  не могут делиться одновременно на  4
2  и  4
5 ,  потому что x  — четырёхзначное число. Поэтому возможны два случая:

1)  x  делится на  4
2  и x − 1  делится на  4
5 .

2)  x− 1  делится на 4
2  и x  делится на  4
5 .

Попробуем подобрать на место x  или x− 1  четырёхзначное число, кратное 625.  Понятно, что оно не меньше 1250  и не больше  9375.  Также оно должно быть нечётным. Из оставшихся вариантов перебором понимаем, что можно только поставить 625⋅15  на место x − 1.

Ответ:

 1

Специальные программы

Все специальные программы

Программа
лояльности v2.0

Приглашай друзей в Школково и получай вознаграждение до 10%!

Крути рулетку
и выигрывай призы!

Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.

Бесплатное онлайн-обучение

Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.

Налоговые вычеты

Узнай, как получить налоговый вычет при оплате обучения в «Школково».

Специальное предложение
для учителей

Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!

Вернём деньги за курс
за твою сотку на ЕГЭ

Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!

cyberpunkMouse
cyberpunkMouse
Рулетка
Вы можете получить скидку в рулетке!