Ну я вспомнил что число в десятичной системе счисления
Делится на 9 (то есть на 10-1)
Если сумма его цифр делится на 9
Я предположил что в любой k-ичной системе счисления верно
Что если сумма цифр некоторого числа делится на k-1 то и это число делится на k-1
И это оказалось правдой для тех k
Которые содержатся в тестах к этой задаче.

Большое спасибо! Эта подсказка мне помогла.

Доказательство вашего утверждения:
Пусть мы сейчас в k-ой системе счисления и если прочитать наше число X слева направо, то получим цифры a_n, a_{n - 1}, ... , a_1, a_0 (при этом 0 <= a_i <= k - 1 для всех i). Тогда в десятичной системе счисления оно будет равно X = a_n * k ^ n + a_{n - 1} * k ^ {n - 1} + ... + a_1 * k + a_0. Так как k = 1 (mod (k - 1)), то X = a_n + a_{n - 1} + ... + a_1 + a_0 (mod (k - 1)). Значит, X делится на (k - 1) тогда и только тогда, когда его сумма цифр делится на (k - 1).