# IntegerNumberTheoryFunctionsΒΆ

numtheor.spad line 182 [edit on github]

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.

- 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)`

.