3.13Деление.

В случае деления может получиться вещественное число, что недопустимо. Выход состоит в том, чтобы найти такое число, умножив на которое делитель, получим число, дающее в остатке от деления на n единицу.

a/b mod n = (a*k)/(b*k) mod n = (a*k mod n)/(b*k mod n)

Если b*k mod n=1, то (a*k mod n)/(b*k mod n) = a*k mod n. Таким образом, требуется найти k. Это можно сделать, перебирая числа m, удовлетворяющие выражению b*k = m*n+1, причем m=1, 2, …, а k должно быть целое. Заметим, что предложенный метод поиска k не является единственным и наилучшим.

А=m1*m2*m3*…

B=n1*n2*n3*…

N=k1*k2*k3*…

Если А не делится нацело на В, то среди множителей найдется, по крайней мере, один не совпадающий.