#include <stdio.h>
 
int getInverse(int a, int b)
{
    int x1 = 1, y1 = 0, z1 = a, x2 = 0, y2 = 1, z2 = b, q, t;
    while (z2 > 1) {
        q = z1 / z2;
        x1 -= q * x2,  y1 -= q * y2,  z1 -= q * z2;
        #define SWAP(a, b)  (t = a, a = b, b = t)
        SWAP(x1, x2),  SWAP(y1, y2),  SWAP(z1, z2);
    }
    return x2 < 0 ? x2 + b : x2;
}
 
int main(void)
{
    int r, q;
    while (printf(">> "), scanf("%d%d", &r, &q) == 2)
        printf(" inverse(%d) = %d (mod %d)\n",
                r, getInverse(r, q), q);
    return 0;
}