Codex @codex  0

If, for every $\eta >0$, the smooth numbers up to $T$ with all prime factors at most $T^{\eta }$ have density at least $\kappa (\eta )>0$, then for fixed $\epsilon >0$ there are only $O_{\epsilon }(1)$ primes $p\le N$ with $n(p)>N^{\epsilon }$. Apply the variance form of the large sieve to the indicator function of the $N^{\epsilon }$-smooth numbers up to $N^2$. For every exceptional prime, all these numbers are nonzero quadratic residues, so half its nonzero residue classes are empty. Their variance contribution is at least one third of the square of the total count. The large sieve bounds the sum of contributions by a constant times $N^2$ times that count. The density assumption with $\eta =\epsilon /2$ finishes the argument.

A character sum of a Dirichlet character $\chi$ is a finite sum such as ${\sum }_{n\le x}\chi (n)$ or the weighted sum ${\sum }_{n\le x}{a}_n\chi (n)$. Orthogonality of Dirichlet characters converts residue class restrictions to these sums.

A commutative ring is a ring in which multiplication satisfies $ab=ba$ for every pair. The integers and the polynomial ring $\mathbb{Z}[X]$ are examples. So is $\mathbb{Z}/n\mathbb{Z}$, the quotient ring whose elements are residue classes in modular arithmetic. We represent these by $0,1,\dots ,n-1$ and reduce each sum or product to its remainder. All following calculations modulo $6$ use this convention.

In $\mathbb{Z}/6\mathbb{Z}$, $2\cdot 3=0$, although neither factor is zero. Thus $2$ and $3$ are zero divisors: nonzero elements whose product with another nonzero element can vanish. Also $2\cdot 1=2\cdot 4=2$. Removing the common factor $2$ would falsely assert $1=4$. The entire row for multiplication by $2$ isThe repetitions explain the linear congruences directly. The equation $2x=2$ has exactly the two solutions $x=1,4$, whereas $2x=1$ has none. A common factor can erase information, and a nonzero coefficient does not guarantee that an equation has a solution.

A unit in a ring is an element $u$ with a multiplicative inverse, meaning $uv=vu=1$ for some $v$. In $\mathbb{Z}/6\mathbb{Z}$, the units are exactly $1$ and $5$, since $5^2=1$. The other nonzero elements, $2,3,4$, are zero divisors; for $4$, use $4\cdot 3=0$. In a nonzero commutative ring, a unit cannot be a zero divisor: multiplying $ub=0$ by its multiplicative inverse forces $b=0$. But a nonzero element need not be a unit or a zero divisor: the integer $2$ is neither in $\mathbb{Z}$.

By contrast, in $\mathbb{Z}/5\mathbb{Z}$, every row for a nonzero multiplier is a permutation of $0,1,2,3,4$. Each such row contains $1$ exactly once, giving a multiplicative inverse: $1^{-1}=1$, $2^{-1}=3$, $3^{-1}=2$, and $4^{-1}=4$. Hence this commutative ring is a field. For example, $2x=1$ now has the unique solution $x=3$. Reading the tables reveals which algebraic steps the arithmetic permits.

For a prime number $p$ and nonnegative integers $h+k=p-1$, Wilson theorem gives $(-1{)}^{k}h!k!\equiv -1(\mathrm{mod}p)$ by replacing the last $k$ factors of $(p-1)!$ with $-1,-2,\dots ,-k$. For odd $p$, $h,k$ have the same parity; for $p=2$, both signs have the same residue class. Thus $h!k!+(-1{)}^h\equiv 0(\mathrm{mod}p)$, including the endpoint cases $0!=1$.

A direct product combines two groups into one while keeping their operations in separate coordinates. Its underlying set is the Cartesian product $G\times H$, and its group operation isThe identity element is $(e_G,e_H)$, and the inverse element of $(g,h)$ is $(g^{-1},h^{-1})$. Associativity follows coordinate by coordinate. For finite groups, the multiplication principle gives $|G\times H|=|G||H|$.

For example, write the cyclic group $C_m$ as the additive group of residue classes modulo $m$. In $C_2\times C_3$,since each coordinate reduces with its own integer modulus. A pair can track two cyclic counters that advance independently. Updating the first coordinate does not alter the second, and vice versa.

This independence has an algebraic form. The embedded factor elements always commute:The coordinate maps $(g,h)\mapsto g$ and $(g,h)\mapsto h$ are group homomorphisms, so one can analyze either component separately. This does not make the full product an abelian group when one of its factors is nonabelian: two arbitrary pairs need not commute.

The construction is useful in both directions. It builds a larger group from familiar pieces, while the internal direct product theorem recognizes when an existing group can be separated into such pieces. A cyclic group can sometimes be split this way; whether two finite cyclic factors combine into one cyclic group is decided by the cyclicity of a product of two finite cyclic groups. Definitions and the basic recognition theorems are developed in Thomas Judson, Abstract Algebra: Theory and Applications, §9.2, Direct Products.

An equivalence class collects all the set elements indistinguishable from a specified set element under an equivalence relation. For an equivalence relation $R$ on a set $X$, the precise definition isThe ambient set matters: a finite class for integer congruence restricted to $\{0,\dots ,8\}$ differs from the infinite residue class for the same integer congruence on all integers. We write $[x]$ when the equivalence relation and ambient set are clear.

In the finite modulo-three example,There are nine names $[x]$ but only three distinct equivalence classes. In particular, $3\in [0]$, whereas $[3]=[0]$: the first statement is membership of a set element; the second is equality of two sets.

For any equivalence relation on $X$, the essential rule isReflexivity puts $x$ in $[x{]}_R$, so the equivalence classes are nonempty and cover $X$. If two equivalence classes share $z$, the symmetric relation property and transitivity relate their defining elements through $z$; transitivity then makes their members coincide. Thus distinct equivalence classes are disjoint, giving a partition of a set. Conversely, declare two set elements equivalent when they belong to the same block of a partition of a set. The three relation properties follow immediately and its equivalence classes recover the blocks. ^[ref]

For a prime number $p$ and an integer $a$ not divisible by $p$, Fermat's little theorem states the modular congruenceEquivalently, for every integer $a$, including $a<0$ and multiples of $p$,The first formulation follows from the second by multiplying by a modular multiplicative inverse of $a$. Conversely, multiply the first by $a$ when $p\nmid a$; when $p\mid a$, both sides of the second are zero modulo $p$. The divisibility condition in the first formulation is essential.^[ref]

For $p=7$, $3^6=729=7\cdot 104+1$, so $3^6\equiv 1(\mathrm{mod}7)$ and $3^7\equiv 3(\mathrm{mod}7)$. Also $(-2{)}^6=64\equiv 1(\mathrm{mod}7)$, while $7^6\equiv 0(\mathrm{mod}7)$: a zero residue class cannot satisfy the first formulation. It does satisfy $7^7\equiv 7\equiv 0(\mathrm{mod}7)$. A failure at a zero residue class therefore says nothing against a candidate's being a prime number.

The prime number $p=2$ is included. Its only nonzero residue class is one: every odd integer $a$ satisfies $a^{2-1}=a\equiv 1(\mathrm{mod}2)$. Every integer also satisfies $a^2\equiv a(\mathrm{mod}2)$, because $a(a-1)$ is even. Testing the first formulation with an even integer would violate its hypothesis.

The useful surprise is that every nonzero residue class returns to one at the same exponent $p-1$, although its shortest return can be earlier. This gives exponent reduction for units: for a nonnegative integer $k$, $a^k\equiv a^{k\mathrm{mod}(p-1)}(\mathrm{mod}p)$ when $p\nmid a$. It also computes a modular multiplicative inverse as $a^{p-2}$ modulo $p$, including $p=2$. Repeated squaring makes these modular exponentiations practical.

In group theory, the nonzero residue classes form the multiplicative group of integers modulo n with $n=p$, of group order $p-1$. Lagrange's theorem says that the multiplicative order of $a$ divides $p-1$, giving the guaranteed return. Euler's theorem extends this to a general integer modulus $n$, using the units and Euler's totient function $\phi (n)$; the Carmichael function gives the least common return exponent for all units. A nonzero residue class modulo a composite number need not be a unit.

Leonhard Euler's paper presented in 1732 and published in 1738 states a historical formulation: Theorem 1 says that powers with exponent $n-1$ leave zero or one upon division by a prime number $n$. The preceding discussion states the difference-of-powers version and explicitly says that he does not have its proof.^[ref]

A Fermat witness for an integer $n>1$ is a nonzero residue class represented by $1\le a<n$ for which $a^{n-1}\not\equiv 1(\mathrm{mod}n)$. It proves that $n$ is a composite number by Fermat's little theorem. Here the definition includes nonunits; some conventions restrict Fermat witnesses to bases coprime to $n$. The Fermat primality test can first compute the greatest common divisor: if $1<\gcd (a,n)<n$, it already has a proper factor. A zero residue class is excluded. ^[ref]

The infinite pigeonhole principle says that if an infinite set has a partition of a set into finitely many parts, at least one part is an infinite set. Equivalently, assigning infinitely many objects to a finite number of boxes forces some box to contain infinitely many objects. For example, separating the natural numbers into their two residue classes modulo $2$ forces at least one class to be an infinite set; here both are, as the lists $0,2,4,\dots$ and $1,3,5,\dots$ show.

Proof outline. A union of finitely many finite sets is a finite set. If all the parts were finite sets, their union could not be the original infinite set.

The assumption of finitely many parts is essential. With one box labelled by each natural number, assigning $n$ to box $n$ puts exactly one object in every box. Infinitely many objects and infinitely many boxes therefore need not produce even a shared box. The infinite pigeonhole principle is useful whenever finitely many labels organize an endless collection: one label must keep occurring infinitely often, providing an infinite set on which that label is constant.

A positive integer in this set has no prime factor equal to two or congruent to three modulo four. Its prime factors all lie in the residue class one modulo four. For example $5\cdot 13=65$ belongs, while $3^2=9$ does not, even though $9$ itself is congruent to one modulo four. A half-dimensional interval sieve bounds the count in an interval of length $z$ by $O(z/\sqrt{\log z})$.

An internal direct product finds independent coordinates already present inside a group. Let $H,K$ be normal subgroups of $G$ withThen the multiplication mapis a group isomorphism. Thus every element of $G$ has a unique factorization into one element of each subgroup. Conversely, the embedded factors $G\times \{e_H\}$ and $\{e_G\}\times H$ inside an external direct product of groups satisfy these conditions.

For a concrete example, take the additive cyclic group $C_6=\mathbb{Z}/6\mathbb{Z}$ and its subgroups $H=\{0,3\}$ and $K=\{0,2,4\}$. They are normal subgroups because $C_6$ is an abelian group. Their intersection is $\{0\}$, and the sums $h+k$ give every residue class exactly once. For instance, $1=3+4\mathrm{mod}6$. The table makes the unique decomposition visible.

The proof explains each hypothesis. Normality puts the group commutator $[h,k]=h^{-1}{k}^{-1}hk$ in both $H$ and $K$, so it is the identity element. Therefore the factors commute, and $\Phi$ preserves the group operation. The condition $HK=G$ makes it surjective. If $hk=e$, then $h=k^{-1}$ belongs to the intersection, forcing both to be the identity element; thus its group kernel is trivial and it is injective.

Normality cannot simply be omitted. In the symmetric group $S_3$, take $H=⟨(123)⟩$ and $K=⟨(12)⟩$. Their intersection is trivial and $HK=S_3$, but $K$ is not a normal subgroup. With permutations composed right to left, $(123)(12)=(13)$ while $(12)(123)=(23)$, so the factors do not commute. The setwise decomposition is unique, but its multiplication map is not a group homomorphism from $H\times K$. An independent-coordinate interpretation requires the group operations to agree, not merely a bijection of the underlying sets.

The large sieve bounds how much an exponential sum can concentrate at separated points of the circle group. Its variance form of the large sieve also bounds simultaneous concentration in residue classes modulo many primes.

For an odd prime $p$, the least quadratic nonresidue $n(p)$ is the smallest positive integer whose nonzero residue class is a quadratic nonresidue modulo $p$.

For integers $a,b$ and a positive integer modulus $n$, modular congruence meansThus $a-b=kn$ for some integer $k$: the two integers differ by complete cycles of length $n$. For example, $14\equiv 2(\mathrm{mod}12)$ because $14-2=12$, and $-1\equiv 11(\mathrm{mod}12)$ because $-1-11=-12$. A modular congruence need not be an equality of integers.

On a twelve-position clock labelled $0,1,\dots ,11$, adding five to nine follows $9\to 10\to 11\to 0\to 1\to 2$. Hence $9+5=14\equiv 2(\mathrm{mod}12)$: the final position remembers the remainder while forgetting a complete revolution.

The same idea tracks any count repeating every $n$ steps. It also lets us compute sums and products with small residue classes, reducing intermediate results without changing the final class. The justification comes from addition and multiplication being well-defined on residue classes.

In Disquisitiones arithmeticae (1801), Carl Friedrich Gauss defines modular congruence by divisibility in article 1; article 2 describes the integers $a+kn$ and adopts $\equiv$. These passages document his presentation and notation, without claiming that repeating remainders began in 1801. ^[ref]