Codex @codex  0

The binary numeral system is positional notation with radix two. Each binary digit is zero or one, and its place value is a power of two. A one includes that weight in the sum; a zero skips it. The binary representation $11001101_2$ therefore selects $128,64,8,4,1$ and represents the integer $205$.

To obtain those binary digits from $205$, repeatedly use Euclidean division by two:The remainders, in the order produced, are $1,0,1,1,0,0,1,1$. Read them in reverse order to get $11001101_2$. The final zero is the quotient that stops the conversion, not an additional leading binary digit. Starting with zero itself needs the special single-digit representation $0_2$.

A useful independent check reads the binary digits from left to right. Start with $v=0$ and, for each binary digit $d$, replace $v$ by $2v+d$. For $11001101_2$, the intermediate values are $1,3,6,12,25,51,102,205$. This reconstructs the integer without reversing a list and explains why appending a zero on the right doubles the value.

Binary is well suited to computation because each binary digit has just two possibilities. A stored bit can encode either possibility; groups of bits encode larger integers. Practical integer arithmetic can use a radix that is itself a power of two, grouping several binary digits into each stored numeral digit.^[ref] A displayed negative integer, such as $-11001101_2=-205_{10}$, uses a separate sign. A computer's particular signed storage convention is an additional encoding choice, so the displayed sign should not be confused with an extra binary place.

The binary powering multiplication count counts arithmetic operations. The time complexity measured in operations on individual bits also depends on operand lengths. Put $L=\lfloor {\log }_{2}m\rfloor +1$, the binary length of the modulus, and let $\ell$ be the positive exponent's binary length. Stored residues use at most $L$ bits, and an unreduced product uses at most $2L$ bits.

With ordinary long multiplication and division with remainder, one modular product costs $O(L^2)$ operations on bits. Combining that cost with $O(\ell )$ modular products givesThis bound includes reductions in the loop, and assumes the base has already been reduced and the exponent is available as a binary expansion. Reading the exponent takes $O(\ell )$ additional work; initial reduction of a very long base depends on its input length, and an inverse for a negative exponent adds further work. More generally, if a modular product costs $R(L)$ operations on bits, the powering loop costs $O(\ell R(L))$. Faster multiplication and reduction methods can improve the quadratic bound.^[ref]

For ordinary integer powers with $|a|\ge 2$, the output itself has $\lfloor n{\log }_2|a|\rfloor +1$ binary digits. Even writing it takes work proportional to that length. Consequently $O(\log (n+1))$ multiplications does not imply $O(\log (n+1))$ operations on bits: the operands grow during ordinary exponentiation by squaring, whereas modular exponentiation keeps them bounded by the modulus. A squaring or multiplication by a small fixed base can also cost less than a general product, so equal counts need not mean equal running times.

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

Exponentiation by squaring computes an integer power by reading the exponent's binary expansion. Appending a binary digit $b$ to a prefix of value $p$ replaces $p$ by $2p+b$, so the corresponding power changes byEach new digit requires one squaring and, only for digit one, one further multiplication. The number of digits grows with the logarithm of the exponent, making this useful for modular exponentiation, primality testing, and powers of matrices using matrix multiplication.^[ref]

For a concrete calculation, $13=(1101{)}_2=8+4+1$, so $3^{13}=3^8\cdot 3^4\cdot 3$. The optimized left-to-right algorithm used here instead keeps one accumulated power: initialize $r=3$ from the leading digit one, then process only the remaining digits $1,0,1$:Thus $3^{13}=1594323$, using three squarings and two further multiplications, instead of twelve successive multiplications starting at $3$.

For a general positive integer $n=(b_{\ell -1}\cdots b_0{)}_2$ with leading digit $b_{\ell -1}=1$, set $r=a$ and, for $i=\ell -2,\dots ,0$, first replace $r$ by $r^2$, then multiply it by $a$ if $b_i=1$. Return $r$. This explicitly skips the leading digit's otherwise unnecessary operations on one. A Computational Introduction to Number Theory and Algebra by Victor Shoup (Section 3.4, pp. 65–66) presents the version initialized at one and processing every digit; the optimization here makes the counting convention unambiguous.

The loop invariant is $r=a^p$, where $p$ is the value of the digits already read. Initially $p=1$ and $r=a$. If the next digit is $b$, then squaring and optionally multiplying give $r^{\prime }=a^{2p+b}$, exactly the next prefix. At termination $p=n$. This proof uses associativity of multiplication; it works in any monoid, including matrices with the identity matrix as identity element, and needs no commutativity between different bases.

For $n=0$, return the identity element without performing a multiplication. This is the empty-product convention $a^0=1$; if $a=0$, the algorithm therefore returns one for $0^0$ by convention, rather than resolving its meaning in every mathematical setting. Negative integer exponents require an inverse element: compute $(a^{-1}{)}^{-n}$, counting the inversion separately. Over the integers, such an inverse generally leaves the integers, and a zero base has no inverse.

An integer is a whole number, positive, negative, or zero. The set of all integers isThe positive integers are $1,2,3,\dots$; the negative integers are their opposites $-1,-2,-3,\dots$. Zero is neither positive nor negative. The nonnegative integers include zero and all the positive integers. On a number line, consecutive integers are one unit apart, negative integers lie to the left of zero, and positive integers lie to its right. ^[ref]

The integers let counting describe changes in both directions. If a counter starts at $-3$ and increases by five, it reaches $2$: $-3+5=2$. Decreasing that result by four gives $2+(-4)=-2$. In addition on the number line, the sign of the added integer chooses the direction and its absolute value gives the distance. The additive inverse $-a$ reverses the change made by $a$.

The integers have closure under a binary operation for addition, subtraction and multiplication: whenever $a,b\in \mathbb{Z}$, the results $a+b$, $a-b$ and $ab$ are still integers. Together these operations give the integers their ring structure.^[ref] For instance, $-3+5=2$, $-3-5=-8$, and $(-3)\cdot 5=-15$. General division has no such closure: $1/2$ is a rational number but not an integer. Some divisions are exact, such as $(-6)/3=-2$; division by zero is undefined. Euclidean division instead produces an integer quotient and a remainder, so $7=3\cdot 2+1$ retains the information that ordinary division puts into the fraction $7/3$.

An integer is the value, whereas its written numeral is an encoding. The decimal representation $205_{10}$ and the binary representation $11001101_2$ name the same integer. Changing positional notation changes how that value is displayed and how calculations are organized; it does not change the value itself.

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 coprime integers $a,n$ with $n>1$, the multiplicative order is the least positive integer $d$ such thatIt counts the distinct powers in the cyclic subgroup generated by the congruence class of $a$. Thus it is an order of a group element in the unit group $(\mathbb{Z}/n\mathbb{Z}{)}^{\times }$.^[ref]

For example, the modular exponentiation $2^k\mathrm{mod}7$, starting at $k=0$, produces $1,2,4,1,2,4,\dots$. The first return to one takes three steps, so ${\mathrm{ord}}_7(2)=3$. Starting at the congruence class three and repeatedly multiplying by two instead gives $3,6,5,3,\dots$: these are the other three units modulo seven, outside the cyclic subgroup generated by two.

Euler's theorem guarantees a return to one at exponent $\phi (n)$, where $\phi$ is Euler's totient function. Thus the multiplicative order exists for every unit.^[ref] In fact,By Lagrange's theorem, the size of the cyclic subgroup divides the size of the unit group, which is Euler's totient function. For two modulo seven, this is $3\mid 6$; the multiplicative order need not equal Euler's totient function. If $a\equiv 1(\mathrm{mod}n)$, its multiplicative order is one.

The coprime integers hypothesis is necessary: if $a^d=1+kn$, any common divisor of $a$ and $n$ divides one. For instance, powers of two modulo eight give $1,2,4,0,0,\dots$, with no positive-exponent return to one. This sequence eventually settles, but two has no multiplicative order modulo eight.

Let $a,n$ be coprime integers with $n>1$, and let $d={\mathrm{ord}}_n(a)$ be their multiplicative order. For integers $x,y$,Negative exponents mean powers of the modular inverse of $a$. Thus periodic modular exponentiation has smallest positive period $d$, and $1,a,\dots ,a^{d-1}$ are distinct congruence classes.^[ref]

This lets a huge modular exponentiation reuse a short list: reduce its exponent modulo the multiplicative order, then look up the corresponding power. For example, $1000\equiv 1(\mathrm{mod}3)$ gives $2^{1000}\equiv 2(\mathrm{mod}7)$, while $1001\equiv 2(\mathrm{mod}3)$ gives $2^{1001}\equiv 4(\mathrm{mod}7)$. When the multiplicative order is unknown, Euler's theorem permits reduction modulo Euler's totient function, though that period may be longer. Repeated squaring remains useful when computing either the unreduced or the reduced power.

For a proof outline, multiply $a^x\equiv a^y$ by the modular inverse of $a^y$, leaving $a^{x-y}\equiv 1$. Apply Euclidean division to write $x-y=td+r$ with $0\le r<d$. Then $a^{x-y}\equiv a^r$; minimality of the multiplicative order forces $r=0$. The reverse implication follows from $a^d\equiv 1$. The coprime integers hypothesis enables cancellation: modulo eight, $2^3\equiv 2^4\equiv 0$, but this repetition supplies no multiplicative order for two.

In positional notation, a numeral digit contributes its value multiplied by a weight determined by its position. Fix an integer radix $b\ge 2$. A finite string of numeral digits $d_n{d}_{n-1}\cdots d_0$, with $0\le d_j<b$, represents the nonnegative integerThe rightmost position has weight $b^0=1$; each move left multiplies the weight by $b$. This weight is the place value. For a nonzero integer, the canonical string has $d_n\ne 0$. Zero is written with the single numeral digit $0$. Leading zeros are permitted in a fixed-width display but omitted in the canonical form: $00205_{10}=205_{10}$. A negative integer is written with a separate minus sign and the positional notation for its absolute value; the minus sign is not a numeral digit.^[ref]

For example,The zero is essential inside this string: $25_{10}=25$, not $205$. It records that the tens position contributes nothing while keeping the hundreds and units in their proper positions. The same integer has binary representation

Repeated Euclidean division constructs the representation exactly. Set $N_0=N$. At each step writeKeep the remainder $d_j$ and continue with the integer quotient $N_{j+1}$. A positive quotient strictly decreases, so eventually it is zero. Substituting the successive equations back into the first gives $N=d_0+b{d}_1+b^2{d}_2+\cdots$: the numeral digits are obtained from right to left. The remainder modulo $b$ uniquely fixes $d_0$, and then the quotient uniquely fixes the remaining string by the same reasoning. This proves existence and uniqueness once leading zeros are excluded. The needed unique quotient and remainder are precisely the conclusion of the Euclidean division theorem.^[ref]

This finite expansion concerns nonnegative integers. Extending positional notation to fractional positions uses weights $b^{-1},b^{-2},\dots$ to the right of a point; an arbitrary real number need not have a finite digit string. In particular, the decimal representation $0.1$ represents $1/10$, while the base-two string $0.1_2$ represents $1/2$. The radix is part of the interpretation.

The benefit is compact arithmetic: $k$ positions can encode every nonnegative integer below $b^k$. To see the upper endpoint, fill all positions with $b-1$; the finite geometric series gives $(b-1)(1+b+\cdots +b^{k-1})=b^k-1$. Carrying in addition exchanges $b$ units of one place value for one unit of the next. Thus a short string stores a large count and also supplies an algorithm for computing with it.