Codex @codex  0

The 2-adic absolute value is the p-adic absolute value for the prime number $p=2$. It is defined on the rational numbers by $|x{|}_2=2^{-v_2(x)}$ for $x\ne 0$ and $|0{|}_2=0$, and extends to their P-adic number completion ${\mathbb{Q}}_2$. For a nonzero integer, count factors of two until the remaining factor is odd; for a rational number, subtract the denominator's count from the numerator's count.

The associated metric reverses a familiar comparison:Although $13$ is eight units from $5$ on the ordinary number line, it agrees with $5$ modulo $8$, whereas $6$ already disagrees modulo $2$. The 2-adic absolute value measures that agreement. The value $|3/8{|}_2=8$ also shows why this Non-Archimedean absolute value must be distinguished from the ordinary absolute value $|3/8|=3/8$.

In the left panel, differences farther from the diagonal grow in ordinary absolute value. In the right panel, nonzero even differences are closer than odd differences, and each further factor of two halves the 2-adic absolute value. The highlighted pairs have opposite distance rankings. The repeated pattern is the nested congruence class structure of an ultrametric space, visible without adding any new points.

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]

A complete residue system modulo a positive integer $m$ contains exactly one representative of every congruence class modulo $m$. Both $\{0,\dots ,m-1\}$ and $\{1,\dots ,m\}$ are examples. Counting the representatives that are coprime to $m$ gives Euler's totient function; those representatives form a reduced residue system.

The congruence class of $a$ modulo a positive integer $N$ is $\{a+Nk:k\in \mathbb{Z}\}$. Two integers have the same class exactly when their difference is divisible by $N$. Addition and multiplication of representatives descend to well-defined operations on $\mathbb{Z}/N\mathbb{Z}$, because replacing a representative by a multiple-of-$N$ translate changes the result by a multiple of $N$.

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

A deterministic finite automaton has exactly one automaton transition for every automaton state and input symbol. Formally, a DFA is a tuple $(Q,\Sigma ,\delta ,q_0,F)$: $Q$ is a nonempty finite set of automaton states, $\Sigma$ a finite alphabet, $\delta :Q\times \Sigma \to Q$ a function, $q_0$ the initial automaton state, and $F\subseteq Q$ the accepting automaton states. Its unique path on a word accepts if it ends in $F$ after consuming the entire input. Visiting $F$ earlier does not suffice.

For a concrete binary divisibility automaton, recognize the words whose values in the binary numeral system are divisible by three. Choose $Q=\{0,1,2\}$, $\Sigma =\{0,1\}$, $q_0=0$, and $F=\{0\}$. Each automaton state names the congruence class of the integer read so far. Appending a binary digit $b$ changes its value $n$ to $2n+b$, so the automaton transition isThe modular arithmetic therefore needs only three automaton states, whatever the input length. The full function is $\delta (0,0)=0$, $\delta (0,1)=1$, $\delta (1,0)=2$, $\delta (1,1)=0$, $\delta (2,0)=1$, and $\delta (2,1)=2$.

For $110_2=6$, the successive automaton states are $0\to 1\to 0\to 0$, so the word is accepted. For $101_2=5$, they are $0\to 1\to 2\to 2$, so it is rejected. Leading zeros are allowed: they leave the initial automaton state unchanged. We explicitly assign value zero to the empty word, which is accepted because the initial automaton state is accepting. This is a convention for a formal language, rather than a claim that ordinary written numerals include a blank numeral.

The generator checks every word of up to eight binary digits, comparing the final automaton state with the integer value modulo three. Each length $n$ includes all $2^n$ words, preserving leading zeros as distinct inputs:

All 511 checks agree. They are useful for catching a reversed arrow or mistaken label, but the reason the DFA works at every length is its invariant: after reading any word of value $n$, its automaton state is $n\mathrm{mod}3$. The update $n\mapsto 2n+b$ preserves that statement by mathematical induction. Through the extended transition function of a deterministic finite automaton, this becomes $\hat{\delta }(0,w)=\mathrm{value}(w)\mathrm{mod}3$.

Every finite-sums set generated by an infinite sequence of positive integers contains another finite-sums set generated by a strictly increasing sequence $x_i$ satisfying $x_i\mid x_{i+1}$. Consequently the divisibility requirement can be added to the conclusion of Hindman theorem.

Choose each $x_i$ as a sum over a finite block of indices of the original sequence, with these index blocks disjoint and successive. Given $x_i=m$, take two fresh groups of $m$ terms. In either group the $m+1$ partial sums, including $0$, give two equal congruence classes modulo $m$ by the pigeonhole principle. Their difference is a nonempty consecutive sum divisible by $m$, and hence at least $m$. Add the two such sums to obtain $x_{i+1}\ge 2m$ divisible by $m$. Its index block is the union of the two selected subblocks. Discard the rest of these groups and continue after them. Because the blocks are disjoint, every finite sum of the $x_i$ is a finite sum of distinct original terms. This proves both the finite-sums set containment and the strictly increasing divisibility chain.

Every endomorphism of the additive finite cyclic group $C_n=\mathbb{Z}/n\mathbb{Z}$, for a positive integer $n$, has the form $f_a(k)=ak(\mathrm{mod}n)$, determined by $a=f_a(1)$. This is the self-map case of homomorphism from a finite cyclic group: repeated addition forces the value at every element. Conversely, each choice of $a$ respects addition and gives a well-defined map on congruence classes.

Let $d=\gcd (n,a)$, the greatest common divisor. The image of a group homomorphism is the cyclic subgroup generated by $a$, with size $n/d$ by order of an element of a finite cyclic group. The kernel of a group homomorphism isIndeed, $ak=0(\mathrm{mod}n)$ is equivalent to $n/d$ dividing $k$, after cancelling $d$ and using coprimality. Consequently $f_a$ is a group automorphism exactly when $a$ and $n$ are coprime. In that case a modular inverse $b$ of $a$ gives $f_a^{-1}=f_b$. This connects reversible self-maps directly to the generators of a finite cyclic group.^[ref]

For an integer modulus $n\ge 2$ and an integer $a$ with greatest common divisor $\gcd (a,n)=1$, Euler's theorem, also called the Fermat-Euler theorem, statesHere Euler's totient function $\phi (n)$ counts the units in the unit group $U(n)=(\mathbb{Z}/n\mathbb{Z}{)}^{\times }$. These congruence classes have modular multiplicative inverses, equivalently their representatives are coprime to $n$. The guaranteed return to one permits exponent reduction for units.^[ref]

For a prime number $p$, $\phi (p)=p-1$, recovering Fermat's little theorem in the form $a^{p-1}\equiv 1(\mathrm{mod}p)$ when $p\nmid a$. Multiplying by $a$ and separately handling $p\mid a$ gives $a^p\equiv a(\mathrm{mod}p)$ for every integer $a$. For a composite number used as the integer modulus, a nonzero congruence class can be a nonunit.

Modulo twelve, the units have representatives $1,5,7,11$, so Euler's totient function gives $\phi (12)=4$. Multiplication by five producesThus this permutation has two permutation cycles, each of length two. In particular $5^2\equiv 1(\mathrm{mod}12)$, and the guaranteed return $5^4\equiv 1$ follows. The number of units need not be the length of one permutation cycle. Modulo fifteen, multiplication by seven similarly gives the two permutation cycles $(1,7,4,13)$ and $(2,14,8,11)$, covering all eight units. The powers of seven follow the permutation cycle containing one; the other permutation cycle shows that these powers do not visit every unit.

There is a stronger obstruction for a nonunit than just an occasional failed calculation. If a positive integer $d>1$ divides both $a$ and $n$, then $a^k\equiv 0(\mathrm{mod}d)$ for every $k\ge 1$, so $a^k$ cannot be congruent to one modulo $n$. For example, $\gcd (3,15)=3$ and $3^{\phi (15)}=3^8\equiv 6(\mathrm{mod}15)$, rather than one. Such a base has no multiplicative order modulo that integer modulus.^[ref]

Euler's totient function is the arithmetic functionIt counts the congruence classes modulo $n$ represented by integers coprime to $n$. In particular, $\phi (1)=1$, since $\gcd (1,1)=1$. For $12$, the coprime integers among $1,\dots ,12$ are $1,5,7,11$, so $\phi (12)=4$; they form a reduced residue system. ^[ref]

Counting these congruence classes is useful because they are exactly the classes with modular multiplicative inverses. Their number supplies the exponent in Euler theorem. Möbius inversion gives the product formulawhere $p$ runs over distinct prime factors of $n$. Thus $\phi (p^a)=p^{a-1}(p-1)$ for prime powers with $a\ge 1$, and $\phi (12)=12(1-1/2)(1-1/3)=4$. The product for $n=1$ is an empty product, so it gives the same convention $\phi (1)=1$.

A finite cyclic group of order $n$ is isomorphic to the additive group $C_n=\mathbb{Z}/n\mathbb{Z}$. The group isomorphism sends the congruence class of $k$ to $g^k$, where $g$ is a chosen generator of a group. For $n=6$, the identity element is $0$, $4+5=3$ modulo six, and the inverse element of $4$ is $2$.

One finite cyclic group can have several choices of generator of a group. Adding $1$ visits all six elements before returning to zero; adding $5$ also visits all six, in the reverse order. Adding $2$ reaches only $\{0,2,4\}$ from zero, and adding $3$ reaches only $\{0,3\}$. The following permutations of the six elements show what each repeated step can reach.

This gives a precise version of a familiar scheduling question: does a fixed step visit every position, or repeatedly miss some? The generators of a finite cyclic group are exactly the steps coprime to the total number of positions. Changing the step changes the orbit through the same underlying group; the diagram does not replace its group operation with a different one.

A finite group is a group whose underlying set has finitely many elements. Its order of a finite group is the number of elements, counting the identity element. The group operation still has to satisfy all the group axioms: merely having a finite list of states does not make a group.

For example, the six congruence classes modulo six form a finite cyclic group under addition, whereas the permutations of three objects form the symmetric group $S_3$, also with six elements. The first is an abelian group; the second is a non-abelian group. Thus the order of a finite group is a useful first measurement, but the composition rule contains information that the count alone loses.

Finiteness makes group structure accessible to exact calculation. A Cayley table for a finite group of order $n$ has $n^2$ entries, and every group element eventually returns to the identity element when repeated. Lagrange's theorem strengthens this observation: the order of a group element, being the size of its cyclic subgroup, divides $n$. The cyclic group of order four and Klein four-group give a small example of how that constraint can distinguish different composition rules.

A finite-state machine processes inputs using a finite set of automaton states and input-dependent automaton transitions. An automaton state records everything the machine remembers; an automaton transition says how that memory changes on the next symbol. A finite-state machine may also emit outputs. Here the emphasis is on recognizing a formal language: start in a designated automaton state, read a word from an alphabet, and accept exactly when the final automaton state is designated accepting.

Finite memory does not impose a maximum input length. A finite-state machine can read arbitrarily long words, revisiting its automaton states indefinitely. The restriction is that the part already read must be compressed into one of finitely many summaries. For divisibility by three, a word of binary digits can describe an enormous integer, yet its congruence class modulo three is all that the machine needs to retain. Two already-read words giving the same automaton state behave identically under every subsequent continuation in a DFA.

This makes finite-state machines useful whenever past details can be forgotten safely: checking whether a sequence of commands follows an allowed order, or recognizing a pattern with a regular expression. The beautiful design question is which distinctions about the past matter to the future. DFA minimization makes that question precise by merging indistinguishable states of a deterministic finite automaton. Both DFAs and NFAs recognize exactly the regular languages.

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.

For an integer $a$ and an odd prime $p$, the Legendre symbol is the integer valued function

Its value depends only on the congruence class of $a$ modulo $p$; the displayed notation is a symbol, not division. The value zero handles $p\mid a$ separately from quadratic residues and quadratic nonresidues.^[ref]

For example, $(2/7)=1$, $(3/7)=-1$, $(14/7)=0$, and $(2/11)=-1$. The equality $(9/7)=(2/7)=1$ illustrates that choosing a different integer representative does not change the answer. An arbitrary odd composite denominator uses the Jacobi symbol, not the Legendre symbol. For instance,but two is not a square modulo fifteen: any such square root would also give a square root modulo three, where the only nonzero square is one. A Jacobi symbol of one therefore cannot replace the Legendre symbol's square test.

The Legendre symbol also counts square roots compactly. For every congruence class $a$ in the prime field ${\mathbb{F}}_p$,The three cases give two, one and zero solutions for a quadratic residue, zero and a quadratic nonresidue, respectively. This is useful when counting solutions of modular congruences involving polynomials: a solvability question becomes a sum of Legendre symbols, as in the complete Legendre-symbol sum and quadratic Legendre-symbol correlation.

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]

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.

For integers $a$ and $n>1$, a modular multiplicative inverse is a congruence class $b$ satisfying $ab\equiv 1(\mathrm{mod}n)$. It exists exactly when $\gcd (a,n)=1$. Necessity follows because every common divisor of $a,n$ would divide $ab-kn=1$. Conversely, Bézout's identity gives $ua+vn=1$ for coprime integers, making $u$ an inverse. This is the basic bridge from greatest common divisor calculations to reversible modular arithmetic.

For example, $5\cdot 7-2\cdot 17=1$, so $5^{-1}\equiv 7(\mathrm{mod}17)$. The modular congruence $5x\equiv 3(\mathrm{mod}17)$ therefore has the unique solution class $x\equiv 21\equiv 4(\mathrm{mod}17)$. Multiplication by $5$ sends all seventeen residue classes to different classes; multiplying by $7$ reverses it. The inverse criterion and its algorithmic construction are presented in Ankur Moitra, MIT 18.200, 2024, modular inverses and Euclid's algorithm.

By contrast, $5$ has no modular inverse modulo $15$. Its products have only residues $0,5,10$. Consequently $5x\equiv 3(\mathrm{mod}15)$ has no solution, while $5x\equiv 10(\mathrm{mod}15)$ has five solution classes, $x\equiv 2,5,8,11,14$. Dividing by a noninvertible residue would discard this distinction. In a prime field ${\mathbb{F}}_p$, every nonzero residue is invertible; a general integer modulus instead gives a quotient ring that can have zero divisors.