\ return "extended gcd" of a and b; The result satisfies the equation:
\     a*x + b*y = gcd(a,b)
: n:xgcd \ a b --  gcd x y
  dup 0 n:= if
    1 swap            \ -- a 1 0
  else
    tuck n:/mod
    -rot recurse
    tuck 4 roll
    n:* n:neg n:+
  then ;

\ Return modular inverse of n modulo mod, or null if it doesn't exist (n and mod
\ not coprime):
: n:invmod \ n mod -- invmod
  dup >r
  n:xgcd rot 1 n:= not if
    2drop null
  else
    drop dup 0 n:< if r@ n:+ then
  then
  rdrop ;

42 2017 n:invmod . cr bye