Number Theory in SageMath

• a % m computes a mod m.
• Primes().unrank(k) returns the kth prime number, starting with 2 at k = 0.
• n in Primes() returns True if n is prime and False otherwise.
• factor(n) computes the prime factorization of n.
• divisors(n) returns a list of all of the positive divisors of n.
• number_of_divisors(n) returns the number of positive divisors of n.
• euler_phi(n) computes φ(n).
• gcd(a, b) computes the greatest common divisor of a and b.
• lcm(a, b) computes the least common multiple of a and b.
• xgcd(a, b) returns (a, m, n), where d is the greatest common divisor of a and b and m and n are integers so that am + bn = d.
• inverse_mod(a, m) computes a⁻¹ mod m.
• a.powermod(b, m) computes a^b mod m.
• crt(r₁, r₂, m₁, m₂) uses the Chinese remainder theorem to compute the smallest non-negative integer n satisfying n ≡ r₁ (mod m₁) and n ≡ r₂ (mod m₂).