Description

Elementary Number Theory

Collection of integer related functions useful in 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