### 5.2 Modular Arithmetic ¶

`(require 'modular)`

Function: extended-euclid n1 n2 ¶

  Returns a list of 3 integers `(d x y)` such that d = gcd(n1, n2) = n1 * x + n2 * y.

Function: symmetric:modulus m ¶

  For odd positive integer m, returns an object suitable for passing as the first argument to `modular:` procedures, directing them to return a symmetric modular number, ie. an n such that

      (<= (quotient m -2) n (quotient m 2)

Function: modular:characteristic modulus ¶

  Returns the non-negative integer characteristic of the ring formed when modulus is used with `modular:` procedures.

Function: modular:normalize modulus n ¶

  Returns the integer `(modulo n (modular:characteristic modulus))` in the representation specified by modulus.

The rest of these functions assume normalized arguments; That is, the arguments are constrained by the following table:

For all of these functions, if the first argument (modulus) is:

`positive?`

  Integers mod modulus. The result is between 0 and modulus.

`zero?`

  The arguments are treated as integers. An integer is returned.

Otherwise, if modulus is a value returned by `(symmetric:modulus radix)`, then the arguments and result are treated as members of the integers modulo radix, but with symmetric representation; i.e.

    (<= (quotient radix 2) n (quotient (- -1 radix) 2)

If all the arguments are fixnums the computation will use only fixnums.

Function: modular:invertable? modulus k ¶

  Returns `#t` if there exists an integer n such that k * n ≡ 1 mod modulus, and `#f` otherwise.

Function: modular:invert modulus n2 ¶

  Returns an integer n such that 1 = (n * n2) mod modulus. If n2 has no inverse mod modulus an error is signaled.

Function: modular:negate modulus n2 ¶

  Returns (−n2) mod modulus.

Function: modular:+ modulus n2 n3 ¶

  Returns (n2 + n3) mod modulus.

Function: modular:- modulus n2 n3 ¶

  Returns (n2 − n3) mod modulus.

Function: modular:* modulus n2 n3 ¶

  Returns (n2 * n3) mod modulus.

  The Scheme code for `modular:*` with negative modulus is not completed for fixnum-only implementations.

Function: modular:expt modulus n2 n3 ¶

  Returns (n2 ^ n3) mod modulus.