Задача 3. Длинное число Арсения

Что нужно доказать

Число составное, если его можно разложить в произведение двух натуральных чисел, каждое из которых больше $1$. Иначе говоря, у него есть делитель, отличный от $1$ и от самого числа.

Сколько раз Арсений дописал четвёрку, в условии не сказано — «несколько раз» (по тексту видно, что не меньше трёх). Обозначим число четвёрок буквой $k$: доказательство должно годиться при любом $k$.

Признаки делимости здесь не выручают. Число оканчивается на $1$, поэтому не делится ни на $2$, ни на $5$. С делимостью на $3$ — как повезёт. При трёх четвёрках в числе $37$ троек, $3$ четвёрки и единица, и сумма цифр

на $3$ не делится, а при пяти четвёрках в числе $55$ троек, и сумма цифр $3\cdot 55+4\cdot 5+1=186$ делится на $3$. Значит, делитель, который подходит всегда, надо искать в самом устройстве числа.

Откуда берутся четвёрки

Посмотрим на начало числа: десять троек и четвёрка. Будь на месте четвёрки единица, получилось бы число

— десять троек и единица. А четвёрка — это $1+3$: как будто здесь единица одного такого числа сложилась с первой тройкой следующего.

Проверим догадку. Запишем $B$, а под ним ещё раз $B$, сдвинутое на $10$ разрядов вправо, и сложим в столбик (рисунок ниже). Единица верхнего числа встречается с первой тройкой нижнего: $1+3=4$. В остальных разрядах стоит только одна цифра, переносов нет. Получается

то есть десять троек, четвёрка, девять троек и единица — число Арсения с одной четвёркой.

Верхнее число стоит на $10$ разрядов левее: это $B$ с десятью нулями на конце, то есть $B\cdot 10^{10}$ (здесь $10^{10}$ — единица с десятью нулями). Нули при сложении ничего не меняют, поэтому их не пишут. Значит, мы сложили $B\cdot 10^{10}+B$.

Столько копий, сколько нужно

Если четвёрок $k$, возьмём на одну копию больше: $k+1$ копий числа $B$. Запишем их лесенкой — каждую следующую на $10$ разрядов правее предыдущей (рисунок ниже, для трёх четвёрок).

Соседние копии перекрываются ровно в одном разряде: единица верхней над первой тройкой нижней, $1+3=4$. Остальные разряды заняты одной цифрой, переносов нет. Читаем сумму слева направо: десять троек первой копии, $4$, девять троек, $4$, девять троек, …, $4$, девять троек и единица последней копии.

Каждый стык двух соседних копий даёт одну четвёрку, а стыков на один меньше, чем копий, — ровно $k$. Получилось в точности число Арсения с $k$ четвёрками.

Сумма копий — это произведение

Копии в лесенке — это $B$, умноженное на $10^{10k}$, …, $10^{20}$, $10^{10}$ и $1$. Сложить их — то же, что умножить $B$ на сумму этих чисел (распределительный закон: $B\cdot a+B\cdot b=B\cdot(a+b)$):

Второй множитель записывается единицами и нулями: $k+1$ единиц, между соседними единицами — по девять нулей. Например, при трёх четвёрках

Оба множителя больше $1$. Первый — это $B=33333333331$. Второй не меньше $10000000001$: четвёрка в числе есть, значит, копий хотя бы две. Число Арсения разложено в произведение двух множителей, больших $1$, поэтому оно составное.

Обрати внимание: не нужно выяснять, простое ли число $33333333331$. Достаточно, что оно больше $1$ и меньше всего числа.

Второй вариант

Рассуждение то же, меняются цифры: вместо троек — двойки, вместо четвёрок — тройки, а группы на одну цифру короче ($9$ и $8$ вместо $10$ и $9$).

Теперь «кирпичик» — число $2222222221$: девять двоек и единица, $10$ цифр. Пусть троек $k$. Запишем $k+1$ копий кирпичика лесенкой, каждую следующую на $9$ разрядов правее. Соседние копии встречаются в одном разряде: единица верхней над первой двойкой нижней, $1+2=3$; в остальных разрядах по одной цифре, переносов нет. Сумма — девять двоек, $3$, восемь двоек, $3$, …, восемь двоек и единица, то есть число Елизаветы с $k$ тройками. Например,

Значит,

Первый множитель больше $1$, второй не меньше $1000000001$, потому что тройка в числе есть. Число составное.