Question

Четное число а такое, что если оно делится на простое число р, то а – 1 делится на р – 1. Докажите, что число а является степенью двойки.

Answer 1

Предположим, что число а делится на простое число p>2, тогда:

(р-1) будет четным числом, т. к. все простые р>2 нечетные.

(а-1) будет нечетным числом, т. к. по условию а четно.

Получается нечетное число (а-1) делится на четное число (р-1). Противоречие, значит предположение, что а делится на простое р>2 было ошибочно. Из этого следует, что в разложении на множители числа р могут участвовать только 2.

Число а делится на 2, а число (а-1) делится на 2-1=1.

Получается число а является степенью двойки, ч. т. д.

Answer 2

Для доказательства этого утверждения, воспользуемся противоречием.

Предположим, что число а не является степенью двойки. Это означает, что а не может быть записано в виде 2^k для некоторого целого k.

Так как а не является степенью двойки, оно имеет хотя бы один нечетный простой делитель p. Рассмотрим этот нечетный простой делитель p.

Из условия задачи мы знаем, что если а делится на p, то а – 1 делится на p – 1. Это означает, что существует такое натуральное число k, что а – 1 = k(p – 1).

Раскроем скобки в этом уравнении: а – 1 = kp – k.

Так как а – 1 делится на p – 1, то оно также делится на k. Значит, существует натуральное число m, такое что а – 1 = mk.

Теперь мы имеем два уравнения: а – 1 = k(p – 1), а – 1 = mk.

Приравняем их: k(p – 1) = mk.

Мы можем сократить на k, так как оно не равно нулю: p – 1 = m.

Таким образом, мы получили, что p – 1 = m.

Заметим, что p – 1 — это четное число, так как p — нечетное простое число. Но это противоречит условию, которое говорит, что а – 1 должно делиться на p – 1.

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