# (chibi math prime)

Prime and number theoretic utilities. Returns a pair whose car is the power of 2 in the factorization of n, and whose cdr is the product of all remaining primes.

#### `(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.

#### `(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 by finding an exception to the Miller Rabin lemma.

#### `(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`.

#### `(factor n)`

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

#### `(totient n)`

Returns the Euler totient function, the number of positive integers less than `n` that are relatively prime to `n`.

#### `(aliquot n)`

The aliquot sum s(n), equal to the sum of proper divisors of an 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`.