Условие

Докажите, что не существует различных простых чисел 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] нечетны).

Задача из журнала «Квант» (1995 №2)

Условие

В треугольнике [latex]ABC[/latex] проведена биссектриса [latex]AK[/latex], [latex]D[/latex] — точка пересечения биссектрисы внешнего угла при вершине [latex]B[/latex] с описанной окружностью. Докажите, что если [latex]\angle A> \angle C[/latex], то

[latex]\sin A / \sin C- \sin \angle CDK/ \sin \angle BDK=1.[/latex]

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

Пусть углы [latex]A, B, C[/latex] треугольника равны [latex]2\alpha, 2\beta, 2\gamma[/latex] соответственно. Биссектриса внутреннего угла [latex]B[/latex] пересекает дугу [latex]AC[/latex] описанной окружности в точке [latex]L[/latex], диаметрально противоположной [latex]D[/latex](рис. 1).

Рис. 1

Положим [latex]\angle CBD=\delta, \angle BCD=\varepsilon[/latex]. Используя теорему синусов(для [latex]\vartriangle DBK[/latex] и [latex]\vartriangle CDK[/latex]), теорему о биссектрисе треугольника ([latex]BK/KC = AB/AC = \sin 2\gamma / \sin 2\beta[/latex]) и формулу

[latex]2 \sin \varphi \cos\psi = \sin(\varphi + \psi) — \sin(\psi — \varphi)[/latex],

получаем

[latex]\frac{\sin \angle CDK}{\sin \angle BDK} = [/latex] [latex]\frac{KC \sin \varepsilon}{KB \sin \delta} = [/latex] [latex]\frac{ \sin 2\beta \cdot \sin \frac{\pi — 4\gamma — 2\beta}{2}}{\sin 2\gamma \cdot \sin \frac{\pi — 2\beta}{2}} = [/latex]

[latex]\frac{2 \sin \beta \cos \beta \cos(2\gamma + \beta)}{\sin2\gamma \cos \beta} = [/latex] [latex]\frac{\sin(2\beta + 2\gamma)}{\sin2\gamma} — 1 = [/latex] [latex]\frac{\sin2\alpha}{\sin2\gamma} — 1[/latex]

что и требовалось доказать.

Замечание

Если [latex]\angle A< \angle C[/latex] (как на рисунке 2), то меняется лишь знак в формуле

[latex]\sin \varepsilon = \sin(2\gamma + \beta — \pi /2)= — \cos (2\gamma + \beta)[/latex]

а [latex]\sin \delta[/latex] по-прежнемe равен [latex]\sin( \beta + \pi /2) = \cos \beta[/latex], так что равенство в условии принимает вид

[latex]\frac{\sin A}{\sin C} + \frac{\sin \angle CDK}{\sin \angle BDK} = 1[/latex]

Рис. 2

Задача из журнала «Квант»(1989, №5)

Условие

В бильярдном треугольнике вплотную помещается $10$ шаров. Докажите, что если в нем поместить $9$ шаров, то обязательно останется место для десятого (т.е. центры $9$ шаров расположатся по треугольной сетке)

Решение

Примем диаметр шара за $1$. Задача эквивалентна следующей: доказать, что если $9$ точек $K_1, K_2, \cdots, K_9$, попарные расстояния между которыми не меньше $1$, размещены в правильном треугольнике со стороной $3$, то они обязательно находятся в вершинах треугольной решетки со стороной $1$ (в $9$ из $10$ черных точек на рисунке 2). Достаточно доказать, что $6$ (или $7$) из точек $K_i$ находяться в пределах красного шестиугольника, причем они обязательно находяться в его вершинах или в центре $O$ — ведь в каждом угловом треугольнике со стороной $1$ (не на красной стороне) может находится лишь одна из точек $K_i$, причем если на его красной стороне есть другая точка $K_j$, то $K_i$ лежит в вершине большого треугольника.

Ясно, что если одна из $6$ точек $K_i$ внутри шестиугольника совпадает с $O$, то остальные лежат в вершинах. Если же все они отличны от $O$, то отрезки $OK_i$, проведенные в эти точки, образуют между собой углы $60^{\circ}$ (если $\angle K_i O K_j < 60^{\circ} $, $OK_i \leq 1$ , $OK_j \leq 1$, то $K_i K_j$ < 1 ) и $OK_i = 1$

По-видимому, верен и такой факт: если из $1+2+\cdots+n = \frac{n(n+1)}{2}$ шаров, вплотную уложенных в треугольную коробку, убрать один шар, то остальные обязательно будут распологаться по треугольной сетке — так что убранный шар можно уложить на место.