М1476

Условие

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

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

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

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

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

Лемма 1

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

Лемма 2

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

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

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

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

Замечание.

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

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

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

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