Конкурсная задача ММ29 (7 баллов)

Назовем натуральное число «полуквадратным», если приписывая это число само к себе, получим квадрат натурального числа.
1) существуют ли полуквадратные числа в десятичной системе счисления? (2 балла)
2) для каких g (натуральных, больших 1) в системе счисления с основанием g существуют полуквадратные числа? (5 баллов)

Решение

1) Да. Например, приписывая число 20661157025 к себе, получим квадрат числа 45454545455.

2) Полуквадратные числа существуют для любых оснований g. Ясно, что число полученное приписыванием числа a к себе равно a(gⁿn+1), где n - количество цифр в g-ичной записи числа a.
Для того, чтобы построить полуквадратное число, достаточно подобрать n таким, чтобы gⁿ+1 делилось на квадрат натурального числа, большего 1. В самом деле, если gⁿ+1 = s²t, то в качестве a годится число stk, где множитель k подбирается так, чтобы разрядность aⁿ равнялась 2ⁿ. Этого всегда можно добиться, поскольку количество цифр для чисел последовательности a, 4a, 9a… при переходе к следующему числу увеличивается не более чем на единицу. (Исключение составляет переход a - 4a при g=2, но и для для g=2 существуют полуквадратные числа. Например, 100100 - двоичная запись числа 36.)

Остается показать, что для любого натурального g, большего 1, найдется подходящее n. Сделать это можно разными способами. Например, легко проверить что:
1) Если g четно, g^g+1+1 ≡ 0(mod (g+1)²):
2) При g = 4k+3 g+1 ≡ 0(mod 4);
3) При g = 4k+1 g^2k+1+1 ≡ 0(mod (2k+1)²)

Награды

За правильное решение этой задачки Макс Алексеев, Влад Франк и Олег Копылов получают по 7 призовых баллов. За правильное решение первого пункта задачи Анрей Бежан получает 2 призовых балла