Пусть N - целое число, последняя цифра которого - семёрка. Докажите что существует число вида 111...111 (т.е., его десятичная запись состоит только из единичек), которое делится на N.
Ну, всё-таки, надо Теорему Эйлера знать. Лично я про неё совсем забыл уже.
А решение имелось в виду такое: рассмотрим числа 1, 11, 111, ..., 111...111, N+1 штуку. Очевидно, из них есть по крайней мере парочка, у которых остаток от деления на N один и тот же. Вычтем, получим число вида 111...111000...000, которое делится на N. Но, поскольку N не делится ни на 2, ни на 5, нули можно смело отбросить.
Comments 5
(10^phi(9N) - 1) / 9
https://ru.wikipedia.org/wiki/Теорема_Эйлера_(теория_чисел)
Reply
Reply
Куда уж элементарнее? К тому же построение конструктивное и работает для всех последних цифр, когда есть решение (т.е. кроме 0 и 5).
Reply
А решение имелось в виду такое: рассмотрим числа 1, 11, 111, ..., 111...111, N+1 штуку. Очевидно, из них есть по крайней мере парочка, у которых остаток от деления на N один и тот же. Вычтем, получим число вида 111...111000...000, которое делится на N. Но, поскольку N не делится ни на 2, ни на 5, нули можно смело отбросить.
Reply
Leave a comment