A linear integral equation depends linearly on its unknown function. For example, $(I+K)f=g$ with $(Kf)(x)=\int K(x,y)f(y)dy$ has a trivial homogeneous null space whenever its inhomogeneous problem has a unique solution: otherwise a nonzero homogeneous solution could be added to that solution. This is the uniqueness step used in dressing constructions of a Lax pair.

This square-root-kernel integral equation is inverted by integrating $g(x)/\sqrt{x-z}$ over $z<x<b$ and interchanging integrations. The inner integral over $z<x<y$ equals $\pi$, so ${\int }_z^{b}g(x)/\sqrt{x-z}dx=\pi {\int }_z^{b}f(y)dy$. Differentiating recovers $f(z)=-{\pi }^{-1}d[{\int }_z^{b}g(x)/\sqrt{x-z}dx]/dz$. The changes of variables $x=p^2$, $y={\eta }^2$ put the angular-ray equation into this form.

A permutation assigns facilities to locations, and the objective combines their pairwise interactions with pairwise location costs. Ordered-pair and unordered-pair conventions differ by a factor of two for symmetric data. The decision version is NP-complete: letting $A$ record a directed cycle makes the objective exactly the length of a travelling salesman problem tour under the ordering given by the permutation. The optimization version is NP-hard.

Given bidders' values $v_i(S)$ for item bundles, the winner determination problem maximizes ${\sum }_i{v}_i(S_i)$ over disjoint allocated bundles. When every item must be assigned, the bundles form a partition. General values permit complements and difficult combinatorial search; monotone submodular set functions permit a greedy half-approximation. Complexity claims must specify whether the values are supplied explicitly or by a value oracle.

If $Bz=b$, $z\ge 0$ has an integer solution, with $N$ variables and all data bounded by $M\ge 1$, it has one satisfying the displayed bound. Apply support-minimal rays of a nonnegative kernel to $(z,1)$ in the cone $\{(u,t)\ge 0:Bu=bt\}$. Its integer generators have coordinates bounded by $D=(N+1)!M^{N+1}$. Generators with positive last coordinate normalize to feasible points with coordinates at most $D$; their coefficients form a convex combination. The remaining generators are integer recession directions. Subtract the integer parts of their coefficients from the original integer solution. The result remains integral and feasible and has coordinates at most $D+(N+1)D$. Its binary length is polynomial in the input size. Splitting unrestricted integer variables and adding integer slacks reduces general integer linear feasibility to this form, proving its membership in NP.

Partition positive item weights into two bins to minimize the heavier total. The optimum is at least both half the total weight and the largest individual weight. This is two-machine makespan minimization, rather than the version of bin packing that minimizes the number of fixed-capacity bins.

A congruence of squares says that two integers $a,b$ have the same square modulo a positive integer $N$. Factoring their difference of squares givesA useful integer factorization results when $\gcd (a-b,N)$ or $\gcd (a+b,N)$ is a proper divisor of $N$. Divisibility of a product does not generally force divisibility of either factor by all of $N$: different prime factors of $N$ can divide different parts of that product.

For $N=77$, $20^2-13^2=231=3\cdot 77$. ThereforeThus $77=7\cdot 11$. The prime seven divides the difference, while eleven divides the sum. These computations already give a complete prime factorization because seven and eleven are prime numbers.

The Chinese remainder theorem explains the hidden sign choices. The four congruence classes solving $z^2\equiv 15(\mathrm{mod}77)$ have representatives $13,20,57,64$. Modulo seven each is $1$ or $-1$; modulo eleven each is $2$ or $-2$. Two independent sign choices produce four roots. The inputs thirteen and twenty agree modulo seven and disagree by sign modulo eleven, allowing their sum and difference to separate the two prime factors.

For distinct odd prime numbers $p,q$, $N=pq$ and $\gcd (b,N)=1$, a solution $a^2\equiv b^2(\mathrm{mod}N)$ with $a\not\equiv b$ and $a\not\equiv -b$ modulo $N$ yields both proper factors by the two greatest common divisors. For a general composite integer, a proper divisor need not itself be prime; further factoring can remain. If $a\equiv b$ or $a\equiv -b(\mathrm{mod}N)$ in the coprime case, the two calculations return $N$ and one instead. A factor base helps generate relations, but does not ensure every resulting relation is useful.

For historical context, Pomerance describes Kraitchik's 1920s enhancement of the difference-of-squares approach associated with Fermat: seek a difference that is a multiple of $N$, rather than exactly $N$. His account also notes antecedents in Gauss and Seelhoff, so this is not an attribution of the whole idea to a single inventor. ^[ref].

The odd part of a positive integer $n$ is the unique odd positive integer $d$ obtained by repeatedly dividing $n$ by two. The process terminates because the positive integers decrease. If $2^{r}d=2^{s}e$ with $d,e$ odd, then $r>s$ would make $e$ even and $s>r$ would make $d$ even; hence $r=s$ and $d=e$. Two positive integers have the same odd part exactly when their ratio is an integral power of two. The odd positive integers therefore give representatives for the resulting equivalence classes.

A factor base is a finite set of small prime numbers over which selected auxiliary integers are completely factored. Some methods also record a sign coordinate for $-1$, which is not a prime number. A positive integer supported entirely on the chosen factor base gives an exponent vector; reducing that vector modulo two records which prime exponents are odd integers. The product is a square of a number precisely when every prime exponent is an even integer.

For the original toy $N=77$, use factor base $\{2,3,5\}$ and the two relationsThe residues have exponent vectors $(0,1,1)$ and $(2,1,1)$ in the order $(2,3,5)$. Adding the two vectors modulo two gives $(0,0,0)$, so multiplying the residues gives $15\cdot 60=900=30^2$. Consequentlyand $\gcd (X-Y,77)=7$ and $\gcd (X+Y,77)=11$. Neither individual residue was a square; combining the relations made all exponents even.

In a larger collection, choose relations $x_i^2\equiv r_i(\mathrm{mod}N)$ with positive residues $r_i={\prod }_{j=1}^B{p}_j^{e_{ji}}$. If a nonempty selection $I$ has an even sum in every exponent coordinate, setThen $X^2\equiv Y^2(\mathrm{mod}N)$. Finding such a selection is a linear dependence problem over the finite field ${\mathbb{F}}_2$: the indicator vector of the chosen relations belongs to the kernel of a linear map given by the parity matrix. This is why a problem about prime factors recruits linear algebra. The final congruence of squares may still be trivial, so another selection can be needed. ^[ref].

There is a tradeoff: a small factor base gives a smaller parity matrix, but fewer auxiliary integers factor completely over it. A larger factor base accepts more relations but makes the linear algebra larger. Negative auxiliary values need an additional sign coordinate, and a selected product needs even sign parity as well as even prime exponents. Pomerance's account explains this balance and the historical development of combining smooth relations; the toy example omits algorithm-specific sieving and running-time claims. ^[ref].

A repdigit is a positive integer whose base-$b$ expansion repeats one nonzero digit $d$. For $b\ge 2$, $1\le d<b$ and $n\ge 1$, the finite geometric series gives $R_n=d(1+b+\cdots +b^{n-1})=d(b^n-1)/(b-1)$. For example, $5(10^n-1)/9$ has $n$ decimal digits, all equal to five.

Every prime number not dividing $b$ divides infinitely many such repdigits. If it divides $d$, every length works. Otherwise, if it does not divide $b-1$, the Fermat little theorem gives divisibility for lengths that are multiples of $p-1$, and division by $b-1$ is justified by its modular inverse. If $p\mid b-1$, the sum is congruent to $dn$ modulo $p$, so lengths divisible by $p$ work instead. A prime dividing $b$ but not $d$ divides none, since $R_n\equiv d(\mathrm{mod}p)$. This distinction prevents invalid cancellation of the geometric-sum denominator.

Lossless source coding encodes source messages so they can be recovered exactly. Shannon's source coding theorem relates its achievable average code length to information entropy.

A Markov information source uses a stationary finite Markov chain to emit symbols. The emitted symbol can be a function of the state. If it does not identify that state, the observed sequence need not itself be a Markov chain. The examples here use a fully observed Markov source, which makes the next-symbol uncertainty directly computable from the transition matrix.

The entropy rate measures average new uncertainty per emitted symbol of a stochastic process. Predictability from earlier symbols can make this much smaller than the information entropy of one symbol. For example, a binary Markov source can emit a fair bit at every time while repeating its previous bit with probability $7/8$: each individual symbol has one bit of uncertainty, but the entropy rate is only about $0.544$ bits per symbol.

For a finite alphabet source $X=(X_1,X_2,\dots )$, definewhen the limit exists. Base-two logarithms give bits per symbol. Multiplying by a fixed emission frequency $f$ gives $fh(X)$ bits per unit time; the symbol rate and the uncertainty of the sequence are different inputs. A strictly stationary process on a finite alphabet always has an entropy rate, equal to its conditional entropy rate.^[ref]

For an independent and identically distributed source, the chain rule for information entropy gives $H(X_1,\dots ,X_n)=nH(X_1)$, hence $h(X)=H(X_1)$. With dependence, conditioning reduces entropy and makes the past useful. The examples under Markov information source show this benefit using exact finite-block calculations.

Rate-distortion theory asks how much mutual information must survive when a representation may lose detail. Lossy compression groups different inputs into one reconstruction; a distortion measure specifies which differences matter. The rate-distortion function then gives a quantitative tradeoff between allowed expected distortion and the required number of bits. A smaller file is useful only if its reconstruction retains the distinctions that the application needs.

A memoryless classical source emits independent and identically distributed random variables from a fixed finite alphabet. Its block probability mass function factors as shown, and its information per symbol is the Shannon entropy $H(U)=-{\sum }_{u}p(u){\log }_{2}p(u)$. Zero-probability symbols never occur and contribute zero to the entropy. The typical sequence theorem describes the size and probability of the high-probability block set used for reliable compression.

The unit for information content or information entropy computed with natural logarithms. Converting to bits divides the numerical value by $\log 2$, so $1\mathrm{nat}=(1/\log 2)\mathrm{bits}$.

A bit is a binary classical symbol with two distinguishable values, zero and one. A uniform random bit has one bit of information entropy, while a biased binary symbol has less. Sending one bit means transmitting one symbol from this binary alphabet; the mutual information it carries about a particular input need not be one.

A communication channel describes how transmitted inputs become received outputs. In a probabilistic model, conditional probabilities specify which outputs each input can produce. A discrete memoryless channel uses the same finite transition law independently on successive symbols; channel capacity quantifies its optimal reliable transmission rate.

For probability distributions $p,q$ on the same finite alphabet, the Bhattacharyya coefficient measures their square-root overlap:The vectors $(\sqrt{p_i}{)}_i$ and $(\sqrt{q_i}{)}_i$ have unit Euclidean norm, so the Cauchy-Schwarz inequality gives $0\le B\le 1$. Equality $B=1$ holds exactly when the distributions agree; $B=0$ holds exactly when they assign positive probability to disjoint outcomes. For $p=(0.9,0.1)$ and $q=(0.6,0.4)$, $B=\sqrt{0.54}+0.2\approx 0.934847$. This overlap is not the probability that two independent draws agree, which here is $0.58$.

The fidelity of commuting mixed states reduces to this coefficient. More generally, the measurement characterization of quantum fidelity minimizes it over outcome distributions of a common quantum measurement, connecting classical overlap to the unsquared quantum fidelity.

In the infinite square well on $(-a,a)$, extend $\sqrt{2/a}\sin (\pi x/a)$ from $(0,a)$ by zero. It is normalized and continuous, but its derivative jumps at zero. Its energy expectation value is the quadratic form of a positive quantum Hamiltonian ${\hslash }^2\int |{\psi }^{\prime }{|}^2/(2m)$, giving the displayed value. It is not in the operator domain of the Dirichlet Hamiltonian operator: its distributional second derivative contains a Dirac delta. Its sine-basis coefficients are $a_2=-1/\sqrt{2}$, all other even coefficients zero, and $a_{2p+1}=4\sqrt{2}(-1{)}^p/[\pi (4-(2p+1{)}^2)]$. These make ${\sum }_n{E}_n|a_n{|}^2$ finite but ${\sum }_n{E}_n^2|a_n{|}^2$ divergent, independently distinguishing the form domain from the operator domain.