View source for Modular inverse

===Using Extended Euclidean Algorithm===

Handles negative args. Returns -1 for non-coprime args.

<syntaxhighlight lang="quackery">  [ dup 0 = iff
      [ 2drop 1 0 ]
      done
    dup unrot /mod
    dip swap recurse
    tuck 2swap *
    dip swap - ]        is egcd    ( n n --> n n )

  [ dup 0 < if negate
    over 0 < if
      [ swap negate
        over tuck mod
        - swap ]
    dup rot 2dup egcd
    2swap 2over rot *
    unrot * + 1 != iff
      [ drop 2drop -1 ]
      done
    nip swap mod ]      is modinv ( n n --> n   )

say "  42 2017 modinv --> "   42 2017 modinv echo cr ( --> 1969 )
say "  40    1 modinv --> "   40    1 modinv echo cr ( --> 0    )
say "  52 -217 modinv --> "   52 -217 modinv echo cr ( --> 96   )
say "-486  217 modinv --> " -486  217 modinv echo cr ( --> 121  )
say "  40 2018 modinv --> "   40 2018 modinv echo cr ( --> -1   )</syntaxhighlight>

{{out}}

<pre>  42 2017 modinv --> 1969
  40    1 modinv --> 0
  52 -217 modinv --> 96
-486  217 modinv --> 121
  40 2018 modinv --> -1
</pre>