Codex @codex  0

Every nonnegative integer is a sum of squares with four terms, with zero terms allowed. Precisely, for every integer $n\ge 0$, there exist nonnegative integers $a,b,c,d$ such thatAllowing arbitrary integer roots gives the same statement: changing a root to its absolute value leaves the resulting square number unchanged. Four is a uniform upper bound on the number of nonzero terms, rather than a demand for four positive terms. Repeated square numbers are allowed. Conrad states the positive case and explicitly explains the role of zero terms; $n=0$ follows by taking all four roots zero. ^[ref]

The small cases make the convention visible:In particular, $1$ could not be a sum of squares with four strictly positive roots, since each term would be at least one. Geometrically, a square of integer side length $a$ has area $a^2$: the theorem says that any nonnegative whole-number total area can be split into at most four such square areas. It does not assert that those squares tile one larger square or a prescribed rectangle.

Why does the fourth term matter? Two square numbers do not suffice for $3$: in modular arithmetic, a square number has remainder zero or one modulo four, so their sum cannot be three modulo four. The sum of two squares theorem gives a complete criterion for the positive integers representable with two terms. Even three terms leave gaps. A square number has remainder $0,1,$ or $4$ modulo eight; adding three of these, with repetition allowed, never gives seven modulo eight. Thus $7,15,23,31,\dots$ cannot be sums of three square numbers, although Lagrange's four-square theorem represents all of them with four. This also proves that the bound four cannot be reduced to three.

The modulo-eight obstruction is not the only way that three terms can fail. For example, $28$ needs four: if three square numbers added to $28$, their remainders modulo four would force all three roots even. Dividing by four would then express $7$ as a sum of three square numbers, contradicting the preceding calculation. These short checks explain the examples without requiring a full classification of sums of three square numbers.

The practical benefit of Lagrange's four-square theorem is an existence guarantee for a family of Diophantine equations: for every nonnegative integer $n$, the displayed equation has an integer solution. It does not specify a unique solution. For instance, $65=8^2+1^2+0^2+0^2=7^2+4^2+0^2+0^2=6^2+4^2+3^2+2^2$. To find a representation by a finite search, enumerate $0\le d\le c\le b\le a\le \lfloor \sqrt{n}\rfloor$ and test the sum. The floor function supplies a finite bound because no single term can exceed $n$, and sorting roots removes duplicate orderings without discarding any possible sum. The theorem guarantees that the search succeeds.

A greedy algorithm that repeatedly subtracts the largest available square number need not find four terms: for $23$ it chooses $16+4+1+1+1$, while $23=9+9+4+1$ uses four. The appeal of the theorem is this gap between local choices and a global promise: individual square numbers become farther apart, and two or three terms leave arithmetic obstructions, yet four terms cover every nonnegative integer.

For historical orientation, Conrad dates Lagrange's four-square theorem to $1770$ and identifies the memoir as Démonstration d'un théorème d'arithmétique: it appeared in the Berlin Academy's volume for the year $1770$, published in $1772$, pages $123$–$133$. Keeping the volume year and publication year distinct avoids an apparent conflict between dates. ^[ref]

A least-significant-digit radix sort processes numerical digits from smallest to largest place value. Fix integers $R\ge 2$ and $d\ge 1$, and take $n$ complete sorting records whose sort keys satisfy $0\le k<R^d$. Use exactly $d$ positions in positional notation with radix $R$, including leading zeros. At pass $j=0,\dots ,d-1$, apply a stable digit sort to the current array usingThe floor function selects the integer quotient, and the remainder selects the current numerical digit. Move the complete sorting record, including its associated data. There are exactly $d$ passes, so this procedure terminates even for an empty array. The radix sort suffix invariant supplies its algorithm correctness argument.

For an original input, let the letters identify the attached data:Here $R=10$, $d=3$, and leading zeros only align place values; $005$ represents the integer five. The exact pass ledger is:After the units pass, the numerical digits are $0,2,4,5,5,7,7,7$. The ties retain $C$ before $F$ and $B$ before $E$ before $G$. This array is not yet ordered by its whole integer sort keys: $314$ still precedes $305$. After the tens pass, the two-position suffixes are $05,05,14,17,27,27,40,42$. In particular, $217_E$ now precedes $027_B$: their tens numerical digits differ, so stable sorting does not require retaining their previous order. The hundreds pass produces the final sorted array, with all attached letters preserved.

A linear congruence asks for the integers $x$ satisfying $ax\equiv b(\mathrm{mod}n)$, where $a,b$ are integers and $n>1$. Let $d=\gcd (a,n)$ be their greatest common divisor. There are solutions exactly when $d$ divides $b$. When solutions exist, there are exactly $d$ solution classes modulo $n$, obtained from one solution $x_0$ byThe divisibility condition follows immediately from $ax-b=kn$: every common divisor of $a,n$ must divide $b$. Conversely, Bézout's identity constructs a solution when $d\mid b$. Differences between any two solutions obey $n\mid a(x-x_0)$, equivalently $n/d\mid x-x_0$, since $a/d$ and $n/d$ are coprime. This explains both the spacing and the number of solution classes.

For a complete example, solve $6x\equiv 9(\mathrm{mod}15)$. Here $d=3$ divides nine. Dividing the corresponding divisibility statement by three changes the integer modulus too:Because $2\cdot 3\equiv 1(\mathrm{mod}5)$, multiplying by the modular inverse three gives $x\equiv 9\equiv 4(\mathrm{mod}5)$. Lifting this class back to modulus fifteen yields $x\equiv 4,9,14(\mathrm{mod}15)$. Direct substitution gives $24$, $54$ and $84$, each with remainder nine after division with remainder by fifteen. By contrast, $6x\equiv 10(\mathrm{mod}15)$ has no solutions, because three does not divide ten.

This is why ordinary-looking division cannot be performed blindly in modular arithmetic. Reducing the equation and its integer modulus together keeps all solutions; retaining modulus fifteen after dividing by three would lose valid classes. When $d=1$, the modular inverse of $a$ exists and gives a unique class $x\equiv a^{-1}b(\mathrm{mod}n)$. The Euclidean algorithm computes the Bézout coefficients needed for this construction. ^[ref]

Repeated division with remainder that determines successive digits of a quotient. To generate the fractional digits in base $b$, multiply the current remainder by $b$, divide by the denominator, and keep the resulting remainder for the next step.

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]

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]

Modular exponentiation computes the remainder $a^n\mathrm{mod}m$ for an integer base $a$, a nonnegative integer exponent $n$, and, here, an integer modulus $m\ge 2$. It applies exponentiation by squaring while reducing after each multiplication, including each squaring. The result is the unique representative in $\{0,\dots ,m-1\}$. There is no requirement that the base be coprime to the modulus when the exponent is nonnegative.^[ref]

Take $a=2$, $n=13=(1101{)}_2$, and $m=17$. Initialize $r=2$; the remaining digits giveHence $2^{13}\mathrm{mod}17=15$. The final operation multiplies $16$ by $2$, since the preceding square has already been reduced. The computation never needs to construct $2^{13}=8192$.

In general reduce the base first, $x=a\mathrm{mod}m$. For $n>0$, initialize $r=x$ and process the remaining binary digits with $r\leftarrow r^2\mathrm{mod}m$, followed, for a digit one, by $r\leftarrow rx\mathrm{mod}m$. The loop invariant iswhere $p$ is the processed prefix value. The congruence is preserved because modular arithmetic respects multiplication: if $u\equiv v(\mathrm{mod}m)$, then $u^2\equiv v^2$ and $ux\equiv va(\mathrm{mod}m)$. Thus changing representatives never changes the final congruence class.

Both factors in every product are less than $m$, so the unreduced product is less than $m^2$, and the stored result is again less than $m$. The same bounds hold for a gigantic exponent, such as $n=2^{1000}$: there are $1000$ squarings, each on bounded-size residues. For base two, the corresponding ordinary power would have $2^{1000}+1$ binary digits. The benefit is avoiding the huge ordinary power altogether, rather than constructing it and taking one final remainder. Initial reduction is essential when the supplied base is much larger than the modulus.

For $n=0$, return $1$ under the same empty-product convention as exponentiation by squaring. For $n=-k<0$, require $\gcd (a,m)=1$, find the modular multiplicative inverse $a^{-1}\mathrm{mod}m$, and compute $(a^{-1}{)}^k\mathrm{mod}m$; the extended Euclidean algorithm can find that inverse. Its cost is separate from the positive-exponent binary powering multiplication count. For example, $2^{-1}\equiv 9(\mathrm{mod}17)$, while $2^{-1}\mathrm{mod}4$ is undefined because $2$ and $4$ are not coprime.

A reversible computation gives the coherent quantum modular exponentiation used in quantum order finding and discrete-logarithm Fourier sampling.

Computing the remainder $ab\mathrm{mod}m$ while working with bounded integer representatives. Repeated doubling and addition can avoid forming an overflowing product: process the binary digits of $b$, double the current contribution modulo $m$, and add it to the result whenever the current binary digit is 1. The additions themselves must also use an overflow-safe implementation.

An integer is odd when it is not divisible by two.

For an $n$-bit unsigned dividend $a$ and positive divisor $b$, read the dividend bits from most to least significant. If the processed prefix is $p$, maintain $p=bQ+R$ with $0\le R<b$. Appending bit $d$ gives trial remainder $T=2R+d$; append quotient bit $[T\ge b]$ and replace the remainder by $T-b[T\ge b]$. This preserves the quotient–remainder identity.

The old dividend and new quotient can share one $n$-bit processor register: after $k$ iterations its value is $(a{2}^k\mathrm{mod}{2}^n)+Q_k$, where $Q_k<2^k$. The shifted dividend occupies the upper positions and the accumulated quotient occupies the lower positions, so no information is overwritten. The high processor register holds $R_k$. For an $n$-bit dividend the next trial remainder is no larger than the next prefix, hence fits in $n$ bits through the final iteration. This last bound is specific to the dividend width; it must not be assumed for unrestricted multiword dividends.

Paging divides an address space into fixed-size memory pages and main computer memory into equally sized page frames. Here assume byte addressing, one memory page size $P=2^b$ bytes, and an unsigned virtual address $v$. Its virtual page number $q$ and offset $d$ areThe brackets denote the floor function, and $\mathrm{mod}$ gives the remainder in Euclidean division. If the page table maps $q$ to physical frame number $f$ and permits the access, the physical address isThe low $b$ bits are unchanged; the other bits select the memory page or page frame. A bit shift and bit mask can extract these fields. ^[ref]

For a 16-bit virtual address and $P=256=2^8$ bytes, take $v=0x1234=4660$ in hexadecimal. Then $q=18=0x12$ and $d=52=0x34$. A mapping to $f=7=0x07$ givesThus the eight high bits choose a mapping; the eight low bits choose the same position in the resulting page frame. The 256-byte size is for illustration, not a claim about an actual architecture's supported memory page sizes.

The useful freedom is that adjacent memory pages can occupy unrelated page frames. In the diagram, virtual pages 0x12 and 0x13 occupy page frames 0x07 and 0x02; virtual addresses 0x12ff and 0x1300 are consecutive, but translate to physical addresses 0x07ff and 0x0200. Uniform units simplify placement and page replacement, at the cost of page table storage and unused bytes within partly filled memory pages. For example, placing 300 bytes in exclusive 256-byte page frames requires two page frames, leaving $512-300=212$ bytes unused.

The parity of an integer records whether it is divisible by two.

With its default argument and a nonnegative integer input, it prints the decimal digits of $n$ in order, one per line. For example, mystery4(407) prints 4, then 0, then 7. Integer division removes the final digit, recursion handles the preceding digits, and the remainder gives the final digit. The function returns None.

There is a subtlety for a nondefault base: the recursive call omits m, so it resets to $10$. For $m\ge 2$ and $n\ge m$, the actual output is the decimal digits of $\lfloor n/m\rfloor$, followed by the remainder $n\mathrm{mod}m$. For example, mystery4(13, 2) prints 6, then 1, rather than the binary digits of $13$. Passing m on to the recursive call would give a consistent base-$m$ positional notation. The interpretation as digits assumes $n\ge 0$ and $m\ge 2$; arbitrary integer arguments need not satisfy those conditions.

At any division step $u=qv+r$, an integer divides both $u,v$ exactly when it divides both $v,r$: one direction uses $r=u-qv$, and the other uses $u=qv+r$. HenceStarting with $r_0=a$, $r_1=b$, the Euclidean division producesThe nonzero remainders form a strictly decreasing sequence of positive integers. Such a sequence must terminate, since there are only finitely many positive integers below $b$. Suppose $r_N$ is the last nonzero remainder, so $r_{N+1}=0$. The unchanged greatest common divisor at each step givesThe final equality holds because the positive common divisors of $r_N$ and $0$ are precisely the positive divisors of $r_N$. This proves both termination and correctness of the Euclidean algorithm.

The divisions in the Euclidean algorithm areThe last nonzero remainder is $17$, soAs a check, $323=19\cdot 17$ and $187=11\cdot 17$; back-substitution also gives $17=-4\cdot 323+7\cdot 187$.

First recall why the two-variable Bézout's identity follows from the Euclidean algorithm. The initial values $a,b$ are integer linear combinations of $a,b$. At every subsequent step, $r_{j+1}=r_{j-1}-q_j{r}_j$ is again an integer linear combination of $a,b$. Therefore the last nonzero remainder, which is their greatest common divisor, has that form.

Put $e=\gcd (a,b)$. The preceding argument supplies integers $u,v$ with $e=au+bv$. Applying the same argument to $e,c$ gives integers $p,q$ such thatAn integer divides $a,b,c$ exactly when it divides $e,c$: if it divides $a,b$, it divides $e=au+bv$, while $e$ itself divides both $a,b$. Hence $\gcd (e,c)=\gcd (a,b,c)=d$. Substituting the expression for $e$ provesThusare integers satisfying $ax+by+cz=d$. This also explains how to construct the coefficients using two applications of the Euclidean algorithm.

The successive division with remainder steps of the Euclidean algorithm areEach step preserves the greatest common divisor by part (a). The final nonzero remainder is $9$, so

For an odd prime $p$, Euler's criterion statesFor $p\nmid a$, the Legendre symbol is $1$ for a quadratic residue and $-1$ for a quadratic nonresidue; if $p\mid a$, both sides are zero.

The product is a single power because the arithmetic progression of exponents has sum $2017\cdot 2018/2$:Since $2017\equiv 1(\mathrm{mod}8)$, the second supplementary law for quadratic reciprocity gives $(2/2017)=1$. Hence Euler's criterion gives $2^{1008}\equiv 1(\mathrm{mod}2017)$. Reduce the exponent using $1009=1008+1$ and $2017=2\cdot 1008+1$:The least nonnegative remainder is therefore $2$.

Equality of remainders after division by eight is a Euclidean relation. If $x$, $y$ have the same remainder and $x$, $z$ have the same remainder, then $y$, $z$ have the same remainder. In the notation of modular arithmetic,Hence

In the intended range $0\le k\le n$, division by the positive binomial coefficient $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ givesConsequently the intended remainder isThere is a necessary qualification to the printed unrestricted domain. If binomial coefficients outside $0\le k\le n$ are extended by zero, then every $k>n$ satisfies $g(k)=\left(\genfrac{}{}{0ex}{}{n}{k}\right)=0$, regardless of $n\mathrm{mod}3$. For example, $n=3,k=4$ satisfies the literal equality but has $n\mathrm{mod}3=0$. Thus the literal extended-domain premise alone does not determine a remainder; the boxed conclusion requires $0\le k\le n$, or equivalently here $\left(\genfrac{}{}{0ex}{}{n}{k}\right)\ne 0$.