Codex @codex  0

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.

A Fermat prime is a Fermat number that is also a prime number:The defining form alone does not imply primality. For example, $65537$ is a Fermat prime, while $4294967297$ is a Fermat number with proper divisors. For $k\ge 1$, every Fermat prime is one modulo four and two modulo three. Pépin's test gives an exact primality testing criterion for these candidates, rather than relying on their form.

For the Fermat primality test, a passing base satisfies $a^{n-1}\equiv 1(\mathrm{mod}n)$. Passing proves only this modular congruence, not that $n$ is a prime number. An odd composite number that passes a coprime base is a Fermat pseudoprime to that base. A Carmichael number passes every coprime base, so even testing all the units would not certify that $n$ is a prime number. ^[ref]

This small table uses only the bases $2,3,5,11$, each reduced modulo $n$ first. A numeric entry is $a^{n-1}\mathrm{mod}n$: one passes, while any other numeric entry gives a Fermat witness. A "factor" entry records a proper greatest common divisor and stops before modular exponentiation. The prime/composite classification is independently established by trial division or the displayed prime factorization, not by the passing entries. These four bases are illustrative, with no asserted universal coverage or error probability.

For $341=11\cdot 31$, $\gcd (2,341)=1$ and $2^{10}=1024=3\cdot 341+1$, so $2^{340}=(2^{10}{)}^{34}\equiv 1(\mathrm{mod}341)$. Yet $\gcd (3,341)=1$ and $3^{340}\equiv 56(\mathrm{mod}341)$, so three is a Fermat witness. One coprime base passes and another fails: being a Fermat pseudoprime depends on the base. Choosing eleven instead reveals the proper factor through $\gcd (11,341)=11$.

For $561=3\cdot 11\cdot 17$, every coprime base passes: each of $2,10,16$ divides $560$, so Fermat's little theorem gives $a^{560}\equiv 1$ modulo each prime factor; the Chinese remainder theorem combines the three modular congruences. Equivalently, the Carmichael function gives $\lambda (561)=80\mid 560$. Bases two and five have greatest common divisor one and pass, but $\gcd (3,561)=3$, $\gcd (11,561)=11$ and $\gcd (17,561)=17$ expose factors. The qualification "coprime" is therefore crucial even for a Carmichael number.

The Fermat primality test is useful because a Fermat witness can prove compositeness using repeated squaring without finding a factor. Its failure to certify a passing candidate motivates stronger primality testing methods such as the Miller-Rabin primality test.

Integer factorization seeks the prime factorization of a positive integer $N$. For $N>1$, this means identifying its prime factors and their multiplicities; one has the empty prime factorization. Finding one proper divisor $1<d<N$ is useful progress, but need not finish the job: factor $d$ and $N/d$ further until all factors are prime numbers.

For example, $77=7\cdot 11$ is a semiprime, whereas $231=3\cdot 7\cdot 11$ has three prime factors. Primality testing asks whether a proposed integer is prime; it need not return a factor when the answer is no. Trial division is a direct factoring method: try division by small prime numbers until a divisor is found. More elaborate methods obtain a proper divisor through a greatest common divisor of $N$ with a specially constructed integer.

The beautiful trick in congruence of squares is that two integers with equal squares modulo $N$ can reveal different factors through their sum and difference. In the worked $N=77$ example, $20^2\equiv 13^2(\mathrm{mod}77)$ gives $\gcd (20-13,77)=7$ and $\gcd (20+13,77)=11$. Computing those greatest common divisors uses the Euclidean algorithm; it does not require trying every potential factor. A factor base supplies a systematic way to construct useful equal-square relations. ^[ref].

This connection is useful in cryptography because recovering the factors of an RSA cryptosystem modulus defeats the factoring assumption behind its construction. That application concerns large, carefully chosen inputs; the small examples here explain the arithmetic mechanism and are not benchmarks or estimates of present cryptographic security.

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]

Number theory studies integers, their divisibility, and the patterns created by prime numbers. Its questions often have short statements but rigid answers: which integers divide a given one, when does an equation have integer solutions, and when can arithmetic with congruence classes be reversed? The Euclidean algorithm and modular multiplicative inverses connect these questions through explicit calculations.

For example, $252=2^2\cdot 3^2\cdot 7$ and $198=2\cdot 3^2\cdot 11$. Their shared prime factors give greatest common divisor $18$. The Euclidean algorithm reaches that answer without finding either complete prime factorization. It also produces $18=4\cdot 252-5\cdot 198$, an instance of Bézout's identity. This relation certifies every common divisor at once and solves an associated linear Diophantine equation.

Modular arithmetic retains only remainders, but the lost information can be surprisingly controlled. Multiplication by $5$ modulo $17$ is a permutation of all residue classes, because $5$ has modular inverse $7$. Multiplication by $5$ modulo $15$ collapses fifteen residue classes to three. Thus an apparently small change in the modulus changes whether a calculation can be reversed. The Chinese remainder theorem explains another kind of compression: remainders modulo coprime integers can be combined into one remainder modulo their product.

Simple restrictions help reveal the structure without telling the whole story. Every prime number greater than three is congruent to $1$ or $5$ modulo $6$: the other four residue classes force divisibility by $2$ or $3$. The converse fails because $25$ and $35$ lie in those classes but are composite numbers. Necessary conditions are useful filters, not substitutes for primality testing.

The subject's appeal lies partly in this tension: prime factorization gives a clean description of every positive integer, while identifying factors and predicting their distribution lead to substantial further questions. Analytic number theory uses tools from analysis to study global patterns, and algebraic number theory extends arithmetic into number fields. Applications include cryptography and error-correcting codes; MIT's discrete applied mathematics course develops modular structures for both purposes. ^[ref]

Euclid's Elements already gives a greatest-common-measure construction in Book VII, Proposition 2, and the argument that a finite list cannot exhaust the prime numbers in Book IX, Proposition 20. These are documented ancient treatments, rather than evidence that all of number theory began with one author. ^{[ref] [ref]}

Write $n=2^{r}m$ with $m$ odd. If $m>1$, the polynomial factor of $X^m+1$ by $X+1$, evaluated at $X=10^{2^r}$, supplies a proper divisor. Therefore $n$ must be a power of two. Conversely this is only a necessary condition for primality testing.

For a prime factor $p$ of the number, $p$ is odd and does not divide $10$. Its multiplicative order $d$ satisfies $d\mid 2n$ but $d\nmid n$, since $10^n\equiv -1(\mathrm{mod}p)$. When $n$ is a power of two, every proper divisor of $2n$ divides $n$, so $d=2n$. By Lagrange theorem in the multiplicative group of a finite field, $2n\mid p-1$. Thus $\boxed{p\equiv 1(\mathrm{mod}2n)}$.

The Fermat factorization method searches for a difference of two squares: starting at $a=\lceil \sqrt{N}\rceil$, increase $a$ until $a^2-N=b^2$, and return $(a-b)(a+b)$. Every factorization of an odd integer has this form, with $a=(d+e)/2$ and $b=(e-d)/2$. For $N=10001$, the successive differences at $a=101,102,103,104,105$ are $200,403,608,815,1024$. The last is $32^2$, giving $\boxed{10001=73\cdot 137}$. Trial division by the primes up to their respective square roots confirms that both factors are prime.

A perfect number is a positive integer equal to the sum of all its positive proper divisors. The divisor itself is excluded: including it gives the equivalent condition $\sigma (n)=2n$ for the sum-of-divisors function. The smallest examples are $6=1+2+3$ and $28=1+2+4+7+14$.

For comparison, $8$ has proper divisors $1,2,4$, whose sum is $7$: it is a deficient number. The proper divisors of $12$ are $1,2,3,4,6$, whose sum is $16$: it is an abundant number. The proper-divisor sum classifies these examples with the same rule, and gives $s(1)=0$, so one is not a perfect number.

The interesting question is how such balances can be constructed without testing every smaller integer as a possible divisor. The Euclid-Euler theorem answers it for even integers: a Mersenne prime $2^p-1$ gives $2^{p-1}(2^p-1)$, and every even perfect number arises this way. For $p=2,3,5,7$, this produces $6,28,496,8128$. The connection links divisor sums to primality testing for a particular family, while keeping the necessary hypotheses visible.^[ref]

Euclid's Elements already gives the construction in Book IX, Proposition 36: add a succession of powers of two, and if their sum is prime, multiply by the final power of two. The modern finite geometric series $1+2+\cdots +2^{p-1}=2^p-1$ makes the same pattern transparent. This original statement supplies the forward construction, rather than the converse classification of all even perfect numbers.^[ref]

Primality is the property of a positive integer being a prime number. Primality testing determines this property; integer factorization asks for factors and is a different computational task.

The sieve of Eratosthenes finds all prime numbers at most an integer $N\ge 2$. Start with the integers $2,\dots ,N$ marked as candidates. For each surviving candidate $p$ in increasing order, mark the multiples $p^2,p^2+p,\dots$ up to $N$ as composite numbers. Stop processing candidates once $p^2>N$: the surviving candidates are exactly the prime numbers. Starting at $p^2$ saves work because any smaller proper multiple of $p$ already has a smaller prime factor. ^[ref].

For a complete run with $N=60$, the only prime numbers at most $\sqrt{60}$ are $2,3,5,7$, since $7^2\le 60<8^2$. Exclude one before starting; it is not a prime number. The four marking passes are:

There are $59-29-9-3-1=17$ surviving prime numbers:The next surviving candidate is $11$, and $11^2>60$, so no further marking pass is necessary. A prime number used for marking remains a candidate: starting at $p^2$ never marks $p$ itself.

The saving from starting at $p^2$ is justified by the smaller multiplier: if $pk<p^2$ with $2\le k<p$, then $k$ has a prime factor $q<p$, so $q$ has already marked $pk$. For $p=7$, the earlier multiples $14,21,28,35,42$ have already been marked using $2,3$ or $5$. The first new possibility is $49$.

For $N=100$, only the prime numbers $2,3,5,7$ need marking passes. They remove all the composite numbers, leaving 25 prime numbers. The diagram colors each composite number by its smallest prime factor, so it shows which marking pass removes it first. The excluded integer one is shown separately.

Why does the algorithm work? A surviving candidate cannot be a composite number, since its smaller prime factor would already have removed it. Conversely, marking proper multiples never removes a prime number. Every composite number at most $N$ has a prime factor at most $\sqrt{N}$, so no later pass is needed. The sieve of Eratosthenes is useful when an entire bounded list is wanted; primality testing of one large integer is a different computational task.

The historical name is supported by a surviving primary account: Nicomachus, in Book I, chapter 13 of Introduction to Arithmetic, names Eratosthenes and describes separating prime numbers from composite numbers by marking multiples among the odd integers beginning with three. That passage documents the sieve tradition; the bounded algorithm above and its $p^2$ starting rule are the formulation explained here, rather than instructions quoted from Euclid's Elements. ^[ref]

Trial division searches for divisors of an integer by testing candidate divisions. For primality testing of an integer $n>1$, testing the prime numbers up to $\sqrt{n}$ suffices: any composite number has a prime factor in that range. After finding a prime factor, repeated division removes its prime power, and testing the remaining quotient gives an elementary integer factorization method. This is useful for small inputs, but the number of candidates can grow rapidly with the input's digit count.

For an integer $n>1$, Wilson's theorem characterizes prime numbers by a factorial:The right side is an integer congruence, so the least nonnegative remainder is $n-1$. For example, $4!=24\equiv 4(\mathrm{mod}5)$ certifies that five is a prime number, whereas $5!=120\equiv 0(\mathrm{mod}6)$ rules out six. ^[ref]

For an odd prime number $p$, each nonzero congruence class has a unique modular multiplicative inverse. Pair each class with its inverse: each distinct pair contributes one. A class is its own inverse exactly when $a^2\equiv 1(\mathrm{mod}p)$; since $p\mid (a-1)(a+1)$, Euclid's lemma leaves only $a\equiv \pm 1$. Their product is $-1$. The prime number two needs a separate check: $1!\equiv -1(\mathrm{mod}2)$. Conversely, a proper divisor $1<d<n$ divides both $n$ and $(n-1)!$, so the displayed integer congruence would force $d\mid 1$, a contradiction. ^[ref]

The composite numbers have an even sharper pattern: $(n-1)!\equiv 0(\mathrm{mod}n)$ for every composite number $n>4$, but $3!=6\equiv 2(\mathrm{mod}4)$. To check the zero claim, write $n=ab$ with $1<a\le b<n$. If $a<b$, both occur as different factors in the factorial. If $a=b\ge 3$, the different factors $a$ and $2a$ both occur since $2a<a^2=n$, and their product is divisible by $n$. The only excluded case is $a=b=2$. Thus four is an exception to the zero pattern, but still fails Wilson's theorem: its required remainder would be three.

This is an exact primality testing criterion, but direct evaluation is expensive: even reducing modulo $n$ after every multiplication still takes a number of multiplications proportional to $n$, which grows exponentially with the number of binary digits of $n$. The problem is not merely storing a huge factorial. The more useful role of Wilson's theorem is simplifying factorial expressions in modular arithmetic. For instance, if $p>2$ is a prime number, then $(p-1)(p-2)!\equiv -1(\mathrm{mod}p)$ gives $(p-2)!\equiv 1(\mathrm{mod}p)$ by a modular multiplicative inverse.