«Квант» — научно-популярный физико-математический журнал (издаётся с 1970 года)
Старый сайт журнала: kvant.ras.ru

Задача М981

Условие задачи (1986, № 5) Задача М981 // Квант. — 1986. — № 5. — Стр. 28; 1986. — № 9. — Стр. 39—40.

Докажите, что число $11\ldots1$‍‍ (1986 единиц) имеет по крайней мере

  1. 8,
  2. 28

различных делителей.

Л. Д. Курляндчик


Решение задачи (1986, № 9) Задача М981 // Квант. — 1986. — № 5. — Стр. 28; 1986. — № 9. — Стр. 39—40.

а) Ясно, что если число $a$‍‍ записывается $n$‍‍ единицами, число $b$‍‍ записывается $k$‍‍ единицами и $n$‍‍ делится на $k$‍,‍ то и $a$‍‍ делится на $b$‍.‍ А поскольку $1986=2\cdot3\cdot331$‍,‍ число $A=11\ldots1$‍‍ из 1986 единиц имеет кроме числа 1 и самого $A$‍‍ ещё по крайней мере 6 делителей из одних единиц: $$ 11,~111,~111~111,~\underbrace{11\ldots1}_{331},~\underbrace{11\ldots1}_{662},~\underbrace{11\ldots1}_{993\vphantom q}. $$

б) Мы укажем не 28, а сразу 128 делителей числа $A$‍.‍ Заметим, что $111111$‍‍ раскладывается на 5 простых множителей: $$ 111111=1001\cdot111=3\cdot7\cdot11\cdot13\cdot37. $$ Учитывая, что $10^{993}+1$‍‍ делится на $10^3+1=1001$‍,‍ а $10^{993}-1$‍‍ — на $10^3-1=999$‍‍‍ и полагая $a=10^{331}$‍,‍ получим $$ A=\dfrac{a^{6}-1}9=(a^{3}+1)\dfrac{a^{3}-1}9=3\cdot7\cdot11\cdot13\cdot37\cdot \dfrac{a^{3}+1}{1001}\cdot\dfrac{a^{3}-1}{999}. $$ Произведение любого набора из этих 7 множителей будет делителем $A$‍‍ («пустому набору» отвечает делитель 1). Таким образом, мы нашли $2^7=128$‍‍ делителей, причём все они различны. Чтобы убедиться в этом, докажем, что все 7 множителей в выписанном разложении $A$‍‍ попарно взаимно просты. В самом деле, остаток от деления числа $a$‍‍ на $m=10^{6}-1$‍‍ равен 10, поскольку $10^{331}-10=10(10^{6\cdot55}-1)$‍‍ делится на $m$‍;‍ поэтому $a^{3}\pm1$‍‍ при делении на $m$‍‍ даёт остаток $10^{3}\pm1$‍,‍ т. е. числа $\dfrac{a^{3}+1}{1001}$‍‍ и $\dfrac{a^{3}-1}{999}$‍‍ взаимно просты с $m$‍‍ и, очевидно, взаимно просты друг с другом.

Нетрудно продолжить разложение $A$‍‍ на взаимно простые множители: $$ A=3\cdot7\cdot11\cdot13\cdot37\cdot\dfrac{a+1}{11}\cdot\dfrac{a^{2}-a+1}{91}\cdot \dfrac{a^2+a+1}9\cdot\dfrac{a^2+a+1}{111}. $$ (из выделенного выше курсивом утверждения следует, что сомножители здесь целые); отсюда видно, что $A$‍‍ имеет не менее $2^{9}=512$‍‍ делителей. Продолжить это разложение «вручную» уже трудно. Однако из малой теоремы Ферма‍ следует, что $9A=10^{1986}-1$‍‍ делится на простое число 1987. Таким образом, один из 4 последних сомножителей должен делиться на 1987, а значит, $A$‍‍ имеет не менее $2^{10}=1024$‍‍ делителей. Может быть, кому-то из читателей удастся поднять эту оценку ещё выше?

Н. Б. Васильев, Л. Д. Курляндчик


Метаданные Задача М981 // Квант. — 1986. — № 5. — Стр. 28; 1986. — № 9. — Стр. 39—40.

Предмет
Математика
Условие
Решение
,
Номера

1986. — № 5. — Стр.  [условие]

1986. — № 9. — Стр.  [решение]

Описание
Задача М981 // Квант. — 1986. — № 5. — Стр. 28; 1986. — № 9. — Стр. 39‍—‍40.
Ссылка
https://www.kvant.digital/problems/m981/