Версия для печати
Убрать все задачи
Пусть число m1 в десятичной системе счисления записывается при помощи n цифр.
Докажите, что при любом m0 число шагов k в алгоритме Евклида для чисел m0 и m1 удовлетворяет неравенству k ≤ 5n.

Решение
Имеется бесконечное количество карточек, на каждой из которых написано какое-то
натуральное число. Известно, что для любого натурального числа n существуют
ровно n карточек, на которых написаны делители этого числа. Доказать, что
каждое натуральное число встречается хотя бы на одной карточке.

Решение