М1476

Условие

Докажите, что не существует различных простых чисел p, q таких, что 2^{p}+1 делится на q, 2^{q}+1 делится на p.

Доказательство

Ясно, что p и q нечетны, и если одно из них равно 3, то другое тоже должно равняться 3. Поэтому будем в дальнейшем считать, что p>q>3.

Первое решение.

Из условия следует, что 2^{2p}\equiv1(\bmod m).
С другой стороны, согласно малой теореме Ферма, для простого q имеем: 2^{q-1}\equiv1(\bmod q).
Пусть n — найменьшее натуральное число такое, что 2^n=1(mod q). Тогда n\neq 2 — отличный от единицы делитель числа 2p. Значит, n=p либо n=2p, т.е. n не является делителем числа q-1. Противоречие.
Второе решение можно получить, опираясь на следующее утверждение.

Лемма 1

Пусть pq — простые числа, q\neq 3,2^{p}+1 делится на q. Тогда q=2kp+1, где k — натуральное число. Эту лемму легко доказать, заметив, что число n в первом решении равно 2p. Из нее следует, что q>p. Противоречие.
Еще одно решение можно получить, опираясь на такое утверждение.

Лемма 2

Если числа a и b взаимно просты, то НОД(2^{a}+1, 2^{b}+1)=1,

либо НОД(2^{a}+1, 2^{b}+1)=3
(причем второй случай имеет место тогда и только тогда, когда a и b нечетны).

Третье решение

Имеем:2^{p}+1 делится на q; 2^{q-1}-1, по малой теореме Ферма, также делится на q. Следовательно, и 2^{p-q+1}+1 делится на q — в противоречии с леммой 2.

Замечание.

Лемма 2 является частным случаем следующего несложного утверждения. Пусть НОД(m,n)=1, НОД(a,b)=d, НОД(m^{a}+n^{a}, m^{b}+n^{b})=d_{1}. Тогда d_{1}=m^{d}+n^{d}, если числа \frac{a}{d} и \frac{b}{d} оба нечетны; d_{1}=1 либо d_{1}=2 в противном случае (а именно: d_{1}=1, если m и n разной четности; d_{1}=2, если m и n нечетны).

М1476: 1 комментарий

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *