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.