ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 65071
Темы:    [ Основная теорема арифметики. Разложение на простые сомножители ]
[ Доказательство от противного ]
Сложность: 3+
Классы: 8,9
В корзину
Прислать комментарий

Условие

Даны натуральные числа a и b, причём  a < 1000.  Докажите, что если a21 делится на b10, то a² делится на b.


Решение

Предположим, что найдётся простое число p, входящее в разложение числа a² на простые множители с показателем меньшим, чем в разложение числа b. То есть, если a делится на pk, но не делится на pk+1, а b делится на pm, но не делится на pm+1, то  m > 2k,  а значит,  m ≥ 2k + 1. Но из делимости a21 на b10 следует, что  21k ≥ 10m.  Отсюда  21k ≥ 10(2k + 1),  то есть  k ≥ 10.  Но  a < 1000 < 210p10pk,  поэтому a не может делиться на pk. Противоречие.

Источники и прецеденты использования

олимпиада
Название Олимпиада имени Леонарда Эйлера (для 8 классов)
год/номер
Номер 2 (2010)
тур
задача
Номер 4

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .