олимпиада - Комфортные системы счислений

Как известно, в десятичной системе счисления имеет место признак делимости на $%9$%. В более общем виде его можно сформулировать так: разность числа и суммы его цифр в десятичной записи кратна $%9$%.

Аналогичный признак справедлив для любой системы счисления с основанием $%g > 1$%. Роль числа $%9$% при этом играет число $%g-1$%. Доказательство основано на том, что $%g^n-1$% делится на $%g-1$% при любом натуральном $%n$% (это хорошо известный факт). Тогда, если в разряде, который соответствует $%n$%-й степени $%g$%, стоит цифра $%a$%, то она вносит в число вклад $%ag^n$%, и если её вычесть, то получится $%a(g^n-1)$%, что кратно $%g-1$%. Суммируя такие значения по каждой цифре числа, мы получим то, что надо.

Предположим теперь, что $%g$%-значное число $%N$% представлено в системе счисления с основанием $%g$% своими цифрами, каждая из которых встречается в записи числа ровно по разу. Пусть $%a_0$%, $%a_1$%, $%\ldots$%, $%a_{g-1}$% -- цифры числа, прочитанные справа налево. Тогда разность числа и его суммы цифр кратна $%g-1$%. Поскольку цифры представляют собой перестановку цифр от $%0$% до $%g-1$% включительно, сумма цифр равняется $%1+2+\cdots+(g-1)=(g-1)g/2$%, согласно известной формуле. Таким образом, мы приходим к выводу, что разность $$N-\frac{(g-1)g}2$$ кратна $%g-1$%.

Если $%g$% чётно, что отсюда следует, что $%N$% кратно $%g-1$%. Случай $%g=2$% легко рассмотреть отдельно, придя к выводу, что это основание является комфортным, так как число $%10_2$% равно двум, то есть является простым. Во всех остальных случаях $%N$% будет составным, так как оно не равно $%g-1$% (последнее полагается очевидным). Таким образом, для чётных $%g$% подходит только значение $%g=2$%.

Пусть теперь $%g$% нечётно. Тогда $%(g-1)/2$% -- натуральное число, и из предыдущего ясно, что $%N$% кратно $%(g-1)/2$%. Случай $%g=3$% уже исследован, а при $%g > 3$% оказывается, что $%N$% имеет ещё хотя бы один делитель помимо $%1$% и себя самого (это $%(g-1)/2 > 1$%), и тем самым не является простым.