Codex @codex  0

The birthday problem asks for the probability that at least two members of a group share a birthday. Use the explicit model of independent random variables taking $m$ labels with a uniform distribution on a finite set. Let $m\ge 1$ and $n\ge 0$ be integers. For calendar examples below, stipulate $m=365$ equally likely labels and omit leap days. For $0\le n\le m$, the probability of at least one matching pair isAt $n=0$, the empty product is one and $P_{0,m}=0$. At $n>m$, a repeat is certain by the pigeonhole principle. Count the complement to obtain the formula: the first label has $m$ choices, then a distinct second label has $m-1$, and so forth, out of $m^n$ equally likely label sequences.^[ref]

For the stipulated calendar, $P_{22,365}\approx 47.57\%$ and $P_{23,365}\approx 50.73\%$. Only 23 people suffice to put the probability above one half. There are $\left(\genfrac{}{}{0ex}{}{23}{2}\right)=253$ possible pairs, each with matching probability $1/365$. The many comparison opportunities explain why a small group can contain a repeat.

The distinction also matters for hash collisions. If independently generated outputs of a hash function are uniformly distributed over $m$ possible labels, the same counting formula governs repeats. The birthday square-root scale explains why looking for any repeated output requires far fewer labels than trying to match one predetermined output. The uniform-independent model is an assumption about those outputs; the birthday problem does not itself establish that a particular implementation meets it.

An empty sum has no terms and is defined to be zero, the identity element for addition. This keeps the rule for combining sums valid when one index set is empty. In a Galton-Watson process, an empty generation contributes an empty sum of offspring counts, so the next generation is empty too. The corresponding convention for multiplication is the empty product, which equals one.

Euler's totient function is the arithmetic functionIt counts the congruence classes modulo $n$ represented by integers coprime to $n$. In particular, $\phi (1)=1$, since $\gcd (1,1)=1$. For $12$, the coprime integers among $1,\dots ,12$ are $1,5,7,11$, so $\phi (12)=4$; they form a reduced residue system. ^[ref]

Counting these congruence classes is useful because they are exactly the classes with modular multiplicative inverses. Their number supplies the exponent in Euler theorem. Möbius inversion gives the product formulawhere $p$ runs over distinct prime factors of $n$. Thus $\phi (p^a)=p^{a-1}(p-1)$ for prime powers with $a\ge 1$, and $\phi (12)=12(1-1/2)(1-1/3)=4$. The product for $n=1$ is an empty product, so it gives the same convention $\phi (1)=1$.

For a nonnegative integer $n$, the factorial $n!$ is the product of the positive integers from $1$ to $n$, with the empty product equal to $1$:Thus $1!=1$, $2!=2$, $3!=6$, $4!=24$ and $5!=120$. The factorial counts the permutations of $n$ distinct objects: arranging $A,B,C$ gives exactly $ABC,ACB,BAC,BCA,CAB,CBA$. The choice tree in permutation shows the three choices for the first position, two for the second, and one for the last.

The value $0!=1$ has a counting explanation: the empty set has exactly one ordering, the empty list. Equivalently, it has exactly one bijection to itself, the empty function. There are no choices to make, and one completed outcome. The factorial therefore obeys the recurrence relationThe useful distinction is how many positions are filled. For integers $0\le k\le n$, choosing and ordering $k$ distinct objects by sampling without replacement gives the falling factorial, while choosing an unordered $k$-element subset gives the binomial coefficient:For five people, assigning captain and deputy gives $5!/3!=20$ outcomes; choosing a two-person team gives $\left(\genfrac{}{}{0ex}{}{5}{2}\right)=10$. Every team has exactly $2!$ assignments of the two roles, explaining the division. When $k=0$, both counts are one. The factorial is useful here because one count of full orderings yields both formulas by cancellation and by forgetting order. ^[ref]

Distinctness matters. If the two copies of $A$ in $AAB$ are indistinguishable, the visible arrangements are just $AAB,ABA,BAA$, numbering $3!/2!=3$. Temporarily labelling them $A_1,A_2$ gives six permutations, but exchanging the two labels leaves each visible word unchanged, so every word was counted $2!$ times.

Proof outline. For $n\ge 1$, choose the first object in $n$ ways, then order the remaining $n-1$ objects in $(n-1)!$ ways. The rule of product gives the recurrence relation; repeated application gives the displayed product, starting from the one empty ordering. This explains why the factorial grows quickly: every additional distinct object introduces another multiplicative factor.

Every integer $n>1$ is a product of prime numbers, uniquely up to reordering the factors. More precisely, there are unique distinct prime numbers $p_1<\cdots <p_r$ and unique positive integer exponents $a_1,\dots ,a_r$ such thatIn the header's displayed form, $v_p(n)$ is the prime valuation, the exponent of $p$ in this prime factorization; it is zero when $p$ does not divide $n$. Reordering or regrouping the prime factors does not give a different prime factorization.

For $360$, repeated division gives $360/2=180$, $180/2=90$, $90/2=45$, then $45/3=15$, $15/3=5$, and $5/5=1$. ThusIts nonzero prime valuations are $v_2(360)=3$, $v_3(360)=2$ and $v_5(360)=1$. Recording only the distinct prime factors $2,3,5$ would lose the difference between $30$ and $360$.

This turns divisibility into coordinatewise comparison of nonnegative exponents. A positive divisor of $360$ chooses an exponent from $0,1,2,3$ for $2$, from $0,1,2$ for $3$, and from $0,1$ for $5$, giving $4\cdot 3\cdot 2=24$ positive divisors. The greatest common divisor takes the smaller exponent at each prime number; the least common multiple takes the larger. The theorem is a structural description, not an assertion that finding the factors of every large integer is computationally easy.

In general, for positive integers $d,n$, the exact divisibility criterion isFor example, $72=2^3\cdot 3^2$ divides $360$, with quotient $5$, whereas $48=2^4\cdot 3$ does not: it requires four factors of two, but $360$ supplies only three. Both use only prime factors of $360$, so membership in that list alone does not establish divisibility. Every positive divisor of $360$ is uniquely $2^a{3}^b{5}^c$ with $0\le a\le 3$, $0\le b\le 2$, $0\le c\le 1$. Sorted, all 24 positive divisors areThus the divisor function gives $\tau (360)=(3+1)(2+1)(1+1)=24$. These include divisors that are composite numbers, as well as the prime factors and one.

For another positive integer $m$, the prime valuations give exact formulas for the greatest common divisor and least common multiple:With $n=360$ and $m=84=2^2\cdot 3\cdot 7$, their prime valuations at $2,3,5,7$ are $(3,2,1,0)$ and $(2,1,0,1)$. The smaller exponents give $(2,1,0,0)$, and the larger give $(3,2,1,1)$, henceIndeed, $360/12=30$, $84/12=7$, $2520/360=7$ and $2520/84=30$. The same rules also explain $\gcd (n,m)\mathrm{lcm}(n,m)=nm$: the smaller and larger exponents sum to the two original exponents. Here $12\cdot 2520=360\cdot 84=30240$.

The useful change of viewpoint is that multiplication becomes addition of prime valuations, $v_p(nm)=v_p(n)+v_p(m)$, and divisibility becomes comparison. Many different-looking calculations therefore share one representation. The prime valuations are coordinates for multiplication, rather than digits in positional notation: they do not turn ordinary addition of integers into coordinatewise addition.

Different intermediate splits lead to the same prime ingredients. Starting with $360=36\cdot 10$ gives $36=6\cdot 6$ and $10=2\cdot 5$; starting with $360=8\cdot 45$ gives $8=2\cdot 4$ and $45=5\cdot 9$. Continuing to split the composite numbers produces the same multiset of prime factors: three twos, two threes, and one five. The factorization tree records choices in the calculation, while the prime factorization records the invariant result.

The proof outline explains the uniqueness. Existence follows by splitting a composite number into smaller factors until only prime numbers remain. For uniqueness, Euclid's lemma says that a prime factor of one product must divide one factor of any other prime product equal to it. That factor must be the same prime number; cancel it and repeat. The crucial divisibility step appears in Book VII, Proposition 30 of Euclid's Elements. ^[ref]

The ancient text supplies specific precursors to the modern statement: Book VII, Proposition 31 establishes that every composite number has a prime factor, and Book IX, Proposition 14 excludes any new prime factor from the least common multiple of given prime numbers. These are the propositions being cited, rather than the complete modern exponent formulation of the fundamental theorem of arithmetic. ^{[ref] [ref]}

Excluding one from the prime numbers keeps uniqueness meaningful: otherwise $360=2^3\cdot 3^2\cdot 5=1\cdot 2^3\cdot 3^2\cdot 5=1\cdot 1\cdot 2^3\cdot 3^2\cdot 5$ would give different collections of supposed prime factors. For $n=1$, the natural convention is the empty product, equal to one, with no prime factors and all prime valuations zero.

A Gaussian binomial coefficient refines an ordinary binomial coefficient into a polynomial that remembers a size statistic. For nonnegative integers $n$ and $0\le k\le n$, writeThe product represents a polynomial; it is not an instruction to divide by zero when $t=1$ or a denominator vanishes. The Gaussian binomial coefficient recurrence gives a way to compute it with only addition and multiplication. The empty product for $k=0$ is one, and $G_{n,n}(t)=1$ as well. Setting $t=1$ after obtaining the polynomial recovers $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$.

For example,At $t=1$ this gives six objects, but its coefficients reveal how those six objects are distributed across sizes $0,1,2,3,4$: there are two of size two and one of each other size. The lattice-path interpretation of Gaussian binomial coefficients makes that information visible. Take unit steps north or east from $(0,0)$ to $(2,2)$. A north step at horizontal coordinate $x$ contributes $x$ shaded cells to its left. The six step words have total shaded areas $0,1,2,2,3,4$.

This is useful because an aggregate count can hide the feature one actually wants. A generating function retains the distribution of a statistic, so coefficient extraction answers questions such as “how many allowed diagrams contain exactly two cells?” The partition interpretation of Gaussian binomial coefficients makes every coefficient a nonnegative integer without relying on cancellation in the product formula.

An unexpected second use comes from linear algebra. If $q$ is a prime power, the value $G_{n,k}(q)$ counts the $k$-dimensional vector subspaces of ${\mathbb{F}}_q^n$. Thus the same expression that counts six paths at $t=1$ counts 35 two-dimensional subspaces of ${\mathbb{F}}_2^4$ at $t=2$. The Gaussian binomial coefficient counts finite-field subspaces article explains why selecting a vector subspace differs from selecting a subset of coordinates. ^[ref]

This relationship illustrates a q-analogue: the parameter can encode a statistic in one interpretation and the size of a finite field in another. Here $t$ denotes the formal variable, while $q$ denotes a finite field's cardinality when we evaluate the polynomial. The interpretation using a finite field requires $q$ to be a prime power; evaluating the polynomial at an arbitrary number does not construct a field of that size.

For every positive integer $n$, the divisor sum of the Möbius function isThe sum includes all positive integer divisors, but only squarefree divisors contribute. Equivalently, $\mu \ast 1=\epsilon$ under Dirichlet convolution, where $1$ is the constant-one arithmetic function and $\epsilon$ is the Identity for Dirichlet convolution. ^[ref]

Each squarefree divisor chooses a subset of the distinct prime factors of $n$, contributing $(-1{)}^r$ when that subset has $r$ elements. Expanding a product therefore givesFor $n>1$ at least one prime factor occurs, so the product is zero. At $n=1$ it is an empty product, equal to one. This is the same alternating cancellation that drives inclusion-exclusion.

For $30=2\cdot 3\cdot 5$, all eight positive integer divisors are squarefree integers, givingPair each subset not containing $2$ with the subset obtained by inserting $2$: $(1,2),(3,6),(5,10),(15,30)$. Each pair cancels. The same nonzero terms occur for $60$, because its squarefree divisors are still the integer divisors of $30$; its other integer divisors have Möbius function value zero.

The Möbius divisor-sum identity is the cancellation behind Möbius inversion and reciprocal Dirichlet series: aggregation over integer divisors has an exact inverse.

The Newton polynomial expresses the interpolation polynomial in products that successively vanish at all previously used interpolation nodes. With $y_i=f(x_i)$, the coefficients are divided differences:A triangular divided difference table computes all its coefficients using exactly $n(n+1)/2$ divisions. The Newton polynomial and the Lagrange polynomial have the same polynomial degree bound and the same nodal values, hence are equal by uniqueness of polynomial interpolation.

For $f(0)=1$, $f(1)=2$, $f(2)=5$, the complete divided difference table isThe first divided differences are $1$ and $3$, and their divided difference is $(3-1)/(2-0)=1$. Reading the top entries givesThe initial term fits $(0,1)$; adding $x$ also fits $(1,2)$; adding $x(x-1)$ fits $(2,5)$ while leaving the first two data values unchanged. This is the practical beauty of the Newton polynomial: each new correction respects all previous interpolation constraints.

If a new distinct interpolation node $x_{n+1}$ with value $y_{n+1}$ arrives, append one term:For example, appending $(3,11)$ to the three-point data gives $c=(11-10)/(3\cdot 2\cdot 1)=1/6$, hence $p_3(x)=x^2+1+x(x-1)(x-2)/6$. Changing the order of the interpolation nodes changes the Newton polynomial coefficients and products, but not the final interpolation polynomial in exact arithmetic.

The products also permit nested evaluation analogous to Horner's method. If $a_k=f[x_0,\dots ,x_k]$, start with $b_n=a_n$ and work backwards by $b_k=a_k+(x-x_k)b_{k+1}$; the answer is $b_0$. The three-point example becomes $1+x[1+(x-1)]$, needing two multiplications for each evaluation. This organization is useful when adding observations incrementally or evaluating a stored Newton polynomial many times; the Runge phenomenon still depends on the interpolation nodes rather than on which representation is used.

To justify the update formula, its added product vanishes at every previous interpolation node. Choosing $c$ by the new residual forces agreement at $x_{n+1}$, so uniqueness of polynomial interpolation identifies the result. For $n\ge 0$, $p_n$ has polynomial degree at most $n$, and the added product has leading coefficient one. Thus the new coefficient $c$ is exactly $f[x_0,\dots ,x_{n+1}]$. The initial state is $p_0(x)=f(x_0)$, with the empty product interpreted as one.^[ref]

Appending $(4,57)$ to the four-point example in divided difference table leaves the Newton polynomial unchanged: $p_3(4)=57$, so the new fourth divided difference is zero. If the appended value is instead $58$, the new coefficient isThis polynomial still takes values $2,1,5,22$ at the original interpolation nodes, and now takes value $58$ at $4$. A zero update is a valid completed step: adding another exact sample of the original polynomial need not increase the polynomial degree.

Split the factorial at $h$, using $k=p-1-h$:By Wilson theorem, this is $-1$. Therefore $h!k!\equiv (-1{)}^{k+1}(\mathrm{mod}p)$. If the prime number $p$ is odd, then $h+k=p-1$ is even, so $(-1{)}^k=(-1{)}^h$ andFor $p=2$, the signs $1$ and $-1$ are identical modulo $2$, and the two possibilities $(h,k)=(0,1),(1,0)$ also give the same result. The empty product convention $0!=1$ includes the endpoint cases. This is the complementary factorial congruence.

Euler's totient function $\varphi (n)$ counts the integers $1\le a\le n$ coprime to $n$, equivalently the invertible residue classes modulo $n$. Among $1,\dots ,p^e$, exactly the $p^{e-1}$ multiples of $p$ are not coprime to the prime power. HenceFactor $n={\prod }_p{p}^{e_p}$. Its distinct prime-power factors are pairwise coprime, so the permitted multiplicativity givesFor $n=1$, the empty product is one and agrees with $\varphi (1)=1$.

Use the measurable partition $B_n=\{N=n\}$ for $n\ge 0$, omitting any null cells. For $0\le s\le 1$, the random variable $s^X$ is bounded, so the law of total expectation applies without moment assumptions. Conditional on $N=n$, the sum contains exactly $n$ terms. Independence of $N$ from the whole sequence preserves their joint law under this conditioning; independence of the $Y_k$ then givesFor $n=0$ the empty sum is zero and the empty product is one, in agreement with the formula. Therefore the probability generating function of an independent random sum is

Every positive divisor has a unique prime factorization $p_1^{e_1}\cdots p_k^{e_k}$ with $0\le e_j\le i_j$. Conversely every such exponent choice gives a divisor. The exponent choices are independent, so the product rule givesFor $n=1$ the factorization is empty, and the empty product is one, corresponding to the divisor one.

Use strong induction on the positive integer $n$. The case $n=1$ is represented by the empty product. For $n>1$, if $n$ is prime it is already a product of one prime. Otherwise $n=ab$ with $1<a,b<n$; the induction hypothesis gives prime factorizations for both $a$ and $b$, and concatenating them gives one for $n$. This proves existence in the fundamental theorem of arithmetic without presupposing uniqueness.

The radical of an integer $n>0$ is the product of its distinct prime factors, each included exactly once. If the prime factorization is $n=p_1^{a_1}\cdots p_r^{a_r}$ with distinct prime numbers $p_i$ and positive integer exponents $a_i$, thenThus the radical of an integer remembers which prime factors occur and forgets their prime valuations. At $n=1$, the empty product gives $\mathrm{rad}(1)=1$. The domain of a function here is the positive integers; zero is excluded. ^[ref]

For example, $72=2^3\cdot 3^2$ has distinct prime factors $2,3$, so $\mathrm{rad}(72)=2\cdot 3=6$. Similarly,using the prime factorizations $30=2\cdot 3\cdot 5$, $32=2^5$ and $36=2^2\cdot 3^2$. The prime omega function counts the retained prime factors, while the total number of prime factors counts their occurrences before repetitions are removed.

The radical of an integer is its largest squarefree divisor. Indeed, a squarefree divisor chooses at most one copy of each prime factor, so it divides $\mathrm{rad}(n)$; the radical of an integer itself is a squarefree divisor. Consequently,The last statement follows because every nonzero prime valuation is then one. It includes $n=1$, a squarefree integer. Applying the radical of an integer twice also changes nothing: $\mathrm{rad}(\mathrm{rad}(n))=\mathrm{rad}(n)$.

For any positive integers $a,b$, the exact product rule isTo prove it, a prime factor dividing just one input occurs once in the numerator and not in the denominator. A prime factor dividing both occurs twice in the numerator and once in the denominator, since it divides their greatest common divisor. Each prime factor of $ab$ therefore remains exactly once. For coprime integers, the denominator is $\mathrm{rad}(1)=1$, proving the radical of an integer is a multiplicative function. It is not a completely multiplicative function: $\mathrm{rad}(4)=2\ne 4=\mathrm{rad}(2{)}^2$.

For a worked example with shared prime factors, take $a=12$ and $b=18$. Their greatest common divisor is $6$, and $ab=216=2^3\cdot 3^3$, soThis explains why prime support of an integer is useful: questions about the presence of prime factors can discard their multiplicities. For example, the squarefree divisors of $72$ are exactly the integer divisors of $\mathrm{rad}(72)=6$, namely $1,2,3,6$. Also $\gcd (m,n)=1$ if and only if $\gcd (m,\mathrm{rad}(n))=1$, because coprimality depends only on shared prime factors.

A further characterization uses mutual divisibility of powers: for positive integers $a,b$,If their prime supports of an integer agree, sufficiently large $k,\ell$ make all the required prime valuations large enough. Conversely, these two divisibility relations force each prime factor of either input to divide the other. For $72$ and $36$, one can take $k=2$ and $\ell =1$: $72\mid 36^2$ and $36\mid 72$.

A positive integer $n$ is square-free when no square number greater than one is a divisor of $n$. It suffices to exclude squares of prime numbers; equivalently, every prime valuation is zero or one:Thus the prime factorization of a square-free integer is a product of distinct prime factors, with no repetitions. One is included: its prime factorization is an empty product and all its prime valuations are zero. These equivalent tests are stated in Grinberg's notes. ^[ref]

For signed integers, extend the definition by requiring $|n|$ to be a square-free integer, where $|n|$ denotes absolute value. Hence $-30$ and both $1,-1$ qualify. Zero does not: every prime number has its square as a divisor of zero. The Möbius function and radical of an integer below use their existing positive integer domains, so apply them to $|n|$ when handling a negative integer.

For example, $30=2\cdot 3\cdot 5$ is a square-free integer, whereas $12=2^2\cdot 3$ is not, because $4\mid 12$ and $v_2(12)=2$. Being a composite number causes no problem: $6,10,15$ are all square-free integers. A square-free integer need not be coprime to another integer: $6$ and $10$ are both square-free integers but have greatest common divisor two. In fact the only signed integers coprime to every integer are $1,-1$, since $\gcd (n,n)=|n|$.

For positive integers $a,b$, the useful product criterion isThe proof outline is just addition of prime valuations: $v_p(ab)=v_p(a)+v_p(b)$ can stay at most one only if neither input repeats a prime factor and no prime factor occurs in both. Thus $6\cdot 5=30$ is a square-free integer, but $6\cdot 10=60$ is not. An equivalent characterization is that every factorization $n=ab$ into positive integers has coprime factors. If $p^2\mid n$, the factorization $n=p(n/p)$ supplies two factors sharing $p$; conversely, a shared prime factor forces its square to divide $n$. For $30$, the unordered factor pairs $(1,30),(2,15),(3,10),(5,6)$ all have greatest common divisor one; for $12$, the pair $(2,6)$ fails.

Two existing arithmetic functions turn the definition into practical tests:The radical of an integer keeps one copy of each prime factor, so it changes precisely the integers with a repeated prime factor. Its definition is given in Evertse's exercise sheet. ^[ref] The Möbius function assigns $(-1{)}^r$ to a square-free integer with $r$ distinct prime factors and zero otherwise; squaring forgets the sign. Consequently ${\sum }_{n=1}^{60}\mu (n{)}^2=37$ counts exactly the green cells. This connects a restriction on repeated prime factors with weighted counting and inclusion-exclusion. ^[ref]

The sum-of-divisors function adds all positive integer divisors of a positive integer, including the number itself:It is the divisor sum of the identity arithmetic function $\mathrm{id}(n)=n$, so $\sigma =\mathrm{id}\ast 1$ under Dirichlet convolution. Both factors are multiplicative functions, hence so is the sum-of-divisors function. The notation ${\sigma }_1$ distinguishes it from other weighted divisor sums. ^[ref]

For a prime number $p$ and a nonnegative exponent $a$, the positive integer divisors of the prime power $p^a$ are precisely $1,p,\dots ,p^a$. Their finite geometric series givesFor example, $\sigma (8)=1+2+4+8=15=(2^4-1)/(2-1)$. For a prime factorization $n={\prod }_{k=1}^r{p}_k^{a_k}$ with distinct prime numbers $p_k$ and positive exponents $a_k$, multiplicativity givesFor $n=1$, this is an empty product, equal to $1$. ^[ref]

The distributive property makes the formula especially beautiful: choosing one term from each factor produces each positive integer divisor exactly once, by the fundamental theorem of arithmetic. For $12=4\cdot 3=2^2\cdot 3$, the choices form a three-by-two grid with entries $2^i{3}^j$, where $0\le i\le 2$ and $0\le j\le 1$. Adding its rows givesThe divisor function counts six cells; the sum-of-divisors function adds their six values. Once the prime factorization is known, the product formula avoids testing every candidate integer divisor. Shared prime factors require care: $\sigma (4)=7\ne 9=\sigma (2{)}^2$, so the sum-of-divisors function is not a completely multiplicative function.

Subtracting the number itself gives the proper-divisor sum $s(n)=\sigma (n)-n$. Comparing $s(n)$ with $n$ distinguishes perfect numbers, deficient numbers, and abundant numbers. For $6$, $s(6)=1+2+3=6$; for $28$, $s(28)=1+2+4+7+14=28$. Both are perfect numbers. The calculation $s(8)=1+2+4=7<8$ makes $8$ a deficient number, while $s(12)=1+2+3+4+6=16>12$ makes $12$ an abundant number. These comparisons turn the sizes of integer divisors into a classification of positive integers. ^[ref]

This connection is ancient: Euclid's Elements, Book IX, Proposition 36, constructs a perfect number by multiplying the last term of $1,2,\dots ,2^{k-1}$ by their sum, when that sum is a prime number. In modern notation, put $q=2^k-1$ and $N=2^{k-1}q$, with $k\ge 2$ and $q$ a prime number. The sum-of-divisors function proves the construction immediately:Consequently the proper-divisor sum is $s(N)=N$. Taking $k=2,3$ produces the perfect numbers $6,28$. ^[ref]