Codex @codex  0

For positive integers $a,b$, the Euclidean algorithm repeatedly performs division with remainder: write $a=qb+r$ with $0\le r<b$, then replace $(a,b)$ by $(b,r)$ until the second entry is zero. The final nonzero entry is their greatest common divisor. A remainder preserves the set of common divisors: an integer divides $a$ and $b$ exactly when it divides $b$ and $a-qb$. The positive remainders strictly decrease, so the calculation terminates.

The complete calculation for $252$ and $198$ isHence $\gcd (252,198)=18$. The fraction $252/198$ reduces to $14/11$ by dividing numerator and denominator by that common factor. The same remainder calculation has a geometric interpretation: remove squares from a $252$-by-$198$ rectangle, then repeat on the remaining strip. Each division step records how many equal squares fit and the width of the new strip.

The procedure does more than test individual divisors. Each step replaces the whole common-divisor problem by a smaller equivalent one. Euclid's Book VII, Proposition 2 describes the corresponding repeated-subtraction construction; batching those subtractions into division with remainder gives the present formulation. ^[ref]

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.

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

A rational number is a quotient $a/b$ of integers with $b\ne 0$. The numerator $a$ can be negative or zero; the denominator $b$ can be chosen positive by transferring its sign to $a$. For example, $-6/8=-3/4$ and $0/7=0$.

Different fractions describe the same rational number exactly when cross multiplication gives $ad=bc$. Dividing the entries by their greatest common divisor produces the unique reduced fraction with positive denominator, including $0/1$ for zero.

The rational numbers form a field: addition, subtraction, multiplication and division by a nonzero rational number remain rational. They are dense in the real line, by density of the rational numbers, although they do not fill it: the square root of two is an irrational number.

The difference of two squares identity isIt follows by expanding the right side and cancelling its cross terms. It holds for real numbers and, more generally, in a commutative ring.

For integers $r,s$, the factors $u=r-s$ and $v=r+s$ have the same parity. Conversely, any integer factorization $n=uv$ with factors of the same parity yields $r=(u+v)/2$ and $s=(v-u)/2$. Thus an integer is a difference of two squares exactly when it is not congruent to two modulo four: odd values use $u=1,v=n$, and multiples of four use $u=2,v=n/2$. This is the factor-pair interpretation behind Fermat's factorization method.

A square factor of an integer $n$ is a positive perfect square $m^2$ dividing $n$. Every integer has the trivial square factor one; usually the useful question is whether a nontrivial one, with $m>1$, occurs.

A positive integer has a nontrivial square factor if and only if some prime number $p$ satisfies $p^2\mid n$. One direction takes $m=p$; for the other, choose any prime factor of $m$. Equivalently, some prime exponent in $n$ is at least two. For example, twelve has square factor four and eighteen has square factor nine, whereas thirty has none other than one. A positive integer without a nontrivial square factor is a square-free integer.

For a prime number $p$ and an integer $a$ not divisible by $p$, Fermat's little theorem states the modular congruenceEquivalently, for every integer $a$, including $a<0$ and multiples of $p$,The first formulation follows from the second by multiplying by a modular multiplicative inverse of $a$. Conversely, multiply the first by $a$ when $p\nmid a$; when $p\mid a$, both sides of the second are zero modulo $p$. The divisibility condition in the first formulation is essential.^[ref]

For $p=7$, $3^6=729=7\cdot 104+1$, so $3^6\equiv 1(\mathrm{mod}7)$ and $3^7\equiv 3(\mathrm{mod}7)$. Also $(-2{)}^6=64\equiv 1(\mathrm{mod}7)$, while $7^6\equiv 0(\mathrm{mod}7)$: a zero residue class cannot satisfy the first formulation. It does satisfy $7^7\equiv 7\equiv 0(\mathrm{mod}7)$. A failure at a zero residue class therefore says nothing against a candidate's being a prime number.

The prime number $p=2$ is included. Its only nonzero residue class is one: every odd integer $a$ satisfies $a^{2-1}=a\equiv 1(\mathrm{mod}2)$. Every integer also satisfies $a^2\equiv a(\mathrm{mod}2)$, because $a(a-1)$ is even. Testing the first formulation with an even integer would violate its hypothesis.

The useful surprise is that every nonzero residue class returns to one at the same exponent $p-1$, although its shortest return can be earlier. This gives exponent reduction for units: for a nonnegative integer $k$, $a^k\equiv a^{k\mathrm{mod}(p-1)}(\mathrm{mod}p)$ when $p\nmid a$. It also computes a modular multiplicative inverse as $a^{p-2}$ modulo $p$, including $p=2$. Repeated squaring makes these modular exponentiations practical.

In group theory, the nonzero residue classes form the multiplicative group of integers modulo n with $n=p$, of group order $p-1$. Lagrange's theorem says that the multiplicative order of $a$ divides $p-1$, giving the guaranteed return. Euler's theorem extends this to a general integer modulus $n$, using the units and Euler's totient function $\phi (n)$; the Carmichael function gives the least common return exponent for all units. A nonzero residue class modulo a composite number need not be a unit.

Leonhard Euler's paper presented in 1732 and published in 1738 states a historical formulation: Theorem 1 says that powers with exponent $n-1$ leave zero or one upon division by a prime number $n$. The preceding discussion states the difference-of-powers version and explicitly says that he does not have its proof.^[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$.

For a prime number $p$ and a positive integer $n$, the prime valuation is the exponent of $p$ in the prime factorization of $n$, equivalentlyThus $v_2(360)=3$ because $8$ divides $360$ but $16$ does not; $v_3(360)=2$, $v_5(360)=1$ and $v_7(360)=0$. In particular $v_p(1)=0$. Multiplication adds prime valuations, $v_p(ab)=v_p(a)+v_p(b)$, and the fundamental theorem of arithmetic makes comparison of prime valuations an exact test for divisibility between positive integers. This definition extends to a nonzero integer by taking its absolute value; for zero one commonly sets $v_p(0)=+\infty$.

A binary quadratic form is a quadratic form in two variables, written $f(x,y)=a{x}^2+bxy+c{y}^2$ or $[a,b,c]$. In number theory an integral binary quadratic form has integer polynomial coefficients $a,b,c$. It represents an integer $n$ when $f(x,y)=n$ for some integers $x,y$.

The homogeneous polynomial identity $f(tx,ty)=t^{2}f(x,y)$ distinguishes a form from a general quadratic polynomial with constant or linear terms. The discriminant of a binary quadratic form is $D=b^2-4ac$. For example, $x^2+y^2$ has $D=-4$ and represents $5=1^2+2^2$, while $x^2+xy+y^2$ has $D=-3$ and represents $7=1+2+4$ at $(1,2)$.

Changing integer coordinates can conceal the same arithmetic. Substituting $(x,y)=(u+v,v)$ into $x^2+y^2$ gives $u^2+2uv+2v^2$. The transformation has determinant one and an integer inverse, so both forms represent exactly the same integers. Proper equivalence of binary quadratic forms records this reversible change, and the reduction algorithm for a positive definite binary quadratic form chooses a small representative for each such equivalence class.

Diophantine approximation asks how closely a real or complex quantity can be approximated by rational numbers or algebraic numbers of bounded arithmetic complexity. For a real $\alpha$, one compares $|\alpha -p/q|$ with functions of the denominator $q$.

For example, continued fraction convergents to $\sqrt{2}$ give approximations $3/2,7/5,17/12,\dots$. A nonzero integer norm of $p-q\sqrt{2}$ also supplies a lower bound, preventing arbitrarily exceptional accuracy. The Liouville approximation theorem extends this idea to algebraic numbers, while Roth's theorem sharpens the exponent for algebraic irrational inputs. Approximation quality can therefore distinguish algebraic from transcendental behavior, not merely give convenient decimal values.

For a real bound $y\ge 2$, a positive integer is $y$-smooth when every prime factor is at most $y$. Thus $72=2^3{3}^2$ is three-smooth, while $70=2\cdot 5\cdot 7$ is not. The number one is smooth for every such bound because it has no prime factors.

Equivalently, a $y$-smooth number is ${\prod }_{p\le y}{p}^{e_p}$ with nonnegative integer prime exponents. The fundamental theorem of arithmetic makes this representation unique. Consequently two three-smooth numbers multiply to another three-smooth number, but adding them need not preserve the property: $1+6=7$.

Smooth numbers are useful in integer factorization: a number factoring entirely over a small factor base can be recorded by a finite exponent vector, and matching exponent parities produces a congruence of squares.

An integer is a perfect power if it can be written $m^k$ with integers $m$ and $k>1$. In the common nontrivial positive version, both the value and the base exceed one. For example, $64=8^2=4^3=2^6$ qualifies, whereas twelve does not. The degenerate values $0$, $1$ and $-1$ are included or excluded according to the convention being used.

For a positive integer $n>1$ with prime factorization $n={\prod }_i{p}_i^{e_i}$, the exact criterion isIf $n=m^k$, every prime exponent is divisible by $k$. Conversely, a common divisor $k>1$ lets one take $m={\prod }_i{p}_i^{e_i/k}$. This gives a recognition test once the prime factorization is known; it does not imply that factorization is the fastest recognition algorithm.

A negative value requires an odd exponent. Thus $-64=(-4{)}^3$ is a perfect power, while $-16$ is not: its absolute value has only powers of two as common divisors of its exponents. Perfect cubes are the special case $k=3$, whereas a cube-full number imposes a different lower bound on each prime exponent.

A composite integer $N>1$ is a Carmichael number if and only if it is a squarefree integer andThe criterion is named for Alwin Korselt. The two requirements are different: the first excludes repeated prime factors, while the second makes the exponent $N-1$ a common multiple of the prime-field return exponents.^[ref]

For $1105=5\cdot 13\cdot 17$, the numbers $4,12,16$ divide $1104$ with quotients $276,92,69$. Thus 1105 is another Carmichael number. By contrast $341=11\cdot 31$ is squarefree, but $30\nmid 340$; a single failed divisor condition excludes it. This illustrates the appeal of the criterion: a statement about every unit becomes a small calculation using a known prime factorization.

The composite condition must be retained. A prime number is squarefree and satisfies the divisibility condition, but is excluded from the definition of a Carmichael number. The resulting certificate also depends on the supplied factors really being prime numbers; merely finding a product decomposition is insufficient.

A Carmichael number is a composite number $N>1$ for whichEvery unit modulo $N$ satisfies the same modular congruence supplied by Fermat's little theorem for a prime number. The name refers to Robert Daniel Carmichael. The coprime qualification is essential: a nonunit can expose a prime factor through a greatest common divisor calculation. A Carmichael number is therefore a Fermat pseudoprime to every coprime base, rather than to every nonzero residue class.^[ref]

For example,The factors are distinct prime numbers. Their predecessor numbers $2,10,16$ all divide $560$, so Korselt criterion applies. More explicitly, for any integer $a$ coprime to $561$, Fermat's little theorem givesThe Chinese remainder theorem combines these into $a^{560}\equiv 1(\mathrm{mod}561)$. This proves all coprime bases pass from three short divisibility checks, rather than from a long table of sampled bases.

Equivalently, a composite $N$ is a Carmichael number exactly when $a^N\equiv a(\mathrm{mod}N)$ for every integer $a$, including nonunits. The equivalence follows from Korselt criterion: modulo each prime factor, either $a$ is zero or its nonzero power returns to one, and squarefreeness combines those congruences. This does not say a nonunit satisfies $a^{N-1}\equiv 1$. For instance $a=3$ gives $3^{560}\equiv 375(\mathrm{mod}561)$, while $3^{561}\equiv 3(\mathrm{mod}561)$; the greatest common divisor already supplies the factor three.^[ref]

The Carmichael function supplies another compact description: a composite $N$ is Carmichael exactly when $\lambda (N)\mid N-1$. For $561$, $\lambda (561)=\mathrm{lcm}(2,10,16)=80$ and $560=7\cdot 80$. In contrast, Euler's totient function gives $\phi (561)=320$, which does not divide $560$. The least common return exponent, rather than the number of units, controls this test.

The obstruction is useful to know when interpreting a Fermat primality test: even checking every coprime base cannot certify primality. The passing-base fraction for the Fermat test makes this failure quantitative. Stronger primality tests require additional structure, such as the squaring conditions in a Miller-Rabin primality test.

The historical record predates the name. Václav Šimerka's 1885 paper lists $561,1105,1729,2465,2821,6601,8911$ on printed page 224, together with factorizations. This is an early published list of examples, independently of their later name.^[ref]

Quadratic reciprocity compares two questions: is the prime number $p$ a quadratic residue modulo $q$, and is $q$ a quadratic residue modulo $p$? Let $p,q$ be distinct odd primes. In terms of the Legendre symbol,The two Legendre symbols have opposite signs exactly when both primes are $3$ modulo $4$; otherwise they are equal. Their values are nonzero because the primes are distinct. Equal signs can mean two quadratic residues or two quadratic nonresidues: reciprocity compares the answers rather than declaring either answer positive.^[ref]

For a direct computation, the nonzero quadratic residues modulo $3,5,7$ are respectively $\{1\}$, $\{1,4\}$, and $\{1,2,4\}$. Squaring just $1,\dots ,(p-1)/2$ suffices because $x$ and $p-x$ have the same square modulo an odd prime $p$.The pair $3,7$ has a sign flip, whereas $5,7$ has two negative signs. These small quadratic residue tables make the distinction tangible.

The first supplementary law for quadratic reciprocity handles numerator $-1$, and the second supplementary law for quadratic reciprocity handles numerator $2$:For an odd prime $p$, $-1$ is a quadratic residue exactly when $p\equiv 1(\mathrm{mod}4)$, while $2$ is a quadratic residue exactly when $p\equiv 1,7(\mathrm{mod}8)$. The remaining odd congruence classes modulo $8$, namely $3,5$, make $2$ a quadratic nonresidue. These laws fill the cases excluded from swapping distinct odd primes.^[ref]

For an odd positive integer $n={\prod }_i{p}_i^{e_i}$, the Jacobi symbol is the product of Legendre symbolsThe fundamental theorem of arithmetic makes this definition unambiguous. Its value is zero exactly when $a$ and $n$ have a common prime factor; otherwise it is $1$ or $-1$. For $n=1$, the empty product convention gives $(a/1)=1$.

If $a$ is a quadratic residue modulo $n$ and is coprime to $n$, its Jacobi symbol is one. The converse can fail for a composite number: $(2/15)=(2/3)(2/5)=(-1)(-1)=1$, but two is not a square modulo fifteen because it is not a square modulo three.

Computing the Jacobi symbol does not require first finding the prime factorization. Repeatedly remove factors of two, swap odd numerator and denominator using Jacobi reciprocity, and reduce the numerator modulo the denominator, as in the Euclidean algorithm. This makes it useful in the Solovay-Strassen primality test.

If $g$ is a primitive root modulo an odd prime $p$, thenis the exact condition for $g$ to remain a primitive root modulo every power $p^m$. Its multiplicative order modulo $p^2$ must be a multiple of $p-1$ and a divisor of $p(p-1)$, so the condition makes that order $p(p-1)$. The result then follows from lifting a primitive root to odd prime powers.

For example, two is primitive modulo three and $2^2=4\not\equiv 1(\mathrm{mod}9)$. It is therefore primitive modulo every $3^m$. The assumption that $p$ is odd is essential; the unit groups of higher powers of two are not cyclic groups.

For an odd prime $p$, a nonzero congruence class $a$ is a quadratic residue when $a\equiv x^2(\mathrm{mod}p)$ for some integer $x$. Here "quadratic residue" excludes zero: zero is a square of a number, but is neither a quadratic residue nor a quadratic nonresidue under this convention. Some treatments include zero among quadratic residues; the distinction matters when counting them or discussing their subgroup.^[ref]

Modulo seven, squaring the six nonzero congruence classes givesThus the set of quadratic residues is $Q_7=\{1,2,4\}$, and the quadratic nonresidues are $\{3,5,6\}$. In particular, $x^2\equiv 2(\mathrm{mod}7)$ has exactly the two solutions $x\equiv 3,4(\mathrm{mod}7)$: $3^2=9\equiv 2$ and $4^2=16\equiv 2$. Modulo eleven the quadratic residues are instead $Q_{11}=\{1,3,4,5,9\}$. Two is therefore a quadratic residue modulo seven and a quadratic nonresidue modulo eleven: being a quadratic residue depends on the modulus.

Why do the square roots come in pairs? If $x^2\equiv y^2(\mathrm{mod}p)$, the prime number $p$ divides $(x-y)(x+y)$, so it divides one factor: $y\equiv x$ or $y\equiv -x(\mathrm{mod}p)$. For nonzero $x$ these are distinct, because $p$ is an odd prime. Every nonempty nonzero fiber of a function of $s(x)=x^2$ therefore contains exactly two inputs. Pairing the $p-1$ nonzero congruence classes gives exactly $(p-1)/2$ quadratic residues and $(p-1)/2$ quadratic nonresidues. Including zero gives $(p+1)/2$ different squares, with one rather than two square roots for zero.

The quadratic residues form a subgroup of the multiplicative group of a finite field ${\mathbb{F}}_p^{\times }$, with index of a subgroup two. Indeed, one is a square, $(u^2)(v^2)=(uv{)}^2$, and $(u^2{)}^{-1}=(u^{-1}{)}^2$; the inverses exist because the inputs are nonzero in the prime field. Equivalently, the squaring group homomorphism has kernel of a group homomorphism $\{1,-1\}$ and image of a function $Q_p$. The apparent loss of a sign in squaring becomes a precise division of the nonzero arithmetic into two equal parts.

This structure turns a search for square roots into a yes-or-no test: Euler's criterion detects quadratic residues through modular exponentiation, and the Legendre symbol records the result as a sign. For a general integer modulus, the modular congruence $x^2\equiv a(\mathrm{mod}n)$ still makes sense, but the two-root count and the prime field argument need not survive. For example, $x^2\equiv 1(\mathrm{mod}15)$ has four solutions $1,4,11,14$; the Chinese remainder theorem separates the sign choices modulo three and five.

The prime-counting function $\pi (x)$ counts the prime numbers not exceeding a real bound $x$:Thus $\pi (10)=4$, $\pi (11)=5$ and $\pi (12)=5$. It is a nondecreasing step function with a jump of one at each prime number, and $\pi (x)=0$ for $x<2$.

Computing one large value is different from listing every prime number below it. A number-theoretic sieve can do both up to a moderate bound; Legendre prime-counting formula and the Lehmer prime-counting algorithm instead organize counts of allowable factors. The Prime number theorem describes the long-term scale $\pi (x)\sim x/\log x$, rather than exact individual jump locations.