Description

Number Theory Library

Collection of integer related functions for number theory.

• elementary functions

  • gcd(m, n)- find greatest common denominator of m and n

  • lcm(m, n)- find least common multiple of m and n

  • coprime(m, n)- return tuple without common factors, preserve signs

  • iSqrt(n)- find unique m such that m*m <= n < (m+1)*(m+1)

  • isSqr(n)- true if n is a perfect square

• symbols

  • legendre_symbol(a, p)- Legendre symbol (a/p) ∈ {-1, 0, 1} where p odd prime

  • jacobi_symbol(a, n)- Jacobi symbol (a/n) ∈ {-1, 0, 1} where n positive odd integer

• prime functions & generators

  • is_prime(n)- true if n is a prime number

  • primes(n, m)- generate primes n <= p <= m where m is optional