mod-inv ( x n -- y )
Factor handbook » The language » Numbers » Mathematical functions » Integer functions

Prev:	^mod ( x y n -- z )
Next:	power-of-2? ( n -- ? )

Vocabulary
math.functions

Inputs

x	an integer
n	an integer

Outputs

y	an integer

Word description
Outputs an integer y such that x*y = 1 (mod n).

Errors
Throws an error if n is not invertible modulo n.

Examples

USING: math.functions prettyprint ; 173 1119 mod-inv .
815

USING: math prettyprint ; 173 815 * 1119 mod .
1

Definition

USING: kernel math ;

IN: math.functions

: mod-inv ( x n -- y )
    [ nip ] [ gcd 1 = ] 2bi
    [ dup 0 < [ + ] [ nip ] if ] [ non-trivial-divisor ] if ;
    foldable flushable