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.

Returns the multiplicative inverse of `a`

modulo `b`

.

Returns (remainder (expt a e) m).

Returns true iff n and m are coprime.

Returns true iff `n`

is definitely prime. May take an
impossibly long time for large values.

Returns true if we can show `n`

to be composite by finding an
exception to the Miller Rabin lemma.

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.

Returns true iff `n`

is prime. Uses `provable-prime?`

for small `n`

, falling back on `probable-prime?`

for
large values.

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

Returns the first prime less than or equal to `n`

, or #f if
there are no such primes.

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`

.

Returns the factorization of `n`

as a monotonically
increasing list of primes.

Returns the Euler totient function, the number of positive
integers less than `n`

that are relatively prime to `n`

.

The aliquot sum s(n), equal to the sum of proper divisors of an integer n.

Returns true iff `n`

is a perfect number, i.e. the sum of its
divisors other than itself equals itself.

Returns a random prime between `lo`

, inclusive, and `hi`

,
exclusive.

Variant of `random-prime`

which ensures the result is
distinct from `p`

.

Returns a random integer less than `n`

relatively prime to
`n`

.