number_theory

Number Theory Library

Collection of integer related functions useful in number theory.

boring_math.number_theory.coprime(m: int, n: int, /) → tuple[int, int]

Makes 2 integers coprime by dividing out their common factors.

Parameters:

• m – first int for coprime calculation

• n – second int for coprime calculation

Returns:

coprimed values with original signs, (0, 0) when n = m = 0

boring_math.number_theory.gcd(m: int, n: int, /) → int

Uses Euclidean algorithm to compute the gcd of two integers.

Note

• mathematically the gcd of 0 and 0 does not exist

• taking gcd(0, 0) = 1 is a better choice than math.gcd(0, 0) = 0

  • eliminates lcm & coprime functions having to edge case test

  • also gcd(0, 0) returning 1 instead of 0 more mathematically justified

Parameters:

• m – first int for gcd calculation

• n – second int for gcd calculation

Returns:

gcd of the absolute values of m and n

boring_math.number_theory.iSqrt(n: int, /) → int

Integer square root of a non-negative integer.

Parameters:

n – integer whose integer square root is to be found

Returns:

the unique m such that m*m <= n < (m+1)*(m+1)

Raises:

ValueError – if n < 0

boring_math.number_theory.isSqr(n: int, /) → bool

Determine if argument is a perfect square.

Parameters:

n – integer to check

Returns:

true only if integer argument is a perfect square

boring_math.number_theory.is_prime(n: int, /) → bool

Test if argument is a prime number, uses Wilson’s Theorem.

Parameters:

n – integer to check if prime

Returns:

true only if n is prime

boring_math.number_theory.jacobi_symbol(a: int, n: int) → int

Calculate the Jacobi Symbol (a/n).

Note

See https://en.wikipedia.org/wiki/Jacobi_symbol

Parameters:

• a – any integer

• n – any positive odd integer

Returns:

the Jacobi Symbol (a/p) ∈ {-1, 0, 1}

Raises:

ValueError – if n is not a positive odd integer

boring_math.number_theory.lcm(m: int, n: int, /) → int

Find the least common multiple (lcm) of two integers.

Parameters:

• m – first int for lcm calculation

• n – second int for lcm calculation

Returns:

lcm of the absolute values of m and n

boring_math.number_theory.legendre_symbol(a: int, p: int) → int

Calculate the Legendre Symbol (a/p) where p is an odd prime.

Note

See https://en.wikipedia.org/wiki/Legendre_symbol

Parameters:

• a – any integer

• p – any prime p > 2, does not check that p is actually prime

Returns:

the Legendre Symbol (a/p) ∈ {-1, 0, 1}

Raises:

ValueError – if abs(p) < 3

boring_math.number_theory.primes(start: int = 2, end: int | None = None) → Iterator[int]

Yield all primes p where start <= p <= end.

Warning

If end is not given, returned iterator is infinite.

Parameters:

start – first value to check, defaults to 2

Returns:

an iterator of all primes p where start <= p <= end

boring_math.number_theory.primes_capped(start: int, end: int) → Iterator[int]

Yield all primes `p` where start <= p <= end.

Parameters:

• start – first value to check

• start – last value to check

Returns:

an iterator of all primes p where start <= p <= end.

boring_math.number_theory.primes_wilson(start: int = 2) → Iterator[int]

Prime number generation using Wilson’s Theorem.

Note

Wilson’s Theorem: ∀(n>1), n is prime if and only if (n-1)! % n ≡ -1

Parameters:

start – first value to check, defaults to 2

Returns:

an infinite iterator of prime numbers