M22. Вычисление остатка с использованием модульной арифметики

1. То, что запись числа (59)⁹⁶ содержит 171 цифру, следует из того факта, что

96log₁₀(59)=96(1.77085...)=170.0018...

Отсюда вытекает, что число (59)⁹⁶ заключено между величинами 10¹⁷⁰ и 10¹⁷¹, и следовательно, его запись содержит 171 цифру.

2. При использовании модульной арифметики бывает выгодно вычесть из показателя степени максимально возможную степень двойки, затем возвести число в степень (нечетного) остатка, и наконец, последовательно возводя его в квадрат, найти требуемое значение. Так, например, поскольку 96=332, то если мы вычислим (59)³(mod 97) и последовательно возведем это значение в квадрат пять раз, на каждом этапе приводя результат по модулю 97, то в результате получим нужное нам число. В деталях это выглядит так:

5959=3481=3597+86,

следовательно,

(59)³8659=5074=5297+3030(mod 97),

поэтому

(59)⁶(30)²=900=997+2727(mod 97),

поэтому

(59)¹²(27)²=729=797+5050(mod 97),

следовательно,

(59)²⁴(50)²=2500=2597+7575(mod 97),

следовательно,

(59)⁴⁸(75)²=5625=5797+9696(mod 97) -1(mod 97),

и наконец,

(59)⁹⁶(-1)²=1(mod 97),

то есть, как и утверждалось, (59)⁹⁶ дает при делении на 97 остаток 1.