Question

Подскажите алгоритм решения таких задач?

Answer 1

Алгоритм решения таких задач достаточно прост.
Вспоминаем, как мы переводим число из десятичной системы счисления в систему счисления по основанию n. Мы берем десятичное число, делим его на n, записываем остаток, а частное снова делим на n, продолжая процесс, пока частное не станет меньше n. А затем записываем частное и приписываем к нему остатки в обратном порядке. Следовательно, последней цифрой в записи числа будет первый полученный остаток.

1. Известно, что 41(10)=xxx...x2(n), где хххх - некоторые цифры числа в системе по основанию n. Отметим, что при делении 41 на n получается остаток 2.
Также сказано, что 131(10)=xxx...x1(n), т.е. при делении 131 на n остаток равен 1.
Составим систему двух уравнений.
$\begin {cases} 41=k_1n+2 \\ 131=k_2n+1 \end {cases} \to \begin {cases} k_1n=39 \\ k_2n=130\end {cases}; \quad \begin {cases} k_1n=3\times\underline{13} \\ k_2n=2\times5\times\underline{13}\end {cases}$
Представление чисел 39 и 130 в виде простых множителей позволяет выделить их наибольший общий делитель (НОД), который и будет являться искомым основанием системы счисления n. Итак, n=13

2. Теперь, когда алгоритм известен, решение можно получить и быстрее.
58 = k1 x n + 2 ⇒ k1 x n = 56 = 2 x 2 x 2 x 7;
103 = k2 x n + 3 ⇒ k2 x n = 100 = 2 x 2 x 5 x 5
НОД = 2 х 2 = 4 ⇒ n=4

Окончательный алгоритм: вычитаем из каждого десятичного числа остаток и для полученной пары чисел ищем НОД, который и будет основанием системы счисления.