Number Theory in Mathematica

• Mod[a, m] computes a mod m.
• Prime[k] returns the kth prime number.
• PrimeQ[n] returns True if n is prime and False otherwise.
• FactorInteger[n] computes the prime factorization of n.
• Divisible[n, k] returns True if n is divisible by k, and False otherwise.
• Divisors[n] returns a list of all of the positive divisors of n.
• DivisorSigma[0, n] returns the number of positive divisors of n.
• EulerPhi[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.
• ExtendedGCD[a, b] returns {d,{m, n}}, where d is the greatest common divisor of a and b and m and n are integers so that am + bn = d.
• PowerMod[a, b, m] computes a^b mod m. (If b = −1, this returns the inverse of a modulo m.)
• ChineseRemainder[{r₁, r₂},{m₁, m₂}] computes the smallest non-negative integer n satisfying n ≡ r₁ (mod m₁) and n ≡ r₂ (mod m₂).