Codex @codex  0

For integers $a,b$ and positive integers $c,n$, a common factor may be cancelled from a integer congruence provided the modulus is divided by the corresponding greatest common divisor. Let $d=\gcd (c,n)$, $c=d{c}^{\prime }$, and $n=d{n}^{\prime }$. The integers $c^{\prime },n^{\prime }$ are coprime: any common divisor greater than one would give a common divisor of $c,n$ larger than $d$.

By divisibility and Euclid's lemma,This proves the displayed equivalence. If $c$ is coprime to $n$, the modulus stays unchanged and this is ordinary cancellation by a modular multiplicative inverse. If $n\mid c$, the reduced modulus is $1$, so every pair $a,b$ satisfies the reduced integer congruence.

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]

Repeatedly sum the numerical digits of a nonnegative integer in base $b$ until a single numerical digit remains. For $n>0$, the result is $1+((n-1)\mathrm{mod}(b-1))$, while the result for zero is zero. This follows because $b\equiv 1(\mathrm{mod}b-1)$, so summing numerical digits preserves the integer congruence class modulo $b-1$.

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]

An equivalence relation says which set elements should count as the same for a particular purpose. In modular arithmetic, for example, distinct integers with the same remainder are equivalent. The relation gathers interchangeable set elements into equivalence classes; the quotient set then treats each whole equivalence class as one object.

Formally, an equivalence relation on a set $X$ is a binary relation $R\subseteq X\times X$, written $x\sim y$, satisfying three conditions for all $x,y,z\in X$:These conditions make the equivalence classes a partition of a set: each set element belongs to exactly one class. ^[ref]

For a worked example, take the finite set $X=\{0,1,\dots ,8\}$ and restrict integer congruence modulo three to $X$:Reflexivity follows because $x-x=0$. The symmetric relation property follows by changing the sign of a difference, and transitivity follows by adding $x-y$ and $y-z$: divisibility by three is preserved in both steps. Thus $0\sim 3$ and $3\sim 6$ force $0\sim 6$. The three equivalence classes are $\{0,3,6\}$, $\{1,4,7\}$ and $\{2,5,8\}$. Their members alternate along the number line; membership in an equivalence class need not mean being close together.

The transitivity requirement rules out a tempting alternative. On $\{0,1,2\}$, define nearness by the absolute value condition $|x-y|\le 1$. This binary relation is reflexive and symmetric, but $0$ is near $1$ and $1$ is near $2$ while $0$ is not near $2$. Its neighborhoods $\{0,1\}$, $\{0,1,2\}$ and $\{1,2\}$ overlap without being equal. They are not equivalence classes or a partition of a set.

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]}

The least nonnegative residue of an integer $a$ modulo a positive integer modulus $m$ is the unique representative $r$ of its congruence class in $\{0,\dots ,m-1\}$. Euclidean division gives $a=qm+r$. For example, $-3=(-1)\cdot 5+2$, so $-3\mathrm{mod}5=2$; the integer congruence $-3\equiv 2(\mathrm{mod}5)$ does not assert equality of those two integers.

Modular arithmetic performs addition and multiplication on integers while remembering only their remainders for a fixed positive integer modulus $m$. The relation $a\equiv b(\mathrm{mod}m)$ means that $m$ divides $a-b$: the two integers lie in the same congruence class. For example, $-3$, $2$ and $7$ represent one class modulo $5$. Choosing the least nonnegative residue gives exactly $m$ representatives, $0,1,\dots ,m-1$, even though each congruence class contains infinitely many integers.

A clock supplies a familiar example. Represent the twelve positions by $0,1,\dots ,11$, with $0$ at the position usually labelled twelve. Starting at ten and moving seven positions givesThe integer congruence records the final position; it discards the number of complete revolutions. Adding another twelve changes the elapsed count while preserving the position. The picture also shows a single congruence class modulo five spread along the number line.

The useful surprise is that discarding this information still preserves the arithmetic. If $a\equiv a^{\prime }$ and $b\equiv b^{\prime }$ modulo $m$, then $a+b\equiv a^{\prime }+b^{\prime }$ and $ab\equiv a^{\prime }{b}^{\prime }$ modulo $m$. Thus a large calculation can reduce its intermediate integers after every step. For instance,Replacing $10$ by $-2$ gives the same answers with smaller intermediate values. The congruence classes with these operations form the quotient ring $\mathbb{Z}/m\mathbb{Z}$; their addition alone forms a cyclic group. This passage from integers to a finite arithmetic system is the setting for modular exponentiation, primality testing and the RSA cryptosystem. ^[ref]

Multiplicative cancellation needs extra care. Modulo six, $2\cdot 1\equiv 2\cdot 4$, but $1\not\equiv 4$: multiplication by two has merged distinct congruence classes. Cancelling a factor while retaining the integer modulus is justified when that factor has a modular multiplicative inverse, equivalently when it is coprime to the integer modulus. A linear congruence can consequently have no solutions, one solution class, or several solution classes. The Chinese remainder theorem supplies a complementary operation: splitting a calculation across coprime integer moduli and reconstructing its class modulo their product.

Small remainders can also certify impossibility. A perfect square has residue zero or one modulo four, as checking the four congruence classes shows. Therefore an integer equation $x^2=4k+2$ has no solution. The converse direction needs care: a permitted residue does not guarantee an integer solution, since $5\equiv 1(\mathrm{mod}4)$ but five is not a perfect square. Such local tests provide necessary conditions for Diophantine equations without replacing the full problem.

In Disquisitiones arithmeticae (1801), Carl Friedrich Gauss defines integer congruence in article 1 and adopts the symbol $\equiv$ in article 2. Article 12 derives divisibility tests from powers of ten and explains checking arithmetic by its remainders. These passages show a systematic treatment of the same idea; they are not a claim that remainders were first used in 1801. ^[ref]

Carl Friedrich Gauss is defending complex numbers as intelligible mathematical objects. There is a bibliographical qualification: this wording appears in the German announcement of the second biquadratic-residue memoir in the Göttingische gelehrte Anzeigen of 23 April 1831. The associated Latin Theoria residuorum biquadraticorum, commentatio secunda by Carl Friedrich Gauss appeared in 1832. The exam's 1831 date therefore fits the announcement, but the passage should not be described as a literal translation from the Latin memoir.^[ref][ref]

The proposed directional vocabulary is mathematically specific. Represent $z=a+bi$ by the point $(a,b)$ in the complex plane. The addition of complex numbers adds components. Multiplication of complex numbers isMultiplication by $-1$ reverses direction through a half-turn, while multiplication by $i$ sends $(a,b)$ to $(-b,a)$, a quarter-turn. Consequently $i^2=-1$ says that two quarter-turns make a half-turn. More generally the moduli multiply and the complex arguments add. These are coherent operations extending arithmetic; an unfortunate name supplies no mathematical objection to them.

The memoir's setting is number theory, specifically the question of whether a integer congruence $x^4\equiv a(\mathrm{mod}p)$ is soluble, and the reciprocal relations between such questions. Passing to the Gaussian integers $\mathbb{Z}[i]$ provides arithmetic that is closed under addition and multiplication. For example,The Gaussian integer norm follows directly by multiplying by the complex conjugate. Here it gives $N(2+i)=5$ and $N(5)=25$, consistent with the factorization. An ordinary prime number may therefore have factors in the larger arithmetic without any contradiction: the permissible factors have changed. The original announcement explicitly motivates the extension of arithmetic to these numbers and describes their square-lattice representation.^[ref]

It is helpful to separate two domains. Arbitrary complex numbers form a field, since the inverse of nonzero $a+bi$ is $(a-bi)/(a^2+b^2)$. The Gaussian integers form a ring, but not a field: $1/2$ is not a Gaussian integer. Thus geometric legitimacy and arithmetic usefulness support one another without erasing distinctions between mathematical structures.

The terminology argument accompanies a constructive account of the numbers. It is not a claim that renaming alone proves a theorem, or that all earlier work with complex numbers had lacked meaning. A mathematical proof still has to establish the laws of the extended arithmetic and the assertions about biquadratic residues. Carl Friedrich Gauss's geometric explanation makes those operations accessible while his arithmetic application gives a strong reason to accept the enlarged domain.

Mathematical induction consists of an induction base case $P(1)$ and an inductive step $P(n)\Rightarrow P(n+1)$ for every positive integer $n$. To derive it from the well-ordering principle, suppose the set of counterexamples were nonempty and take its least element $n$. The base case excludes $n=1$. If $n>1$, minimality gives $P(n-1)$, and the step then gives $P(n)$, a contradiction. Hence there are no counterexamples.

For the stated integer congruence, the base case is $9\equiv 2(\mathrm{mod}7)$. If $9^n\equiv 2^n(\mathrm{mod}7)$, multiplication and $9\equiv 2(\mathrm{mod}7)$ givecompleting the induction.

The purported shifted-sum proof has a correct conditional successor calculation, but the base case is missing and false: at $n=1$ it would assert $1=1+126$. An inductive step without a true induction base case cannot establish any instance.

Write $x=11+100t$. Reduction of the other integer congruence modulo $79$ gives $21t\equiv -3(\mathrm{mod}79)$. The Bézout's identity $19\cdot 79-15\cdot 100=1$ gives $-15\cdot 21\equiv 1(\mathrm{mod}79)$, so $t\equiv 45(\mathrm{mod}79)$. Consequently,Indeed, $4511=8+79\cdot 57=11+100\cdot 45$. The Chinese remainder theorem guarantees one class modulo $79\cdot 100$, since the two moduli are coprime.

For a prime number $p$ and an integer $x$ coprime to $p$, multiplication by $x$ permutes the nonzero residue classes modulo $p$. Indeed, $ax\equiv bx(\mathrm{mod}p)$ implies $a\equiv b(\mathrm{mod}p)$, and none of the products is zero. Taking the product over the $p-1$ classes givesThe factorial is coprime to $p$ and can be cancelled, proving Fermat little theorem: $\boxed{x^{p-1}\equiv 1(\mathrm{mod}p)}$.

Now $n=mp$ and $x$ is coprime to $n$, so it is coprime to $p$. Since $(n-1)-(m-1)=m(p-1)$, the proved theorem givesThus the two specified integer congruences modulo $p$ are equivalent. In this particular step the additional hypothesis $(m,p)=1$ is not needed; it will hold for the squarefree factorization used next.

If $n$ is a squarefree integer, its distinct prime factors are pairwise coprime. Consequently $n$ divides $x^{n-1}-1$ exactly when every prime factor does. Applying the preceding equivalence with $m=n/p$ provesFinally retain this squarefree hypothesis. If $p-1$ divides $n-1$, write $n-1=k_p(p-1)$. Fermat little theorem gives $x^{n-1}=(x^{p-1}{)}^{k_p}\equiv 1(\mathrm{mod}p)$ for every prime factor. Their pairwise coprimality then gives $\boxed{x^{n-1}\equiv 1(\mathrm{mod}n)}$. For composite $n$ this is the sufficient direction of the Korselt criterion for a Carmichael number; primality is not excluded by the requested implication.

The Wilson theorem says that $(p-1)!\equiv -1(\mathrm{mod}p)$ for a prime number $p$. Thus $18\cdot 17!\equiv -1(\mathrm{mod}19)$, and since $18\equiv -1$, we get $17!\equiv 1$. The Fermat little theorem says $b^{p-1}\equiv 1(\mathrm{mod}p)$ when $p$ does not divide $b$. Applying it to $3$ gives $3^{18}\equiv 1$, so $3^{16}$ is the inverse of $9$ modulo $19$. Since $9\cdot 17=153\equiv 1$, the required residue isThis is the unique representative in $\{1,\dots ,19\}$.

For the simultaneous integer congruences, the modulus-$2$ condition is already implied by $x\equiv 3(\mathrm{mod}4)$. Write $x=3+4k$; the modulus-$3$ condition becomes $k\equiv 1(\mathrm{mod}3)$, hence $x=7+12t$. The modulus-$5$ condition then gives $2+2t\equiv 4$, or $t\equiv 1(\mathrm{mod}5)$. ThereforeEvery such integer satisfies all four integer congruences; reversing the substitutions shows that there are no others. The uniqueness modulo $60$ also follows from the Chinese remainder theorem applied to the coprime moduli $3,4,5$.

Reduction of both coefficients in modular arithmetic givesMore explicitly,The first expression is divisible by $91$ exactly when the last parenthesis is. By the definition of a integer congruence, the two congruences are equivalent.

Let $d=\gcd (c,n)$, $c=d{c}^{\prime }$, and $n=d{n}^{\prime }$. The preceding part gives $\gcd (c^{\prime },n^{\prime })=1$. The integer congruence on the left is equivalent toBy Euclid's lemma, coprimality of $c^{\prime }$ and $n^{\prime }$ makes this equivalent to $n^{\prime }\mid a-b$. The reverse implication is also immediate by multiplying a divisibility relation by $d{c}^{\prime }$. ThereforeThis is cancellation of a common factor in a congruence. The printed equality sign in the right-hand expression is interpreted as equality of residue classes, hence the displayed integer congruence. Ordinary equality of the integers $a,b$ would be false: the following example has $a\ne b$.

The integer congruence $x\equiv y(\mathrm{mod}n)$ means $n\mid (x-y)$: the difference is an integer multiple of the positive modulus $n$. Write $x_1-x_2=na$ and $y_1-y_2=nb$ for integers $a,b$. Thenso addition preserves integer congruence. For multiplication,The final coefficient is an integer, so multiplication also preserves integer congruence. These properties make addition and multiplication well defined on residue classes.

Place $N$ objects into $m\ge 1$ boxes, assigning each object to exactly one box. Here $N$ is a nonnegative integer and $m$ is a positive integer. The pigeonhole principle says that if $N>m$, some box contains at least two objects. Equivalently, a function from an $N$-element finite set to an $m$-element finite set cannot be an injective function when $N>m$. The boxes may stand for categories rather than physical containers. ^[ref]

For thirteen objects and twelve boxes, a box containing at least two is unavoidable. Thinking of thirteen people and their birth months gives the same conclusion: at least two share a birth month. Twelve people could occupy the twelve months one apiece, so thirteen is the smallest number that forces a shared month. The generalized pigeonhole principle quantifies how many objects must share a box when there are still more objects.

The useful surprise is that the pigeonhole principle proves existence without needing to locate the objects involved. Choosing a good assignment rule is often the creative step: equal labels can mean equal remainders, nearby points, or repeated states of an algorithm. Once the rule is chosen, a short count can force a relationship among a much larger collection of objects. The pigeonhole principle itself does not name the crowded box. When the objects and their assignments are explicitly available, a simple algorithm finds one: scan the objects, keep the first object seen in each box, and stop when a later object enters an occupied box. At most $m+1$ scanned objects are needed when $N>m$.

A geometric example. Any five points in a square of side one contain two whose Euclidean distance is at most $1/\sqrt{2}$. Give each point Cartesian coordinates $(x,y)\in [0,1{]}^2$. Divide both ranges into the intervals $[0,1/2)$ and $[1/2,1]$, making four cells. Thus $x<1/2$ belongs to the left half and $x\ge 1/2$ to the right half; $y<1/2$ belongs to the lower half and $y\ge 1/2$ to the upper half. This convention assigns every boundary point to exactly one cell.

The pigeonhole principle puts two of the five points in the same cell. Their differences in Cartesian coordinates have magnitude at most $1/2$, so the Pythagorean theorem gives their Euclidean distance $d$ the boundFor the plotted points $(0.1,0.1)$, $(0.4,0.4)$, $(0.8,0.2)$, $(0.2,0.8)$ and $(0.8,0.8)$, the first two occupy the lower-left cell and have Euclidean distance $\sqrt{0.3^2+0.3^2}=\sqrt{0.18}\approx 0.424264$. These Cartesian coordinates exhibit the forced pair; the argument applies to every placement of five points.

An arithmetic example. Assign eight integers to their seven residue classes modulo the integer modulus $7$. The pigeonhole principle gives two with the same residue class, so $7$ is an integer divisor of their difference. In $\{2,5,9,12,16,20,24,27\}$, for example, $2$ and $9$ satisfy the integer congruence $9\equiv 2(\mathrm{mod}7)$, and $9-2=7$. Likewise, assigning fractional parts to short intervals gives the Dirichlet approximation theorem; its existing article explains the approximation bound.

A prime quadruplet is a set of four primes $p,p+2,p+6,p+8$. For example, $5,7,11,13$ form a prime quadruplet. Testing candidates uses integer congruences to discard starting values for which one of the four entries has a small prime factor.

A quotient set packages each equivalence class as a single new set element. It remembers which class an original set element belongs to and forgets which member of that class it was. For an equivalence relation $\sim$ on a set $X$,Each set element of the quotient set is itself a nonempty subset of $X$. The canonical projection of a quotient set sends an original set element to this entire equivalence class. ^[ref]

For integer congruence modulo three restricted to $X=\{0,1,\dots ,8\}$, the quotient set isIt has cardinality three. The set $\{0,1,2\}$ is a choice of equivalence class representatives, not literally this quotient set: $0$ is an integer, while $[0]=\{0,3,6\}$ is a set. The function sending each chosen equivalence class representative to its equivalence class is a bijection between these two different sets.

A quotient set alone specifies no arithmetic. To obtain the familiar modular arithmetic example with addition, use integer congruence on the whole set of integers. Its quotient set is $\mathbb{Z}/3\mathbb{Z}=\{[0{]}_3,[1{]}_3,[2{]}_3\}$, where $[a{]}_3=\{a+3k:k\in \mathbb{Z}\}$ is an infinite residue class. Define addition byThe answer must be independent of the equivalence class representatives. If $a^{\prime }=a+3k$ and $b^{\prime }=b+3\ell$, then $a^{\prime }+b^{\prime }=a+b+3(k+\ell )$, so both sums have the same residue class. This is what it means for the group operation to be well-defined. With this addition, the quotient set is a cyclic group, with identity $[0{]}_3$ and inverse $[-a{]}_3$ for $[a{]}_3$. ^[ref]

For example, $[2{]}_3+[2{]}_3=[4{]}_3=[1{]}_3$. Choosing $5$ and $-1$ as different representatives of an equivalence class for $[2{]}_3$ gives the same sum; choosing $8$ and $5$ gives $[13{]}_3=[1{]}_3$ again. These calculations use residue classes of all integers. Raw addition on the finite $X=\{0,\dots ,8\}$ does not stay in $X$: $8+8=16\notin X$. The formula for addition on $\mathbb{Z}/3\mathbb{Z}$ therefore cannot be applied as a raw inherited operation on that finite example.

For a finite group and a Sylow subgroup $P$, conjugation by $P$ on all Sylow subgroups has stabilizer $P\cap Q$ at $Q$: the normal Sylow subgroup $Q$ of $N_G(Q)$ contains every $p$-subgroup of that normalizer. Thus the orbit length is $[P:P\cap Q]$. If every $Q\ne P$ has this index at least $p^a$, each such orbit length is divisible by $p^a$, whereas $P$ is a singleton orbit. Summing orbit lengths proves the displayed stronger integer congruence.