Остатки и делимость по модулю степеней двойки или пятёрки

Будем последовательно выбирать цифры от первого места к последнему.

На первом месте могла оказаться любая цифра, кроме На втором, третьем и четвертом местах могла оказаться любая цифра. Осталось выбрать цифру на последнее место. Для этого рассмотрим, какие могли быть остатки у суммы первых четырех выбранных цифр. Обозначим этот остаток через а последнюю цифру через

• Если то или
• Если то или
• Если то или
• Если то или
• Если то или

Заметим, что для каждого можно выбрать последнюю цифру двумя способами. Это значит, что последнюю цифру нашего числа можно выбрать двумя способами. Тогда количество чисел, сумма цифр которых делится на 5, равно

Если кратно , то чётно, то есть , откуда кратно , что равносильно делимости на . В частности, отсюда следует, что кратно , откуда , а значит . Таким образом,

откуда кратно , кратно , то есть .

В итоге . Отсюда понимаем, что при делении на число может давать остатки и . Значит, подходящие двузначные числа — и , а вероятность — .

В записи любого числа, получаемого перестановкой цифр, будут цифры и Чтобы число делилось на последняя цифра должна делиться на то есть должна быть равной либо либо При этом чтобы число делилось также и на последняя цифра должна быть четной. Поэтому подходит только цифра Но в данном в условии числе нет цифры поэтому добиться одновременной делимости и на и на нельзя.

Первое решение.

С одной стороны, это число оканчивается на цифру , то есть делится на . С другой, число дает при делении на такой же остаток, что и число, образованное последними двумя цифрами. В нашем случае число, образованное последними двумя цифрами, — это . Оно не делится на , значит, и исходное число не делится на . Итак, число делится на , но не делится на .

Заметим, что если число квадрат, то простые числа входят в него в четной степени. Значит, если квадрат делится на 5, то делится и на 25. Но перед нами число, которое делится на и не делится на . Значит, оно не квадрат.

Второе решение.

Это число даёт остаток при делении на , однако квадраты могут быть сравнимыми только с по модулю , значит, искомое число не квадрат.

Нас интересуют только однозначные, двухзначные и трехзначные числа. Давайте сделаем их всех трехзначными, дописав в начале нули. На делимость на влияют только последние цифры, поэтому на первом месте может стоять любая цифра, кроме и . Наше число делится на , поэтому третья цифра должна быть четной. Пусть на втором месте , на третьем . Для у нас есть варианты . Если или , то может быть только . Если или , то может быть равно . Итого для пары и всего вариантов и тогда для всего числа вариантов, но среди этих вариантов есть случай . Он нам не подходит, так как число должно быть натуральным.

Способ 1. Так как десятизначные числа, перемножаемые Гарри, состоят только из цифр и , то и оканчиваются они только на или . Но числа, оканчивающиеся на и , дают остаток при делении на . Значит, Гарри перемножал числа, дающие остаток при делении на . Тогда и произведение дает остаток при делении на . Поэтому после вычитания из произведения мы получим число, делящееся на . А так как результат больше 5, то быть простым и делиться на 5 он не может.

Способ 2. Заметим, что хотя бы одно число, которое перемножал, заканчивается на 6. Так как умножать мы можем в любом порядке, результат не изменится, будем умножать именно это число на остальные последовательно. Последняя цифра произведения зависит только от последних цифр сомножителей. Но оканчивается на , и также оканчивается на . Значит, произведение всегда будет оканчиваться на . Тогда после вычитания из произведения числа результат будет оканчиваться на . Но число, оканчивающееся на , делится на . И так как результат больше , то он не может быть простым.

Применим признаки делимости на и на . С одной стороны, число оканчивается на цифру , и так как она четная, то это число делится на . С другой стороны, число дает при делении на такой же остаток, как и число, образованное последними двумя цифрами. При этом дает остаток при делении на . Итак, число делится на , но не делится на , значит, квадратом оно быть не может.

Любая степень числа, оканчивающегося цифрой 1, тоже оканчивается цифрой 1. Поэтому разность оканчивается на 0 и, следовательно, не является простым числом, так как делится на 10.

Если перемножить все двузначные числа, получится число, которое делится на . Значит, оно оканчивается на два нуля. Поэтому, вычтя из него , мы получим число, оканчивающееся на . Итак, Дмитрий Алексеевич родился в году, оканчивающемся на . Это либо , либо , либо раньше. Так как Дмитрию Алексеевичу меньше ста лет, то подходит только .

Обозначим часть числа без двух последних цифр через , а предпоследнюю цифру через . Тогда исходное число можно представить в виде . Так как само число — степень двойки, и оно явно не равно , то это число делится на . Итак, делится на .

Слагаемое всегда делится на , поэтому число дает такой же остаток, что и сумма . Если делится на , то делится на , и тогда исходное число дает такой же остаток, как и число , то есть дает остаток . Но в таком случае оно не делится на , чего не может быть. Значит, не делится на , и таким образом предпоследняя цифра числа нечетная.

Посмотрим на число после переноса последней цифры в начало. Чтобы результат делился на , но не делился на , число должно оканчиваться на . Значит, до переноса последней цифры в разряде десятков стояла пятерка.

Исходное число должно было оканчиваться на четную цифру, чтобы делиться на , но при этом не на , чтобы не делиться на . Самая маленькая подходящая под эти условия цифра — двойка. И действительно, число подходит: оно делится на , но не делится на , а после переноса результат, то есть число , делится на , но не делится на .

Это действительно самое маленькое подходящее число, так как мы выяснили, что в разряде десятков должна стоять пятерка, числа и не подходят, а следующее по величине число —  — как раз является нашим ответом.

Обозначим число, получающееся из исходного вычеркиванием последней цифры, через . Исходное число делится на , значит, оканчивается на или на . Если оно оканчивается на , то его можно представить как . По условию, делится на . Но тогда и исходное число также делится на , что противоречит условию. Значит, исходное число оканчивается на .

Теперь, когда мы знаем последнюю цифру, исходное число будет тем меньше, чем меньше число, получающееся после вычеркивания последней цифры. Это число, то есть , должно делиться на . Самое маленькое число, которое делится на  — само число . Поэтому самое маленькое исходное число, подходящее под оба условия — это .

Простые числа, большие , нечетны и не делятся на . Поэтому они могут оканчиваться только на цифры , , и . Так как чисел , а возможных последних цифр только , то какие-то два числа оканчиваются на одну и ту же цифру. Тогда разность между ними оканчивается на , значит, делится на .

Предположим, что такое число существует. Тогда кратно 12, а значит, и 4. По признаку делимости на 4 кратно 4. Аналогично из того, что кратно 24, следует, что кратно 4. Значит, и делится на 4, что не так.

Делимость числа на 125 определяется тремя его последними цифрами. Следовательно, годится число .

Предположим, что и — удачные числа. В записи этих чисел не может быть цифры 0 (на 0 делить нельзя), поэтому, эти числа отличаются только последней цифрой, следовательно, одно из них оканчивается либо на 4, либо на 8. Далее можно рассуждать по-разному.

Первый способ. Пусть — произведение первых шести цифр числа . Так как соседние числа и взаимно просты и оба делятся на , то . Следовательно, каждая из первых шести цифр числа равна 1. Но число не делится на 4, а число 1111118 не делится на 8. Противоречие.

Второй способ. Среди этих четырёх чисел есть нечётные. Поскольку они делятся на произведение своих цифр, то все их цифры нечётны. Следовательно, первые шесть цифр каждого из четырёх чисел — нечётные. Но числа, оканчивающееся на или , где — нечётная цифра, не делятся на 4. Противоречие.

На что нам намекает условие этой задачи? Оканчиваться на 4 одинаковые цифры: с этим связан признак делимости на . При этом степень двойки, конечно, на 16 делится. А делится ли на 16 число, оканчивающееся на 4 одинаковые цифры? По признаку равноостаточности, можно посмотреть только на число, образованное последними 4 цифрами, пусть это . Но и 16 взаимно просты, значит, должно делиться на 16. Так как — цифра, то может быть равно только 0. Но на 0 степени двойки не заканчиваются, хотя бы потому, что степени двойки не делятся на 10.

Сумма цифр числа равна Она кратна трём, то есть наше число может быть только квадратом кратного тройке числа, но тогда оно должно быть кратно что не выполняется для суммы цифр.

Заметим, что если число квадрат, то простые числа входят в него в четной степени. Значит если квадрат делится на 5, то делится и на 25, но перед нами число, которое делится на 5 и не делится на 25. Значит оно не квадрат.

Число, которое делится на , должно оканчиваться на или на . Зеркальное число оканчиваться на не может, так как тогда оно должно и начинаться на . Итак, первая и последняя цифры — это . Вторая и третья цифра могут быть любыми — от сочетания до сочетания — всего вариантов. Так как четвертая цифра повторяет вторую, всего различных чисел будет .