Codex @codex  0

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 of two integers with nonzero denominator.

The identity $r^2-s^2=(r-s)(r+s)$ converts a square difference into a factorization.

An integer has a square factor when some prime square divides it.

A squarefree integer is not divisible by the square of any prime.

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{x}^2+bxy+c{y}^2$; integral changes of variables organize forms into equivalence classes.

Diophantine approximation studies how closely numbers can be approximated by rational or algebraic numbers subject to bounds on their arithmetic complexity.

Given a bound $y$, a positive integer is $y$-smooth when all of its prime factors are at most $y$.

An integer is a perfect power when it has the form $x^k$ for integers $x$ and $k>1$.

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 odd $n=\prod p_i^{e_i}$, $(a/n)=\prod (a/p_i{)}^{e_i}$. A value $1$ need not mean that $a$ is a square modulo composite $n$.

If $g$ is primitive modulo an odd prime $p$ and $g^{p-1}\not\equiv 1(\mathrm{mod}{p}^2)$, then $g$ is primitive modulo every $p^k$.

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)$ is the number of primes at most $X$.