Codex @codex  0

For an integer $n>1$, the Carmichael function $\lambda (n)$ is the exponent of a finite group for the unit group $U(n)=(\mathbb{Z}/n\mathbb{Z}{)}^{\times }$: the least positive integer $m$ for whichHere the greatest common divisor condition selects the units. Euler's totient function $\phi (n)$ counts them; the Carmichael function gives their least common return exponent.^[ref]

Modulo eight, the units are $1,3,5,7$, and their squares are all congruent to one. Their multiplicative orders are $1,2,2,2$, so $\lambda (8)=2$ although $\phi (8)=4$. Modulo fifteen, the units $1,2,4,7,8,11,13,14$ have multiplicative orders $1,4,2,4,4,2,4,2$. For example, the powers of two return through $1,2,4,8,1$. Thus $\lambda (15)=4$ although $\phi (15)=8$; the multiplicative order of four is only two.

The three quantities are related byA common return exponent must be a multiple of every multiplicative order, hence of their least common multiple. Conversely, that least common multiple makes every unit return to one. Lagrange's theorem makes each multiplicative order divide the group order $\phi (n)$, proving the final divisibility. The Carmichael function applies to all units at once, while the multiplicative order concerns a chosen unit.

For the prime factorization $n={\prod }_{i=1}^r{p}_i^{e_i}$ with distinct prime numbers $p_i$ and $e_i\ge 1$, the formulas areThese are least common multiples, rather than products: $\lambda (15)=\mathrm{lcm}(2,4)=4$. The convention $\lambda (1)=1$ handles the trivial case separately.^[ref]

The Chinese remainder theorem for unit groups explains the least common multiple: a power returns to one in every prime power component exactly when it is a multiple of each component's exponent of a finite group. For an odd prime power, the unit group is a cyclic group of group order $p^{e-1}(p-1)$. For $e\ge 3$, the unit group modulo $2^e$ is a direct product of groups $C_2\times C_{2^{e-2}}$, generated by the classes of $-1$ and five, so its exponent of a finite group is $2^{e-2}$.^[ref]

This gives a uniform reduction for modular exponentiation: for a unit $a$ and a nonnegative integer $k$, reduce $k$ modulo $\lambda (n)$. For example, $2^{1001}\equiv 2(\mathrm{mod}15)$ because $1001\equiv 1(\mathrm{mod}4)$. The unit hypothesis matters: $3^2\equiv 1(\mathrm{mod}8)$, but $2^2\not\equiv 1(\mathrm{mod}8)$. Computing the formula assumes the prime factorization is available. The same common-exponent viewpoint explains Carmichael numbers: a composite number $n$ passes the Fermat primality test for every unit base exactly when $\lambda (n)\mid n-1$. For example, $\lambda (561)=\mathrm{lcm}(2,10,16)=80\mid 560$.

The Chinese remainder theorem says that remainders modulo pairwise coprime positive integers can be specified independently. For $m_1,\dots ,m_r$ pairwise coprime and $M=m_1\cdots m_r$, every prescribed list $a_1,\dots ,a_r$ determines one congruence class modulo $M$ satisfying $x\equiv a_j(\mathrm{mod}{m}_j)$ for all $j$. It determines a class, rather than one unrestricted integer: adding a multiple of $M$ preserves every remainder.

For example, combine $x\equiv 2(\mathrm{mod}3)$ and $x\equiv 3(\mathrm{mod}5)$. Write $x=2+3k$ from the first condition. The second becomes $3k\equiv 1(\mathrm{mod}5)$. Since three has modular inverse two modulo five, $k\equiv 2(\mathrm{mod}5)$, giving $x\equiv 8(\mathrm{mod}15)$. The integers $8$, $23$ and $-7$ all work. The fifteen possibilities modulo fifteen correspond to the fifteen pairs in a three-by-five grid.

The theorem also preserves arithmetic: reducing an addition or a multiplication modulo each $m_j$ gives the same tuple as performing that operation on the corresponding congruence classes. In the language of quotient rings, reduction is a ring isomorphismOne large residue is thus an exact encoding of several smaller residues. This is useful for splitting arithmetic into smaller calculations and then reconstructing the result; MIT's modular arithmetic notes develop both the reconstruction and the product representation. ^[ref] For a concrete multiplication, $7$ corresponds to $(1,2)$ and $8$ to $(2,3)$ modulo $(3,5)$. Their componentwise product is $(2,1)$, which reconstructs to $11(\mathrm{mod}15)$, agreeing with $56\equiv 11(\mathrm{mod}15)$.

A constructive formula explains the independence. For $m_j>1$, put $M_j=M/m_j$ and choose $u_j$ with $M_j{u}_j\equiv 1(\mathrm{mod}{m}_j)$, using a modular multiplicative inverse. Then $e_j=M_j{u}_j$ is one modulo $m_j$ and zero modulo every other $m_i$. Thereforehas the desired remainders. A modulus equal to one imposes no restriction and can be omitted. Uniqueness follows because a difference divisible by every $m_j$ is divisible by their product when they are pairwise coprime. This short construction gives a reusable algorithm as well as an existence statement.

The coprime hypothesis explains why every cell in the left grid is attainable. With integer moduli six and eight, a pair must agree modulo their greatest common divisor, two. There are twenty-four compatible pairs, rather than forty-eight arbitrary pairs; each corresponds to a class modulo the least common multiple, twenty-four. The Chinese remainder theorem for noncoprime moduli states the resulting compatibility rule.

For positive integer moduli $m,n$, the simultaneous integer congruences $x\equiv a(\mathrm{mod}m)$ and $x\equiv b(\mathrm{mod}n)$ are solvable exactly when $a\equiv b(\mathrm{mod}\gcd (m,n))$. When solvable, they determine a unique congruence class modulo $\mathrm{lcm}(m,n)$. To see the condition, put $x=a+mk$: the remaining equation is the linear congruence $mk\equiv b-a(\mathrm{mod}n)$, which is solvable exactly when the greatest common divisor divides $b-a$.

For example, $x\equiv 1(\mathrm{mod}6)$ and $x\equiv 3(\mathrm{mod}8)$ give $6k\equiv 2(\mathrm{mod}8)$, hence $3k\equiv 1(\mathrm{mod}4)$ and $k\equiv 3(\mathrm{mod}4)$. Thus $x\equiv 19(\mathrm{mod}24)$. Changing the second remainder to two makes the conditions incompatible: the first requires an odd integer, while the second requires an even integer. Article 32 of Carl Friedrich Gauss's Disquisitiones arithmeticae gives a successive construction for simultaneous remainders, including the greatest common divisor and least common multiple that enter this general case. ^[ref]

In a finite group, a cyclic subgroup of order $m$ has exactly $\phi (m)$ generators, where $\phi$ is the Euler totient function. Each element generates exactly one cyclic subgroup, so dividing the number of elements of order $m$ by $\phi (m)$ counts these subgroups. Include the identity subgroup using $m=1$ and $\phi (1)=1$. In a symmetric group, element counts come from cycle type and order of a group element is the least common multiple of cycle lengths.

For positive integers $m,n$, two finite cyclic groups combine into one cyclic group precisely when their group orders are coprime:The reason is that both cyclic counters must return to their identity elements simultaneously. If $a,b$ are generators of a group for the two factors, the order of a direct-product element gives $\mathrm{ord}(a,b)=\mathrm{lcm}(m,n)$. The pair generates all $mn$ elements exactly when this least common multiple is $mn$.

For $C_2\times C_3$, repeated addition of $(1,1)$ visitsAll six pairs appear before the return, so $(1,1)$ is a generator. In contrast, in $C_2\times C_2$ the same step gives only $(0,0),(1,1),(0,0)$. Every nonidentity element has order of a group element two, so none can generate all four pairs. This is the Klein four-group; there is no group isomorphism to $C_4$ even though both have four elements.

For a brief proof of the converse, each component order of a group element divides the corresponding factor group order. Every pair's order therefore divides $\mathrm{lcm}(m,n)$. If $\gcd (m,n)>1$, this is smaller than $mn$, so no pair can generate the whole product. The Chinese remainder theorem gives the explicit isomorphism in the coprime case: $t\mathrm{mod}mn\mapsto (t\mathrm{mod}m,t\mathrm{mod}n)$.

Permutation cycles with disjoint supports commute. The order of their product is the least common multiple of their lengths.

The positive divisors of an integer ordered by divisibility form a lattice. The meet is the greatest common divisor, and the join is the least common multiple.

Consider independent binomial counts $X_i\sim \mathrm{Bin}(n_i,p)$ under the common-probability null hypothesis, with fixed positive row sizes $n_i$. Let $N={\sum }_i{n}_i$, $K={\sum }_i{X}_i$ and assume $0<K<N$. Conditional on $K$, the probability mass function is the displayed multivariate hypergeometric distribution: in the joint likelihood, the factor $p^K(1-p{)}^{N-K}$ is common to all admissible tables and cancels. The Vandermonde identity gives the denominator, so the conditional distribution is free of the unknown nuisance parameter $p$.

For a table $x$, its Pearson chi-squared statistic isAn exact conditional p-value sums the displayed probabilities over all tables with the same margins and $Q(x)\ge Q(x_{\mathrm{obs}})$. The ordering is by the Pearson chi-squared statistic, rather than by the probability of an individual table; different exact-test orderings can give different answers. Enumeration is practical when $K$ and the number of rows are small. Monte Carlo tests can approximate the same tail by sampling tables with fixed margins.^[ref]

An exact arithmetic comparison is easy too. Let $M$ be the least common multiple of the row sizes. Compare the integersince every table has the same positive denominator $MK(N-K)$. This includes boundary ties without a floating-point tolerance. Conditional p-values are discrete and can be conservative; “exact” concerns their null calibration, not equality of rejection probability with every chosen significance level.

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.

For integers $a,b$ not both zero, their greatest common divisor is the largest positive integer dividing both. It is unchanged by replacing either input by its negative. The convention $\gcd (0,0)=0$ is useful, but this exceptional value is not a largest positive common divisor. For positive inputs, the Euclidean algorithm computes the answer, and Bézout's identity expresses it as an integer linear combination of the inputs.

For $12=2^2\cdot 3$ and $18=2\cdot 3^2$, a common divisor can contain at most one copy of the prime number two and one of the prime number three. Taking the smaller prime valuation at each prime number therefore givesThe check $6=18-12$ is also a Bézout's identity: every common divisor divides this difference, and six itself divides both inputs. More generally, every common divisor divides the greatest common divisor, a stronger statement than merely being no larger than it. The companion least common multiple takes the larger prime valuations, as the diagram there illustrates. For an application, divide the numerator and denominator of the fraction $12/18$ by six to obtain $2/3$; these remaining integers are coprime.

Up to group isomorphism, the finite groups with at most six elements are the trivial group, the cyclic groups $C_2,C_3,C_4,C_5,C_6$, the Klein four-group $C_2\times C_2$, and the symmetric group $S_3$.

A group of prime cardinality is a cyclic group, since Lagrange's theorem forces any nonidentity element to generate it. For four elements, either an element has order of a group element four, or every nonidentity element is an involution. In the latter case the group of exponent two is abelian identity shows that two distinct nonidentity elements $a,b$ generate $\{e,a,b,ab\}\cong C_2\times C_2$.

For a group of order six, either an element generates it or some element $a$ has order of a group element three: otherwise all nonidentity elements would be involutions, producing a four-element subgroup in contradiction with Lagrange's theorem. Pairing each element with its inverse element gives an involution $b$ outside $⟨a⟩$. The subgroup $⟨a⟩$ has index of a subgroup two and is a normal subgroup, so $ba{b}^{-1}=a$ or $a^{-1}$. The commuting case makes $ab$ have order of a group element six, whereas the second case gives the multiplication rules of $S_3$ on the six distinct elements $a^i,a^{i}b$, $0\le i<3$.

All these groups embed in $S_4$ except $C_5$ and $C_6$. The former is excluded by Lagrange's theorem; the latter is excluded because the disjoint cycle decomposition of a permutation of four letters cannot have least common multiple of cycle lengths equal to six.

For any group $G$, evaluation at a chosen generator of a group $x$ of $C_n$ gives a bijection between group homomorphisms $C_n\to G$ and elements satisfying $g^n=1$. A group homomorphism must send $x^j$ to $g^j$. Conversely, this formula is well-defined because exponents differing by a multiple of $n$ give equal powers, and it respects multiplication. The displayed correspondence is a bijection of sets; it is not claimed to be a group isomorphism for a nonabelian target. In a symmetric group, the order of a group element is the least common multiple of its disjoint cycle lengths, making this correspondence easy to enumerate.

An integer multiple of an integer $d$ is a product $dk$ with $k$ an integer; equivalently, $d$ is a divisor of that product. The integer multiples of $12$ are $\dots ,-24,-12,0,12,24,\dots$. Zero is an integer multiple of every integer, and the only integer multiple of zero is zero. Shared positive integer multiples lead to the least common multiple.

For positive integers $a,b$, their least common multiple is the smallest positive integer that is an integer multiple of both. Write it as $\mathrm{lcm}(a,b)$. A positive common integer multiple always exists, since $ab$ is one, but it can be larger than necessary.

For example, the positive integer multiples of $12$ begin $12,24,36,48,60,72$, while those of $18$ begin $18,36,54,72$. Their first positive coincidence is $36$, so $\mathrm{lcm}(12,18)=36$. Both also divide zero, but the word positive excludes zero from this minimum.

Suppose two events happen every twelve and eighteen days, and both happen at day $t=0$. Their next meeting is at day $36$, after three twelve-day intervals and two eighteen-day intervals. Through day $72$, their common event times are $0,36,72$.

The prime factorization explains why this coincidence occurs. For the integers $12$ and $18$,A common integer multiple must contain at least the prime valuations required by each input. Taking the larger prime valuation at each prime number meets both requirements with no extra factors. The greatest common divisor uses the smaller prime valuations instead. This is the same coordinate comparison developed under prime factorization, applied in opposite directions.

For any positive integers $a,b$, the prime valuations giveThe proof outline is one observation at each prime number: $\min (r,s)+\max (r,s)=r+s$. Hence the two sides have identical prime factorizations. Numerically, $6\cdot 36=12\cdot 18=216$. This also gives a calculation using the Euclidean algorithm for the greatest common divisor, without first finding the prime factors of both inputs.

Every positive common integer multiple is an integer multiple of the least common multiple, because its prime valuations must be at least the larger input prime valuations. Including negatives and zero, the common integer multiples of $12$ and $18$ are exactly $36k$ for integers $k$. For more than two positive integers, the same definition and rule of taking the largest prime valuations apply; one may also combine inputs successively. For example, $\mathrm{lcm}(12,18,20)=\mathrm{lcm}(36,20)=180$.

For nonzero signed integers, take absolute values: $\mathrm{lcm}(-12,18)=36$. We extend the definition to zero by the convention $\mathrm{lcm}(a,0)=0$, since zero is then the only common integer multiple; this is an extension, not a positive minimum. In particular $\mathrm{lcm}(0,0)=0$ must be handled separately from the displayed quotient, which would involve division by zero.

The least common multiple is useful for combining fractions with the smallest positive shared denominator. For example,Its scheduling interpretation requires care about starting times. If the events start at integer days $r$ and $s$, a common time must satisfy the integer congruences $t\equiv r(\mathrm{mod}12)$ and $t\equiv s(\mathrm{mod}18)$. The Chinese remainder theorem for noncoprime moduli says a solution exists exactly when $6\mid (r-s)$. If it exists, solutions form one congruence class modulo $36$, but the first meeting need not be day $36$. With starts $r=0,s=6$, the first meeting is day $24$ and subsequent meetings are $60,96,\dots$; with $r=0,s=1$, they never meet. The beauty of the least common multiple is the exact shared spacing, while the integer congruences determine whether and where the spacing begins.

Book VII, Proposition 34 of Euclid's Elements constructs the least common multiple of two numbers, and Proposition 36 extends the construction to three by first combining two of them. In modern notation this is $\mathrm{lcm}(a,b,c)=\mathrm{lcm}(\mathrm{lcm}(a,b),c)$. These are specific ancient treatments of the construction, rather than a claim about its first discovery. ^{[ref] [ref]}

Suppose the rational canonical form of $T$ is $C(f_1)\oplus \cdots \oplus C(f_r)$, with monic nonconstant invariant factors of a linear operator satisfying $f_1\mid \cdots \mid f_r$. Each block has minimal polynomial and characteristic polynomial $f_j$, because a cyclic operator has equal minimal and characteristic polynomials. The determinant of a block diagonal matrix is the product of block determinants, giving $c_T={\prod }_j{f}_j$. A polynomial kills the direct sum exactly when it kills each block, equivalently when every $f_j$ divides it. Thus $m_T$ is their least common multiple, which the divisibility chain reduces to $f_r$. On the zero vector space both polynomials are conventionally one.

Write the prime factorization of $m>1$ as $m=q_1\cdots q_t$, with each $q_j$ a positive power of a distinct prime number. The least $n$ such that $S_n$ contains a permutation of order $m$ is $q_1+\cdots +q_t$.

For existence, take disjoint permutation cycles of lengths $q_j$. Their order of a permutation is the least common multiple of those lengths, namely $m$. For minimality, start with the disjoint cycle decomposition of any permutation of order $m$. Assign each full prime-power factor $q_j$ to one cycle whose length is divisible by it; one exists because the least common multiple of all cycle lengths is $m$. The length of each cycle is at least the product of the factors assigned to it. For integers $a,b\ge 2$, $ab\ge a+b$, so a product of at least two assigned factors is at least their sum; the assertion is immediate for one factor. Summing over cycles gives at least ${\sum }_j{q}_j$ symbols. In particular an element of order $60=4\cdot 3\cdot 5$ requires at least twelve symbols.

If the order of a group element is $m$ for $g$ and $n$ for $h$, with both finite, thenexactly when both $m$ and $n$ divide $k$. The smallest positive such $k$ is their least common multiple, givingThis concerns the orders of the selected elements, which need not equal the orders of their entire groups. If either component has infinite order of a group element, no positive power can return the pair to the identity element, so the pair also has infinite order.

For example, in $C_4\times C_6$, the additive element $(2,3)$ has component orders $2,2$, hence pair order $2$. The element $(1,1)$ instead has order $\mathrm{lcm}(4,6)=12$. The product has $24$ elements, so even this latter element does not generate it. This distinguishes group order from order of a group element while exposing the simultaneous-return interpretation.

Let $T(N)$ count pairs $n,n+2$ both prime with $n+2\le N$. The Selberg sieve replaces primality by the necessary condition that the polynomial $F(n)=n(n+2)$ have no small prime divisor. Its strength is a nonnegative quadratic majorant with optimizable divisor weights; its limitation is that a sifted integer need not be prime.

For a prime $p$, let $\nu (p)$ count the forbidden residues of $n$ modulo $p$. We have $\nu (2)=1$, since the two roots coincide modulo two, and $\nu (p)=2$ for every odd prime, where the roots are zero and $-2$. The Chinese remainder theorem makes $\nu (d)$ multiplicative on squarefree integers. With $g(d)=\nu (d)/d$,These local densities constitute the sieve distribution for the twin-prime problem. Since ${\sum }_{p\le z}g(p)=2\log \log z+O(1)$, it is a dimension-two sieve, which is why the expected upper bound has two logarithms in the denominator.

Let $P(R)={\prod }_{p\le R}p$ and choose real Selberg sieve weights ${\lambda }_d$ supported on squarefree $d\le R$, with ${\lambda }_1=1$. If $\gcd (F(n),P(R))=1$, the only supported divisor of $F(n)$ is one. HenceExpanding and using the distribution of the polynomial roots givesHere $[d,e]$ denotes the least common multiple. The divisor-square support reaches $R^2$, although each individual weight is supported only to $R$; keeping these two levels distinct is essential for estimating the remainder.

The Selberg sieve diagonalization solves the main-term minimization exactly. On squarefree integers putMultiplicativity givesAlso, Möbius inversion gives ${\sum }_{r\le R}\mu (r)Y_r={\lambda }_1=1$. Therefore the Cauchy-Schwarz inequality proveswith equality at $Y_r=\mu (r)w(r)/G(R)$. Inverting the divisor sums gives the optimizing weightsIn particular ${\lambda }_1=1$ and $Q(\lambda )=1/G(R)$.

These weights have $|{\lambda }_d|\le 1$, which supplies a simple rigorous remainder estimate. Indeed, multiply the inner sum by ${\prod }_{p\mid d}(1-g(p){)}^{-1}={\sum }_{e\mid d}w(e)$. The terms are $w(em)$ for distinct squarefree integers $em\le R$ with $e\mid d$ and $(m,d)=1$, hence form a subset of the sum defining $G(R)$. Since $\nu ([d,e])\le \nu (d)\nu (e)$ and $\nu (d)\le \tau (d)$,Thus

For this sieve $w(2)=1$ and $w(p)=2/(p-2)$ for odd primes. Here is a direct proof that $G(R)\asymp {\log }^{2}R$, sufficient for the upper bound. PutThe Mertens theorem for reciprocal primes implies $W(z)\asymp {\log }^{2}z$, by taking logarithms and using the convergence of ${\sum }_{p}g(p{)}^2$. Give each divisor $d\mid P(z)$ probability $w(d)/W(z)$. Its expected logarithm isby the Mertens first theorem. With $z=R^{1/8}$ this is at most $\frac{1}{3}\log R$ for large $R$. The Markov inequality shows that at least two thirds of the total product weight has $d\le R$. These terms occur in $G(R)$, so $G(R)\gg W(R^{1/8})\gg {\log }^{2}R$. Conversely $G(R)\le W(R)\ll {\log }^{2}R$, proving the claim without treating an untruncated Euler product as a truncated divisor sum.

Choose, for example, $R=N^{1/4}$. Any twin-prime pair with smaller member greater than $R$ survives this sieve; pairs with smaller member at most $R$ contribute at most $O(R)$. ConsequentlyThe chosen level is deliberately enough to prove the correct logarithmic order; sharper level and remainder analyses improve the numerical upper-bound constant.

The local correction factor also explains the conjectured main-term constant. Relative to two independent primality conditions, the singular series isThe twin-prime constant $C_2$ is positive and convergent because its logarithm has an absolutely convergent tail. The factor two at $p=2$ records that only one parity is allowed, while each odd-prime factor records the two distinct forbidden residues. The Hardy–Littlewood twin-prime asymptotic conjecture predictsThis is a conjecture, not a consequence of the upper-bound calculation.

The parity problem in sieve theory is the obstruction to reversing the argument. The nonnegative square majorizes all survivors, including composites with sufficiently large prime factors; small-divisor information does not isolate the desired prime-factor parity or force both factors to be prime. Therefore the Selberg sieve establishes the correct upper-bound scale and the arithmetic local factors, but by itself does not prove a positive lower bound for twin primes, their infinitude, or the conjectured asymptotic.

The minimal polynomial $m_A$ is the monic polynomial of smallest degree satisfying $m_A(A)=0$. An annihilating polynomial exists, for example because $I,A,\dots ,A^{n^2}$ are linearly dependent in the $n^2$-dimensional space of matrices. A nonzero constant cannot annihilate $A$, so the minimal degree is positive.

If $p$ and $q$ are two such monic polynomials of minimal degree $d$, then $(p-q)(A)=0$ and $\mathrm{deg}(p-q)<d$ unless $p=q$. Minimality therefore forces $p=q$. Polynomial division also shows that $m_A$ divides every annihilating polynomial: the remainder after division would otherwise be an annihilator of smaller degree. This proves uniqueness rather than merely choosing one of several minimal-degree polynomials.

If $A$ is real, coefficientwise complex conjugation of $m_A(A)=0$ gives $\overline{m_A}(A)=0$. The conjugated polynomial is monic of the same degree, hence uniqueness gives $\overline{m_A}=m_A$. The minimal polynomial of a real matrix has real coefficients.

For $n\ge 3$, use the block diagonal matrixThe two-dimensional Jordan block is annihilated by $(t-1{)}^2$ but not by $t-1$, while the scalar block requires the factor $t+1$. A polynomial annihilates the direct sum exactly when it annihilates every block. Thus its minimal polynomial is the least common multiple $(t-1{)}^2(t+1)$. For $n=3$ the final identity block is omitted.

For every prime factor $p_i$ of $N$, Fermat's little theorem gives $a^{p_i-1}\equiv 1(\mathrm{mod}{p}_i)$. Since $p_i-1$ divides the least common multiple $\lambda (N)$, it follows that $p_i\mid a^{\lambda (N)}-1$. The primes are distinct and hence pairwise coprime, so their product divides this integer. ThusFor the specified product, $N=1729$ and $\lambda (N)=\mathrm{lcm}(6,12,18)=36$. Since $N-1=1728=48\cdot 36$, raising the preceding modular congruence to the forty-eighth power proves $a^{N-1}\equiv 1(\mathrm{mod}N)$ for every $a$ coprime to $N$. This is the defining phenomenon of a Carmichael number.