# (chibi math prime)

Prime and number theoretic utilities.

#### `(modular-inverse a b)`

Returns the multiplicative inverse of `a` modulo `b`.

#### `(modular-expt a e m)`

Returns (remainder (expt a e) m).

#### `(coprime? n m)`

Returns true iff n and m are coprime.

#### `coprime?`

#### `(provable-prime? n)`

Returns true iff `n` is definitely prime. May take an impossibly long time for large values.

#### `(miller-rabin-composite? n)`

Returns true if we can show `n` to be composite using the Miller-Rabin test (i.e., finding a witness `a` where `a`^(`n`-1)≠1 mod `n` or `a` reveals the existence of a 3rd square root of 1 in Z/(n))

#### `(probable-prime? n)`

Returns true if `n` has a very high probability (enough that you can assume a false positive will never occur in your lifetime) of being prime.

#### `(prime? n)`

Returns true iff `n` is prime. Uses `provable-prime?` for small `n`, falling back on `probable-prime?` for large values.

#### `(nth-prime i)`

Returns the nth prime, with 2 being the 0th prime.

#### `(prime-below n)`

Returns the first prime less than or equal to `n`, or #f if there are no such primes.

#### `(prime-above n [limit])`

Returns the first prime greater than or equal to `n`. If the optional `limit` is given and not false, returns `#f` if no such primes exist below `limit`.

#### `(make-factorizer r1 put [put2 put-1])`

#### `(factor-alist n)`

Returns the factorization of `n` as a list of elements of the form `(`p` . `k`)`, where `p` is a prime factor and `k` is its multiplicity.

#### `(factor n)`

Returns the factorization of `n` as a monotonically increasing list of primes.

#### `factor`

The Euler totient φ(`n`) is the number of positive integers less than or equal to `n` that are relatively prime to `n`.

#### `(aliquot n)`

The aliquot sum s(`n`) is the sum of proper divisors of a positive integer `n`.

#### `(perfect? n)`

Returns true iff `n` is a perfect number, i.e. the sum of its divisors other than itself equals itself.

#### `(random-prime lo hi)`

Returns a random prime between `lo`, inclusive, and `hi`, exclusive.

#### `(random-prime-distinct-from lo hi p)`

Variant of `random-prime` which ensures the result is distinct from `p`.

#### `(random-coprime n)`

Returns a random integer less than `n` relatively prime to `n`.