Нахождение обратного элемента в кольце вычетов

Смотрите.

Для начала, A и C должны быть взаимно просты. Если они не взаимно просты, то любая линейная комбинация (A * X) % C = A * X + C * Y не будет равна единице, то есть, ответа нет.

Окей, пускай числа A и C взаимно просты. Для установления этого вы должны использовать алгоритм Евклида для вычисления НОД. Если вы при этом воспользуетесь , вы получите не просто НОД, а и те коэффициенты alpha, beta, при которых

alpha * A + beta * C = НОД(A, C) = 1.

При этом alpha и есть ваш ответ, так как

(alpha * A) % C = (1 - beta * C) % C = 1.

Все остальные значения B получаются из данного прибавлением кратного числу C.