#/***********************************************************
#    inv.rb -- ¹çƱ¼°
#***********************************************************/

def inv( a,  n )
    d = n;  x = 0;  s = 1
    while (a != 0) 
        q = d / a
        r = d % a;  d = a;  a = r
        t = x - q * s;  x = s;  s = t
    end
    gcd = d;  # $\gcd(a, n)$ 
    return ((x + n) % (n / d)), gcd
end

printf("a = ");  a = gets.to_i
printf("n = ");  n = gets.to_i
x, d = inv(a, n)
printf("a = %d, n = %d, d = gcd(a,n) = %d\n", a, n, d)
printf("ax = d (mod n) <==> x = %d (mod n / d)\n", x)
exit 0