02 Делимость

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

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

Возьмем произвольное трехзначное число, записанное одинаковыми цифрами, например Это число можно представить в виде:

где - цифра от до Разложим на множители:

Следовательно,

Так как является множителем, то делится на без остатка. Таким образом, всякое трехзначное число, записанное одинаковыми цифрами, делится нацело на , что и требовалось доказать.

Последняя цифра произведения определяется произведением последних цифр множителей. Рассмотрим произведение последних цифр:

Так как в этом произведении присутствует множитель и четное число то произведение оканчивается на . Действительно, , и любое произведение, содержащее множитель , оканчивается на . Поэтому, оканчивается на .

Следовательно, и исходное произведение также оканчивается на .

Пусть номер билета имеет вид По условию, кратно значит заканчивается на Так как номер билета начинается с и заканчивается на то может быть или Значит, возможны следующие варианты для :

• Если , то номер билета должно быть кратно , значит может принимать значения: Также, должно быть кратно , то есть кратно Значит, может быть равно Из возможных значений для подходят:

  

  То есть, получаем числа

• Если то номер билета должно быть кратно значит может принимать значения:

  Также, должно быть кратно то есть кратно

  Значит, может быть равно Из возможных значений для подходят:

  

  То есть, получаем числа

• Если , то номер билета . Так как билет заканчивается на номере проверяем это число. должно быть кратно .

  кратно Также, должно быть кратно Значит подходит.

Всего получается "счастливых"билетов.

Если делится на то существует целое число такое, что Если делится на то существует целое число такое, что

Подставим второе уравнение в первое:

Если , то можно разделить обе части на

Так как и - целые числа, то это возможно только в двух случаях:

и В этом случае

и В этом случае

Если то так как делится на то

Таким образом, делится на и делится на тогда и только тогда, когда или

Нужно получить число, которое кратно числам и Мы обязаны вычеркнуть цифру иначе результат будет нечётным и, значит, не кратным Мы обязаны также вычеркнуть иначе результат будет оканчиваться на или на и тоже не кратен Получилось число Его сумма цифр не кратна значит, и число не кратно и надо вычеркнуть ещё хотя бы одну цифру. После вычёркивания сумма цифр станет меньше но она должна быть кратна то есть равна или Во всех случаях нам надо уменьшить сумму как минимум на то есть вычеркнуть из не менее двух цифр. Итак, вычеркнуть менее цифр нельзя. А ровно можно: оставим число Оно кратно и а так как и взаимно просты, то оно кратно и

Пусть исходное число равно После перестановки цифр получилось число

Поскольку получено из перестановкой цифр, то сумма цифр числа равна сумме цифр числа

Число делится на следовательно, сумма его цифр делится на Так как сумма цифр числа равна сумме цифр числа то сумма цифр числа также делится на Значит, число делится на

Раз делится на то где - целое число. Тогда Значит, делится на

Так как делится на то сумма его цифр делится на Следовательно, сумма цифр числа также делится на а значит, и число делится на

Раз делится на то где - целое число. Тогда Значит, делится на что и требовалось доказать.

Разложим на взаимно простые множители: Потребуем делимости на и на

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

Далее, чтобы число делилось на необходимо, чтобы сумма цифр делилась на Значит, сумма цифр не меньше и в записи не меньше единиц.

Наименьшее число, в котором единиц и в конце, это Оно нам подходит.

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

Представим в виде или для некоторого целого числа

* Если то В этом случае остаток от деления на равен

* Если то В этом случае остаток от деления на равен

Следовательно, возможные остатки от деления на - это или

Условие задачи равносильно тому, что число, увеличенное на должно делиться на Ввиду взаимной простоты чисел и это число делится на Но не делится на Наименьшее общее кратное (НОК) чисел равно Тогда число, увеличенное на должно делиться на Значит, наименьшее такое число равно а искомое число равно