М1762. Две тысячи делителей

Задача из журнала «Квант» (2001 год, 4 выпуск)

Условие

Существует ли натуральное число $n$ такое, что $n$ имеет ровно $2000$ различных простых делителей и $2^n+1$ делится на $n$?

Решение

Докажем по индукции, что для любого натурального $k$ существует натуральное $n_k$, имеющее $k$ различных простых делителей, делящееся на $3$ и такое, что $2^{n_k}+1$ делится на $n_k$.

Для $k=1$ можно взять $n=3$. Пусть число $n_k=n$, кратное $3$, имеет $k$ различных простых делителей, причём $2^n+1$ делится на $n$.

Число $2^{3n}+1=\left(2^n+1\right)\left(2^{2n}-2n+1\right)$ делится на $3n$. Это следует из того, что $2^n+1$ делится на $n$, а
$$2^{2n}-2^n+1=\left(2^n-2\right)\left(2^n+1\right)+3\;\;\;(*)$$ делится на $3$ (поскольку при нечётном $n$ числа $2^n+1$ и $2^n-2$ делятся на $3$).

Далее, число $2^{2n}-2^n+1$ не делится на $9$, поскольку на $9$ делится произведение $\left(2^n-2\right)\left(2^n+1\right)$. Значит, поскольку $2^{2n}-2^n+1>3$ при $n>1$, то это число имеет при $n>1$ простой делитель $p>3$. Так как НОД $\left(2^n+1, 2^{2n}-2^n+1\right)=3$ (это тоже ясно из равенства $(*)$), то $p$ — не делитель $n$.

Из сказанного следует, что число $3pn$ имеет $k+1$ простой делитель, причём $2^{3pn}+1$ делится на $3pn$. Последнее следует, например из равенства
$$\left(2^{3n}\right)^p+1=\left(2^{3n}+1\right)\left(\left(2^{3n}\right)^{p-1}-\left(2^{3n}\right)^{p-2}+\cdots+1\right)$$

Для завершения решения достаточно положить $n_{k+1}=3pn=3pn_k$.

А.Егоров, В.Сендеров

М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 нечетны).

М1473. О записи степеней двойки

Задача из журнала «Квант» (1995, выпуск №4)

Пусть c_{n} — первая цифра числа 2^{n} (в десятичной записи).

  1. Сколько единиц среди первых 1000 членов этой последовательности?
  2. Докажите, что в последовательности
    $$ c_{1}=2, \quad c_{2}=4, \quad c_{3}=8, \quad c_{4}=1, \quad c_{5}=3, \quad… $$

    встретится ровно 57 различных «слов» c_{k}c_{k+1}...c_{k+12} длины 13.

Решение

  1. Отметим на «логарифмической шкале» y=\log_{10}{x} числа x=2^{n} (каждая следующая отметка получается из предыдущей сдвигом на расстояние   \log_{10}{2}). Число x начинается с 1, если   10^{k} \le x < 2 \cdot 10^{k+1}   для некоторого k; соответствующие интервалы на рисунке 1 выделены красным (поскольку длина интервала как раз равна   \log_{10}{2}, на каждый из них попадает ровно одна отметка). Поскольку

    $$ \log_{10}{2} = 0.30103…, \quad 10^{301} \le 2^{1000} < 10^{302}, $$

    так что   2^{n}(n=0,1,2,...,1000)   ровно 301 раз перейдет через степень 10 и поэтому (не считая 2^{0}=1) 301-ый её член начинается с 1.

  2. line

  3. Чтобы более детально разобраться в закономерностях последовательности c_{n}, свернем логарифмическую шкалу y=\log{10}{x} в «логарифмический круг» z=y-\left[ y \right]: каждый отрезок от 10^k до 10^{k+1} даёт новый оборот круга, а точки 0=\log_{10}{1}, \quad \log_{10}{2}, \quad \log_{10}{3}, \quad ..., \quad \log_{10}{9} — границы интервалов, в которых расположены значения z, соответствующие различным первым значащим цифрам числа x от 1 до 9 (см. рисунок 2).

    log_circle

    Прежде чем решать задачу (2), объясним идею рассуждения на более простом примере: выясним, сколько разных пар \left( c_{k}, c_{k+1} \right) цифр встречается в нашей последовательности. Читать далее «М1473. О записи степеней двойки»