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.

`(miller-rabin-composite? n)`

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.

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

Variant of

`random-prime`

which ensures the result is
distinct from

`p`

.

Returns a random integer less than

`n`

relatively prime to

`n`

.