# Number Theory
The functions in this section provide tools for number-theoretic computations:
prime numbers and integer factorization, divisor functions, partitions, polygonal numbers, perfect/happy numbers, and special combinatorial counts (Eulerian, Stirling).
## Function Definitions
n: integer
Returns Euler’s totient function $φ(n)$: the number of integers $1 ≤ k ≤ n$ that are coprime to $n$.
This function counts how many integers up to $n$ share no common factors with $n$ other than 1. For example, for $n=9$, the integers coprime to 9 are 1, 2, 4, 5, 7, and 8, so $φ(9) = 6$.
See also: [Euler's totient function - Wikipedia](https://en.wikipedia.org/wiki/Euler%27s_totient_function)
```json
["Totient", 9]
// ➔ 6
```
n: integer
Returns the number of positive divisors of $n$.
This function counts how many positive integers divide $n$ without a remainder. For example, for $n=6$, the divisors are 1, 2, 3, and 6, so the count is 4.
See also: [Divisor function - Wikipedia](https://en.wikipedia.org/wiki/Divisor_function)
```json
["Sigma0", 6]
// ➔ 4
```
n: integer
Returns the sum of positive divisors of $n$.
This function sums all positive divisors of $n$. For example, for $n=6$, the divisors are 1, 2, 3, and 6, and their sum is 12.
See also: [Divisor function - Wikipedia](https://en.wikipedia.org/wiki/Divisor_function)
```json
["Sigma1", 6]
// ➔ 12
```
n: integer
Returns the sum of reciprocals of the positive divisors of $n$.
This function sums the reciprocals of all positive divisors of $n$. For example, for $n=6$, the divisors are 1, 2, 3, and 6, and the sum of reciprocals is 1 + 1/2 + 1/3 + 1/6 = 2.333...
See also: [Divisor function - Wikipedia](https://en.wikipedia.org/wiki/Divisor_function)
```json
["SigmaMinus1", 6]
// ➔ 2.333...
```
n: integer
Returns the $n$th prime number (1-based): `NthPrime(1)` is 2, `NthPrime(2)` is 3, and so on.
For example, the 10th prime number is 29.
The function is named `NthPrime` rather than `Prime` because `Prime` denotes derivative notation (such as $f'$) in the Compute Engine. `PrimeNumber` is accepted as an alias and canonicalizes to `NthPrime`.
See also: [Prime number - Wikipedia](https://en.wikipedia.org/wiki/Prime_number)
```json
["NthPrime", 10]
// ➔ 29
```
n: integern: integer, k: integer
Returns the smallest prime number greater than $n$.
With a second argument $k$, returns the $k$th prime after $n$. A negative $k$ returns the $|k|$th prime before $n$, so `NextPrime(n, -1)` is the largest prime less than $n$.
See also: [Prime number - Wikipedia](https://en.wikipedia.org/wiki/Prime_number)
```json
["NextPrime", 10]
// ➔ 11
["NextPrime", 10, 3]
// ➔ 17
["NextPrime", 10, -1]
// ➔ 7
```
n: integer
Returns the prime factorization of $n$ as a list of `[prime, exponent]` tuples, ordered by ascending prime.
For example, $360 = 2^3 \times 3^2 \times 5$, so the factorization is the list of tuples $(2, 3)$, $(3, 2)$, and $(5, 1)$. The sign of a negative $n$ is carried in a leading $(-1, 1)$ tuple.
See also: [Integer factorization - Wikipedia](https://en.wikipedia.org/wiki/Integer_factorization)
```json
["FactorInteger", 360]
// ➔ [(2, 3), (3, 2), (5, 1)]
```
n: integer
Returns the sorted list of positive divisors of $n$.
For example, the divisors of 12 are 1, 2, 3, 4, 6, and 12. The sign of $n$ is ignored; `Divisors(0)` is left unevaluated since 0 has infinitely many divisors.
See also: [Divisor - Wikipedia](https://en.wikipedia.org/wiki/Divisor)
```json
["Divisors", 12]
// ➔ [1, 2, 3, 4, 6, 12]
```
a: integer, b: integer
Returns `"True"` if $a$ divides $b$ — that is, if $b$ is an integer multiple of $a$ — corresponding to the notation $a \mid b$. By convention every integer divides 0, and only 0 divides 0.
The operands are accepted as `number` (not `integer`), so a symbolic operand keeps the relation unevaluated: `Divides(a, b)` stays symbolic until both operands are concrete integers.
In LaTeX, $a \mid b$ parses to `Divides` and the negated form $a \nmid b$ parses to `Not(Divides(a, b))` (also available directly as `NotDivides`).
```json
["Divides", 3, 12]
// ➔ "True"
["Divides", 4, 10]
// ➔ "False"
["NotDivides", 4, 10]
// ➔ "True"
```
Modular **congruence** is written $a \equiv b \pmod{n}$, which parses to `Congruent(a, b, n)` and evaluates to `"True"` when $a$ and $b$ leave the same remainder modulo $n$. Like `Divides`, the relation stays symbolic until all three operands are concrete integers.
```json
["Congruent", 7, 1, 3]
// ➔ "True"
```
Note that `\bmod` is the binary modulo operator ($a \bmod n$ parses to `Mod(a, n)`), distinct from the `\pmod{n}` congruence annotation. The `Congruent` operator is described in the [Arithmetic reference](/compute-engine/reference/arithmetic/#Congruent).
### Reduction of Large Integers
`Mod` and `Congruent` reduce integer-valued expressions in $ℤ/mℤ$ **without materializing** the (potentially astronomically large) intermediate value. Modular exponentiation, sums, products, negations, and factorial reduction are all handled, so an expression that would otherwise require a multi-million-digit integer reduces directly:
```javascript
ce.parse('2^{3^{20}} \\pmod{100}').evaluate();
// ➔ 52
ce.parse('2^{3^{20}} \\equiv 52 \\pmod{100}').evaluate();
// ➔ "True"
ce.parse('2 \\cdot 3^{5000000} \\pmod 7').evaluate();
// ➔ 4
```
The floored-sign convention of `Mod` (the result follows the sign of the divisor) is preserved on this path.
### Solving Congruences
Passing a **linear congruence** to `solve` returns the parametric residue family with a fresh integer parameter $t ∈ ℤ$; an unsolvable congruence returns an empty result, and a gcd-divisible congruence is reduced:
```javascript
ce.parse('6n \\equiv 4 \\pmod 7').solve('n');
// ➔ [7t + 3]
ce.parse('2x \\equiv 1 \\pmod 4').solve('x');
// ➔ [] (no solution)
ce.parse('4x \\equiv 2 \\pmod 6').solve('x');
// ➔ [3t + 2]
```
A **system of simultaneous congruences** in one unknown (an `And` of congruences) is combined via the Chinese Remainder Theorem — including non-coprime moduli — into a single family. An inconsistent system reports no solution.
```javascript
const sol = ce.box(['And',
['Congruent', 'x', 2, 3],
['Congruent', 'x', 3, 5],
['Congruent', 'x', 2, 7]
]).solve('x');
// ➔ { x: 105t + 23 }
```
For a direct CRT computation from lists of residues and moduli, see [`ChineseRemainder`](#ChineseRemainder).
n: integer
Returns the sorted list of distinct prime factors of $n$.
The sign of $n$ is ignored; `PrimeFactors(1)` is the empty list.
```json
["PrimeFactors", 360]
// ➔ [2, 3, 5]
```
n: integer
Returns the radical of $n$ (its square-free kernel): the product of its distinct prime factors.
```json
["Radical", 360]
// ➔ 30
```
n: integer
Returns $ω(n)$, the number of **distinct** prime factors of $n$.
See also: [Prime omega function - Wikipedia](https://en.wikipedia.org/wiki/Prime_omega_function)
```json
["PrimeNu", 360]
// ➔ 3
```
n: integer
Returns $Ω(n)$, the number of prime factors of $n$ counted **with multiplicity**.
See also: [Prime omega function - Wikipedia](https://en.wikipedia.org/wiki/Prime_omega_function)
```json
["PrimeOmega", 360]
// ➔ 6
```
n: integer
Returns the Möbius function $μ(n)$: 0 if $n$ is divisible by a perfect square greater than 1, otherwise $(-1)^k$ where $k$ is the number of distinct prime factors.
See also: [Möbius function - Wikipedia](https://en.wikipedia.org/wiki/M%C3%B6bius_function)
```json
["MoebiusMu", 30]
// ➔ -1
```
n: integer
Returns `"True"` if $n$ is square-free, i.e. not divisible by any perfect square greater than 1.
```json
["IsSquareFree", 30]
// ➔ "True"
```
n: integer
Returns `"True"` if $n$ is a perfect power $a^b$ for integers $a$ and $b ≥ 2$. A negative $n$ requires an odd exponent; the smallest perfect power is 4.
See also: [Perfect power - Wikipedia](https://en.wikipedia.org/wiki/Perfect_power)
```json
["IsPerfectPower", 64]
// ➔ "True"
```
n: real
Returns $π(n)$, the prime-counting function: the number of primes less than or equal to $n$.
See also: [Prime-counting function - Wikipedia](https://en.wikipedia.org/wiki/Prime-counting_function)
```json
["PrimePi", 10]
// ➔ 4
```
n: integerm: integer, n: integer
Returns a random prime. `RandomPrime(n)` draws a prime in the interval $[2, n]$; `RandomPrime(m, n)` draws a prime in $[m, n]$. Undefined if the range contains no prime.
```json
["RandomPrime", 100]
// ➔ 47 (for example)
```
a: integer, b: integer, m: integer
Returns $a^b \bmod m$ (modular exponentiation), in the range $[0, m)$.
A negative exponent $b$ uses the modular inverse of $a$; the result is undefined when that inverse does not exist (i.e. when $a$ and $m$ are not coprime).
See also: [Modular exponentiation - Wikipedia](https://en.wikipedia.org/wiki/Modular_exponentiation)
```json
["PowerMod", 2, 10, 1000]
// ➔ 24
```
a: integer, m: integer
Returns the modular multiplicative inverse of $a$ modulo $m$: the integer $x$ in $[0, m)$ with $a·x ≡ 1 \pmod m$.
The inverse exists only when $a$ and $m$ are coprime; otherwise the expression stays symbolic.
See also: [Modular multiplicative inverse - Wikipedia](https://en.wikipedia.org/wiki/Modular_multiplicative_inverse)
```json
["ModularInverse", 3, 7]
// ➔ 5
["ModularInverse", 4, 6]
// ➔ ["ModularInverse", 4, 6] (4 and 6 are not coprime)
```
a: integer, b: integer
Returns the extended GCD of $a$ and $b$ as a tuple $(g, x, y)$, where $g = \gcd(a, b)$ is non-negative and $a·x + b·y = g$ (the Bézout coefficients).
See also: [Extended Euclidean algorithm - Wikipedia](https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm)
```json
["ExtendedGCD", 12, 18]
// ➔ (6, -1, 1)
```
residues: collection, moduli: collection
Returns the smallest non-negative integer $x$ such that $x ≡ \mathrm{residues}_i \pmod{\mathrm{moduli}_i}$ for every $i$. The moduli need not be coprime. Undefined if the system is inconsistent or the two lists differ in length.
See also: [Chinese remainder theorem - Wikipedia](https://en.wikipedia.org/wiki/Chinese_remainder_theorem)
```json
["ChineseRemainder", [2, 3, 2], [3, 5, 7]]
// ➔ 23
```
n: integer
Returns the integer square root of $n$: the largest integer $m$ such that $m^2 ≤ n$. Undefined for negative $n$.
See also: [Integer square root - Wikipedia](https://en.wikipedia.org/wiki/Integer_square_root)
```json
["IntegerSqrt", 17]
// ➔ 4
```
n: integer
Returns the Carmichael function $λ(n)$ (the reduced totient): the smallest positive integer $m$ such that $a^m ≡ 1 \pmod n$ for every $a$ coprime to $n$. Defined for $n ≥ 1$.
See also: [Carmichael function - Wikipedia](https://en.wikipedia.org/wiki/Carmichael_function)
```json
["CarmichaelLambda", 15]
// ➔ 4
```
n: integer
Returns the $n$th Lucas number: `LucasL(0)` is 2, `LucasL(1)` is 1, and $L_n = L_{n-1} + L_{n-2}$. Negative indices follow $L_{-n} = (-1)^n L_n$.
See also: [Lucas number - Wikipedia](https://en.wikipedia.org/wiki/Lucas_number)
```json
["LucasL", 10]
// ➔ 123
```
n: integer
Returns the $n$th Catalan number $C_n = \frac{(2n)!}{(n+1)!\,n!}$: 1, 1, 2, 5, 14, 42, … Defined for $n ≥ 0$.
See also: [Catalan number - Wikipedia](https://en.wikipedia.org/wiki/Catalan_number)
```json
["CatalanNumber", 5]
// ➔ 42
```
n: integer
Returns the $n$th Bernoulli number $B_n$ as an exact rational, using the convention $B_1 = -\frac{1}{2}$. Odd $n > 1$ give 0.
See also: [Bernoulli number - Wikipedia](https://en.wikipedia.org/wiki/Bernoulli_number)
```json
["BernoulliB", 12]
// ➔ -691/2730
```
x: numberx: number, n: integer
Returns the continued-fraction expansion of $x$ as a list of integer terms $[a_0, a_1, …]$.
An exact rational is expanded fully. For an inexact value the expansion is truncated to the optional $n$ terms (default 20); note that floating-point round-off can introduce spurious large terms in the tail.
See also: [Continued fraction - Wikipedia](https://en.wikipedia.org/wiki/Continued_fraction)
```json
["ContinuedFraction", ["Rational", 43, 19]]
// ➔ [2, 3, 1, 4]
```
terms: collection
Reconstructs the (rational) value of a continued fraction from its list of integer terms $[a_0, a_1, …]$.
```json
["FromContinuedFraction", [2, 3, 1, 4]]
// ➔ 43/19
```
n: integern: integer, base: integern: integer, base: integer, length: integer
Returns the digits of $n$ in the given `base` (default 10), most-significant first. The sign of $n$ is ignored.
With a third argument `length`, the result is zero-padded on the left (or truncated to its least-significant digits) to that length.
```json
["IntegerDigits", 255, 16]
// ➔ [15, 15]
```
n: integer, base: integern: integer, base: integer, digit: integer
Counts digits of $n$ in the given `base` (default 10); the sign of $n$ is ignored.
With a third argument `digit`, returns how many times that digit occurs. Otherwise returns a list `[count of 1, count of 2, …, count of base-1, count of 0]`.
```json
["DigitCount", 122, 10, 2]
// ➔ 2
```
digits: collectiondigits: collection, base: integer
Reconstructs an integer from its list of digits (most-significant first) in the given `base` (default 10). The inverse of `IntegerDigits`.
Digits outside $[0, base)$ are combined positionally (Horner evaluation), so `FromDigits` is well-defined for any integer terms.
```json
["FromDigits", [1, 2, 3, 4]]
// ➔ 1234
```
n: integern: integer, base: integer
Returns the sum of the digits of $n$ in the given `base` (default 10). The sign of $n$ is ignored.
```json
["DigitSum", 1234]
// ➔ 10
```
k: integer, n: integer
Returns the divisor function $σ_k(n) = \sum_{d \mid n} d^k$ over the positive divisors of $n$. $σ_0$ counts divisors (like `Sigma0`) and $σ_1$ sums them (like `Sigma1`). Defined for $n ≥ 1$.
See also: [Divisor function - Wikipedia](https://en.wikipedia.org/wiki/Divisor_function)
```json
["DivisorSigma", 2, 6]
// ➔ 50
```
a: integer, n: integer
Returns the Jacobi symbol $\left(\frac{a}{n}\right)$ for an odd $n > 0$, with value -1, 0, or 1. Undefined when $n$ is even or non-positive.
See also: [Jacobi symbol - Wikipedia](https://en.wikipedia.org/wiki/Jacobi_symbol)
```json
["JacobiSymbol", 5, 21]
// ➔ 1
```
a: integer, p: integer
Returns the Legendre symbol $\left(\frac{a}{p}\right)$ for an odd prime $p$, with value -1, 0, or 1. Undefined when $p$ is not an odd prime.
See also: [Legendre symbol - Wikipedia](https://en.wikipedia.org/wiki/Legendre_symbol)
```json
["LegendreSymbol", 3, 7]
// ➔ -1
```
a: integer, n: integer
Returns the multiplicative order of $a$ modulo $n$: the smallest $k > 0$ such that $a^k ≡ 1 \pmod n$. Undefined unless $a$ and $n$ are coprime.
See also: [Multiplicative order - Wikipedia](https://en.wikipedia.org/wiki/Multiplicative_order)
```json
["MultiplicativeOrder", 2, 7]
// ➔ 3
```
n: integer
Returns the smallest primitive root modulo $n$ (a generator of the multiplicative group of integers mod $n$), or undefined if none exists — which happens unless $n$ is 1, 2, 4, $p^k$, or $2p^k$ for an odd prime $p$.
See also: [Primitive root modulo n - Wikipedia](https://en.wikipedia.org/wiki/Primitive_root_modulo_n)
```json
["PrimitiveRoot", 7]
// ➔ 3
```
n: integer, m: integer
Returns the Eulerian number A(n, m), counting permutations of `{1..n}` with exactly m ascents.
Eulerian numbers count the permutations of the numbers 1 through $n$ that have exactly $m$ ascents (positions where the next number is greater than the previous one). For example, for $n=4$ and $m=2$, there are 11 such permutations.
See also: [Eulerian number - Wikipedia](https://en.wikipedia.org/wiki/Eulerian_number)
```json
["Eulerian", 4, 2]
// ➔ 11
```
n: integer, m: integer
Returns the Stirling number of the second kind $S(n, m)$, counting the number of ways to partition $n$ elements into $m$ non-empty subsets.
Stirling numbers of the second kind count how many ways to split a set of $n$ objects into $m$ groups, none empty. For example, with $n=5$ and $m=2$, there are 15 ways.
See also: [Stirling number of the second kind - Wikipedia](https://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind)
```json
["Stirling", 5, 2]
// ➔ 15
```
n: integer
Returns the number of integer partitions of $n$.
This function counts how many ways $n$ can be expressed as a sum of positive integers, disregarding order. For example, 5 can be partitioned into 7 distinct sums: 5, 4+1, 3+2, 3+1+1, 2+2+1, 2+1+1+1, and 1+1+1+1+1.
See also: [Partition function (number theory) - Wikipedia](https://en.wikipedia.org/wiki/Partition_(number_theory))
```json
["NPartition", 5]
// ➔ 7
```
n: integer
Returns `"True"` if $n$ is a triangular number.
Triangular numbers count objects arranged in an equilateral triangle. The $k$th triangular number is $k(k+1)/2$. For example, 15 is triangular because $5 \times 6 / 2 = 15$.
See also: [Triangular number - Wikipedia](https://en.wikipedia.org/wiki/Triangular_number)
```json
["IsTriangular", 15]
// ➔ "True"
```
n: integer
Returns `"True"` if $n$ is a perfect square.
A perfect square is an integer that is the square of another integer. For example, 16 is a perfect square since $4^2 = 16$.
See also: [Square number - Wikipedia](https://en.wikipedia.org/wiki/Square_number)
```json
["IsSquare", 16]
// ➔ "True"
```
n: integer
Returns `"True"` if $n$ is a pentagonal number.
Pentagonal numbers represent dots forming a pentagon. The $k$th pentagonal number is given by $k(3k-1)/2$. For example, 22 is pentagonal because it matches the formula for some integer $k$.
See also: [Pentagonal number - Wikipedia](https://en.wikipedia.org/wiki/Pentagonal_number)
```json
["IsPentagonal", 22]
// ➔ "True"
```
n: integer
Returns `"True"` if $n$ is an octahedral number.
Octahedral numbers count objects arranged in an octahedron shape. The $k$th octahedral number is given by $k(2k^2 + 1)/3$. For example, 19 is not octahedral.
See also: [Octahedral number - Wikipedia](https://en.wikipedia.org/wiki/Octahedral_number)
```json
["IsOctahedral", 19]
// ➔ "False"
```
n: integer
Returns `"True"` if $n$ is a centered square number.
Centered square numbers count dots arranged in a square with a dot in the center. The $k$th centered square number is $(2k+1)^2$. For example, 25 is centered square as it equals $5^2$.
See also: [Centered square number - OEIS A001844](https://oeis.org/A001844)
```json
["IsCenteredSquare", 25]
// ➔ "True"
```
n: integer
Returns `"True"` if $n$ is a perfect number.
A perfect number is one that equals the sum of its positive divisors excluding itself. For example, 28 is perfect since 1 + 2 + 4 + 7 + 14 = 28.
See also: [Perfect number - Wikipedia](https://en.wikipedia.org/wiki/Perfect_number)
```json
["IsPerfect", 28]
// ➔ "True"
```
n: integer
Returns `"True"` if $n$ is a happy number.
A happy number is defined by iterating the sum of the squares of its digits; if this process eventually reaches 1, the number is happy. For example, 19 is happy because: 1²+9²=82; 8²+2²=68; 6²+8²=100; 1²+0²+0²=1.
See also: [Happy number - Wikipedia](https://en.wikipedia.org/wiki/Happy_number)
```json
["IsHappy", 19]
// ➔ "True"
```
n: integer
Returns `"True"` if $n$ is an abundant number.
An abundant number is one where the sum of its proper divisors exceeds the number itself. For example, 12 is abundant since 1 + 2 + 3 + 4 + 6 = 16 > 12.
See also: [Abundant number - Wikipedia](https://en.wikipedia.org/wiki/Abundant_number)
```json
["IsAbundant", 12]
```