# IntegerNumberTheoryFunctionsΒΆ

This package provides various number theoretic functions on the integers.

bernoulli: Integer -> Fraction Integer
`bernoulli(n)` returns the `n`th Bernoulli number. this is `B(n, 0)`, where `B(n, x)` is the `n`th Bernoulli polynomial.
carmichaelLambda: Integer -> Integer
`carmichaelLambda(n)` returns exponent of the multiplicative group of integers modulo `n`, that is smallest positive integer `k` such that `i^k rem n = 1` for all `i` relatively prime to `n`.
chineseRemainder: (Integer, Integer, Integer, Integer) -> Integer
`chineseRemainder(x1, m1, x2, m2)` returns `w`, where `w` is such that `w = x1 mod m1` and `w = x2 mod m2`. Note: `m1` and `m2` must be relatively prime.
divisors: Integer -> List Integer
`divisors(n)` returns a list of the divisors of `n`.
euler: Integer -> Integer
`euler(n)` returns the `n`th Euler number. This is `2^n E(n, 1/2)`, where `E(n, x)` is the `n`th Euler polynomial.
eulerPhi: Integer -> Integer
`eulerPhi(n)` returns the number of integers between 1 and `n` (including 1) which are relatively prime to `n`. This is the Euler phi function `phi(n)` is also called the totient function.
fibonacci: Integer -> Integer
`fibonacci(n)` returns the `n`th Fibonacci number, `F[n]`. The Fibonacci numbers are defined by `F[0] = 0`, `F[1] = 1` and `F[n] = F[n-1] + F[n-2]`. The algorithm has running time `O(log(n)^3)`. Reference: Knuth, The Art of Computer Programming Vol 2, Semi-Numerical Algorithms.
harmonic: Integer -> Fraction Integer
`harmonic(n)` returns the `n`th harmonic number. This is `H[n] = sum(1/k, k=1..n)`.
jacobi: (Integer, Integer) -> Integer
`jacobi(a, b)` returns the Jacobi symbol `J(a/b)`. When `b` is odd, `J(a/b) = product(L(a/p) for p in factor b )`. Note: by convention, 0 is returned if `gcd(a, b) ~= 1`. Iterative `O(log(b)^2)` version coded by Michael Monagan June 1987.
legendre: (Integer, Integer) -> Integer
`legendre(a, p)` returns the Legendre symbol `L(a/p)`. `L(a/p) = (-1)^((p-1)/2) mod p` (`p` prime), which is 0 if `a` is 0, 1 if `a` is a quadratic residue `mod p` and `-1` otherwise. Note: because the primality test is expensive, if it is known that `p` is prime then use `jacobi(a, p)`.
moebiusMu: Integer -> Integer
`moebiusMu(n)` returns the Moebius function `mu(n)`. `mu(n)` is either `-1`, 0 or 1 as follows: `mu(n) = 0` if `n` is divisible by a square > 1, `mu(n) = (-1)^k` if `n` is square-free and has `k` distinct prime divisors.
numberOfDivisors: Integer -> Integer
`numberOfDivisors(n)` returns the number of integers between 1 and `n` (inclusive) which divide `n`. The number of divisors of `n` is often denoted by `tau(n)`.
sumOfDivisors: Integer -> Integer
`sumOfDivisors(n)` returns the sum of the integers between 1 and `n` (inclusive) which divide `n`. The sum of the divisors of `n` is often denoted by `sigma(n)`.
sumOfKthPowerDivisors: (Integer, NonNegativeInteger) -> Integer
`sumOfKthPowerDivisors(n, k)` returns the sum of the `k`th powers of the integers between 1 and `n` (inclusive) which divide `n`. the sum of the `k`th powers of the divisors of `n` is often denoted by `sigma_k(n)`.