Нахождение обратного элемента по модулю

Для начала заметим, что элемент a кольца Z_n обратим тогда и только тогда, когда НОД(a,n)=1. То есть ответ есть не всегда. Из определения обратного элемента прямо следует алгоритм.

Псевдокод

НА ВХОДЕ: а из Zn.
НА ВЫХОДЕ: обратный к а в кольце, если он существует.

1. Использовать расширенный алгоритм Евклида для нахождения
 x и y, таких что ax + ny = d, где d=НОД(a,n).
2. Если d > 1, то обратного элемента не существует.
 Иначе возвращаем x.

Исходник на Си

/* Author: Pate Williams (c) 1997 */

#include <stdio.h>

void extended_euclid(long a, long b, long *x, long *y, long *d)
/* вычисление a * *x + b * *y = gcd(a, b) = *d */
{
 long q, r, x1, x2, y1, y2;
 if (b == 0) {
 *d = a, *x = 1, *y = 0;
 return;
 }

 x2 = 1, x1 = 0, y2 = 0, y1 = 1;
 while (b > 0) {
 q = a / b, r = a - q * b;
 *x = x2 - q * x1, *y = y2 - q * y1;
 a = b, b = r;
 x2 = x1, x1 = *x, y2 = y1, y1 = *y;
 }

 *d = a, *x = x2, *y = y2;
}

long inverse(long a, long n)
/* вычисление инверсии модуля n */
{
 long d, x, y;
 extended_euclid(a, n, &x, &y, &d);
 if (d == 1) return x;
 return 0;
}

// главная фукнция
int main(void)
{
 long a = 5, n = 7;
 printf("инверсия %ld modulo %2ld is %ld\n", a, n, inverse(a, n));
 a = 2, n = 12;
 printf("инверсия %ld modulo %2ld is %ld\n", a, n, inverse(a, n));
 return 0;
}