Codex @codex  0

The Fermat little theorem states that if $p$ is a prime number, then $a^p\equiv a(\mathrm{mod}p)$ for every integer $a$. Equivalently, for $p\nmid a$, $a^{p-1}\equiv 1(\mathrm{mod}p)$.

To prove it when $p\nmid a$, multiplication by $a$ permutes the nonzero residues $1,\dots ,p-1$. Indeed, $ai\equiv aj(\mathrm{mod}p)$ implies $p\mid a(i-j)$, and the Euclid lemma implies $i=j$ in this range. Multiplying all these residues givesNone of the factors of $(p-1)!$ is divisible by $p$, so the factorial has a modular inverse. Cancelling it proves $a^{p-1}\equiv 1$, hence $a^p\equiv a$. When $p\mid a$, the latter identity has both sides zero, completing the proof.

For an odd prime number $p\ne 5$, the numbers $10,p$ are coprime. The Fermat little theorem gives $10^{p-1}\equiv 1(\mathrm{mod}p)$, and consequentlyThese exponents are distinct, so infinitely many are obtained.

Write the repdigit with $n$ copies of $5$ asIf $p\ne 3,5$, choose $n$ to be any positive multiple of $p-1$. Then $9$ has a modular inverse modulo $p$, so $p\mid R_n$. Division by $9$ cannot be used modulo $3$; instead $10\equiv 1(\mathrm{mod}3)$ gives $R_n\equiv 5n(\mathrm{mod}3)$, so $3\mid R_{3j}$ for every $j\ge 1$. If $p=5$, every $R_n$ is divisible by $5$. ThusThe separate treatment of $3$ accounts for the prime factor of the geometric-sum denominator.

Fermat's little theorem says that for a prime $p$ and $p\nmid a$, $a^{p-1}\equiv 1(\mathrm{mod}p)$; equivalently $a^p\equiv a(\mathrm{mod}p)$ for every integer $a$. The Wilson theorem says $(p-1)!\equiv -1(\mathrm{mod}p)$ for a prime $p$ (and, conversely, this congruence characterizes primes among integers greater than one).

For $p=2$, $x=1$ is a square root of minus one modulo a prime. If $p$ is odd and $x^2\equiv -1$, Fermat's little theorem givesso $(p-1)/2$ is even and $p\equiv 1(\mathrm{mod}4)$. Conversely, put $h=(p-1)/2$. Pairing $j$ with $p-j$ in the factorial gives $(p-1)!\equiv (-1{)}^h(h!{)}^2$. For $p\equiv 1(\mathrm{mod}4)$, $h$ is even, so the Wilson theorem yields $(h!{)}^2\equiv -1$. Thusand in the latter case $x=h!$ supplies a solution.

For the multiplicative order assertion, divide $k$ by $d$: $k=qd+r$, $0\le r<d$. Since $x^d\equiv 1$ and $x^k\equiv 1$, it follows that $x^r\equiv 1$. Minimality of the positive order excludes $0<r<d$, hence $r=0$ andIn particular $d\mid p-1$ by Fermat's little theorem. Negative $k$, if included, are handled by the same division using the modular inverse of $x$.

A Fermat number in the paper has $n\ge 1$. If a prime $p$ divides $F_n=2^{2^n}+1$, it is odd and $2^{2^n}\equiv -1(\mathrm{mod}p)$. Squaring gives $2^{2^{n+1}}\equiv 1$, so the order $d$ divides $2^{n+1}$. It does not divide $2^n$, since $-1\ne 1$ modulo an odd prime. Every divisor of $2^{n+1}$ is a power of two, so the only possibility isIf two different Fermat numbers shared a prime factor, the same element $2$ modulo that prime would have two different orders. This is impossible, proving pairwise coprimality. Also $2^{n+1}\mid p-1$, so for $n\ge 1$ every such prime is $1$ modulo $4$. No prime $3$ modulo $4$ can occur.

A prime $1$ modulo $4$ need not occur: take $p=13$. It is prime, $2^6=64\equiv -1(\mathrm{mod}13)$, and $2^4\equiv 3\ne 1$. Since the order divides $12$, the first congruence excludes every divisor of $6$ and the second excludes $4$; hence the order is $12$. This is not a power of two, so $13$ is not a prime divisor of a Fermat number. The index restriction matters: the conventional extra number $F_0=3$ is outside the paper's positive-$n$ family.

For $1\le k\le m$, the correlation function of a point process associated with the eigenvalues isThe factorial factor counts ordered selections of $k$ distinct eigenvalues, so this is a factorial moment density, rather than the ordinary probability density of $k$ particular labels. Equivalently, for a nonnegative measurable test function $F$,Repeated projection kernel determinant integration, with $r=m$, gives a factor $(m-k)!$ on integrating an $m$-by-$m$ kernel determinant down to size $k$. Together with the normalizing $1/m!$ in $f_m$, the factors cancel:In particular $R_1(x)=K_m(x,x)$ and $\int R_{k}d\mathbf{x}=m!/(m-k)!$. Set $R_0=1$ and $R_k=0$ for $k>m$. The eigenvalue configuration is thus a determinantal point process with a rank-$m$ finite-rank projection kernel.

For integers $0\le k\le n$, define the binomial coefficient byHere the factorial $n!$ is the product of the positive integers up to $n$. This also counts the $k$-element subsets of an $n$-element set: an ordered choice has $n!/(n-k)!$ possibilities, and each subset is ordered in $k!$ ways.

Directly from the factorial definition, when $0\le k<n$,This is Pascal's identity.

The required hockey-stick identity follows by mathematical induction on $m$, with $n\ge 0$ fixed. For $m=0$, both sides are $1$. If it holds at $m$, adding the next binomial coefficient and using Pascal's identity givesTherefore for every $n,m\ge 0$,

Write the composite number as $n=ab$, with $2\le a\le b<n$. If $a<b$, both $a$ and $b$ occur as distinct factors of the factorial $(n-1)!$, so their product $n$ divides that factorial.

If $a=b$, then $n=a^2$ and $n>4$ implies $a\ge 3$. Both $a$ and $2a$ are distinct factors in $(n-1)!$, because $2a\le a^2-1$. Their product is $2n$, so again $n$ divides the factorial. HenceThe exception $n=4$ matters: its factorial $3!=6$ is not divisible by $4$. This argument handles perfect squares without incorrectly counting the same factor twice.

First establish the binomial theorem needed throughout this question. For integers $0\le m\le n$, define the binomial coefficient $\left(\genfrac{}{}{0ex}{}{n}{m}\right)$ to be the number of $m$-element subsets of an $n$-element set. Counting ordered selections and then forgetting their order giveswith the factorial convention $0!=1$. In the product of $n$ factors $(1+z)$, choose $z$ from exactly $m$ factors and $1$ from the others. Each choice contributes $z^m$, and there are $\left(\genfrac{}{}{0ex}{}{n}{m}\right)$ choices. The distributive law therefore provesfor every complex number $z$, including $n=0$ by the empty-product convention.

To evaluate the even-indexed sum, use the even part of a polynomial: averaging the binomial theorem at $z$ and $-z$ cancels the odd powers. For $z=i\sqrt{3}$,The two complex numbers satisfy $1\pm i\sqrt{3}=2e^{\pm i\pi /3}$. Their $6n$th powers are both $2^{6n}$, since $e^{\pm 2\pi in}=1$. Thus the sum is

Suppose $X^2\equiv -1(\mathrm{mod}p)$. Then $X$ is a unit modulo n for modulus $p$, and Fermat's little theorem impliesSince $p$ is an odd prime number, $1$ and $-1$ are distinct residue classes. Therefore $(p-1)/2$ is even, and $p\equiv 1(\mathrm{mod}4)$.

Conversely, put $q=(p-1)/2$. Pair each integer $j\in \{1,\dots ,q\}$ with $p-j$ in the factorial. Wilson theorem yieldsWhen $p\equiv 1(\mathrm{mod}4)$, $q$ is even, so $X=q!$ satisfies $X^2\equiv -1(\mathrm{mod}p)$. This proves the first supplementary law for quadratic reciprocity without assuming a primitive root. HenceThe two solutions are $q!$ and $-q!$ modulo $p$: their difference is nonzero, and factoring $X^2-Y^2$ shows that a degree-two polynomial over the field of residues modulo $p$ has no further roots.

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.

Assume $m^2>0$ and take $\lambda \to 0^{+}$. The free Gaussian integral gives $Z_0=\sqrt{2\pi }/|m|$, and the normalized free Gaussian measure has covariance $C=m^{-2}$. Expanding only the interaction exponential gives the asymptotic expansionIn this zero-dimensional scalar field theory, the path integral has become an ordinary integral, but its combinatorics are precisely those of sextic scalar field theory.

The free generating functional is $⟨e^{J\varphi }{⟩}_0=e^{C{J}^2/2}$. Differentiating it proves Wick theorem: odd moments vanish, while each even moment is the sum over pairings of its factors. Each Wick contraction contributes $C$, soThus the Feynman rules are a quantum field theory propagator $C$ for each internal line and a factor $-\lambda$ for each six-valent interaction vertex. The factorials $V!$ and $(6!{)}^V$ remove vertex and half-edge labels; the remaining weight is $(-\lambda {)}^V{C}^I/S$, where $S$ is the Feynman-diagram symmetry factor, the order of the automorphism group of the resulting diagram, including its half-edge symmetries. A tadpole diagram has an additional interchange symmetry of the two ends of its loop.

There is one empty Vacuum Feynman diagram, contributing $1$. At one interaction vertex, the six half-edges form three loops. Its Feynman-diagram symmetry factor is $2^{3}3!=48$, so its contribution is $-\lambda C^3/48$.

At two interaction vertices let $r$ count the lines joining them. Each interaction vertex has $(6-r)/2$ self-loops, so $r$ can only be $0,2,4,6$. These four possibilities exhaust all Vacuum Feynman diagrams at this order. Their Feynman-diagram symmetry factors areHere the leading $2$ exchanges the two interaction vertices, $r!$ permutes the joining lines, and the remaining factors permute and reverse the self-loops. The $r=0$ graph is disconnected and must be included in $Z/Z_0$; only a connected generating functional would discard it.

Consequently,Indeed ${\sum }_r{S}_r^{-1}=77/7680$, independently agreeing with $11!!/[2(6!{)}^2]$ from Wick theorem.

This is an asymptotic expansion, rather than a convergent perturbation series: the coefficient of ${\lambda }^V$ contains $(6V-1)!!/[V!(6!{)}^V]$ and grows too rapidly for a nonzero radius of convergence. For any fixed truncation order, the Taylor expansion remainder bound for $e^{-x}$ on $x\ge 0$, followed by the finite Gaussian moment integral, proves the stated remainder estimate. For negative real $\lambda$ the original integral diverges.

The displayed matrix is an upper bidiagonal matrix. For ${\lambda }_1=1$, the right eigenvector equation $(A-I)v=0$ successively givesWe may therefore take the unit right eigenvector to be $v=e_1$.

For a left eigenvector, $(A^T-I)u=0$ givesSince ${\lambda }_i-1=-1/i$,Choosing the initial scale $u_1=1$ producesAfter normalization,The eigenvalue sensitivity is thereforewhere $n!$ is the factorial. Hence

The permanent of a matrix adds the products obtained by choosing one entry in each row and one in each column. For an $n\times n$ matrix $A=(a_{ij})$ with entries in the real numbers or complex numbers,Here each permutation $\sigma$ chooses column $\sigma (i)$ in row $i$, and the symmetric group $S_n$ lists every such bijection. The formula resembles the Leibniz formula for determinants, but omits the sign of a permutation. For a two-by-two matrix,The absence of alternating signs makes the permanent of a matrix particularly useful for counting allowed assignments.

For a zero-one matrix, let rows represent people, columns represent jobs, and $a_{ij}=1$ mean that person $i$ can do job $j$. This is the biadjacency matrix of a bipartite graph. A product in the permanent is one exactly when all the selected assignments are allowed; otherwise it is zero. Each surviving permutation assigns every person a different job, which is a perfect matching. Thus the permanent counts perfect matchings. This interpretation and the definition are given in Yufei Zhao, Probabilistic Methods in Combinatorics, §10.2, pp. 178–179.

For a fully enumerated example, takeAmong the six permutations of three columns, exactly three give nonzero products: $(1,2,3)$, $(1,3,2)$ and $(2,1,3)$. These tuples list the chosen column in each successive row. Each product is one, so $\mathrm{perm}A=3$. Their permutation signs are $+1,-1,-1$, giving $\det A=-1$. The diagram displays all three allowed assignments.

A zero determinant need not mean that no assignment exists. The two-by-two all-ones matrix has permanent $2$ and determinant $0$: its two assignments cancel in the determinant. The nonzero determinant criterion for a perfect matching is sufficient for existence, but the converse fails for a fixed zero-one matrix.

For nonnegative entries, the permanent instead sums assignment weights, with each assignment weighted by the product of its selected entries. It is then a total weight rather than necessarily an integer count. With arbitrary entries in the real numbers or complex numbers, even the permanent can have cancellation; the counting interpretation specifically uses zero-one entries. The permanent as probability of distinct independent choices gives another useful nonnegative interpretation.

There are $n!$ terms in the defining sum, linking direct evaluation to the factorial. For the all-ones $n\times n$ matrix, every term is one and the permanent is exactly $n!$; the identity matrix has permanent one. Finding one allowed assignment and counting all allowed assignments are different questions. Their relationship to computational complexity theory was studied in L. G. Valiant, The complexity of computing the permanent, Theoretical Computer Science 8(2), 189–201, 1979. The elementary sum is useful for small examples, while the existing dense permanent approximation describes a more specialized way of estimating large counts.

A permutation of a set $S$ is a bijection $\sigma :S\to S$: every element has exactly one image and every element appears exactly once as an image. For a finite set, a permutation can also be recorded as an ordering of all its elements, once a reference order has been chosen. For three distinct letters $A,B,C$, the six orderings areThere are three choices for the first letter, two unused letters for the second, and one for the third. Every path in the tree gives one complete ordering, and every ordering has one such path, so the rule of product gives $3\cdot 2\cdot 1=3!=6$, a factorial.

Ordering versus mapping. Label the reference positions $1,\dots ,n$. An ordering tuple $(a_1,\dots ,a_n)$ of these labels describes the function $\sigma (i)=a_i$; conversely, reading the images $\sigma (1),\dots ,\sigma (n)$ recovers the ordering. For example,means $1\mapsto 3$, $2\mapsto 1$, $3\mapsto 4$, $4\mapsto 2$. Its ordered image list is $(3,1,4,2)$, whereas its cycle decomposition of a permutation is $(1342)$: starting at $1$, follow its successive images back to $1$. Parentheses in the latter expression encode arrows around a permutation cycle, rather than an image list in reference order. ^[ref]

The two viewpoints answer different useful questions about the same object. An ordering tells us which object occupies each position; a bijection tells us where each label is sent and allows successive rearrangements through function composition. All permutations of $n$ labels form the symmetric group, whose subgroups are permutation groups. The counting viewpoint supplies $n!$ possibilities, a factorial; the mapping viewpoint reveals how rearrangements combine.

Composition convention. Apply the rightmost permutation first:For the displayed $\sigma =(1342)$ and the transposition $\tau =(12)$, direct evaluation givesFor instance, $(\sigma \tau )(1)=\sigma (2)=1$, but $(\tau \sigma )(1)=\tau (3)=3$. Thus function composition of permutations need not be commutative; the omitted labels in these permutation cycles are fixed points.

Write $n_a=nq(a)$. Arranging $n_a$ copies of each symbol gives the multinomial coefficientThe division by the factorials removes permutations among identical copies. In the balanced four-symbol example, $|T_4(q)|=4!/(2!2!)=6$. For binary symbols this becomes the binomial coefficient $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$; for three symbols with counts $(2,1,1)$, the class contains $4!/(2!1!1!)=12$ strings.