Задача 65071

Темы:    [ Основная теорема арифметики. Разложение на простые сомножители ] [ Доказательство от противного ]

Сложность: 3+ Классы: 8,9

Условие

Автор: Кожевников П.А.

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

Решение

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

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

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