A=kN+a
B=sN+b
kN+sN делится на N нацело
Тогда остаток от деления на сумму равен:
a+b если a+b <N
a+b-N если a+b >= N (остаток всегда меньше делителя)
kN-sN делится на N нацело
Тогда остаток от деления на разность равен:
a-b если a-b > 0
N-(a-b) если a-b <=0
(kN+a)(sN+b)
kNb+sNa+ksN^2 делится нацело
Остаток равен ab если ab<N
Остаток равен остатку от деления ab на N(невозможно записать проще)
A/B=(kN+a)/(sN+b)
Воспользуемся сравнениями по модулям
A==a(mod N)
B==b(modN)
A/B==a/b(mod N)
Тогда остаток будет = a/b, но мы сможем его найти только если остатки a и b делятся друг на друга нацело и A/B тоже делятся друг на друга нацело.
1
Пошаговое объяснение: