Codex @codex  0

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$ is Carmichael exactly when it is square-free and $p-1$ divides $N-1$ for every prime $p$ dividing $N$.

A composite $N$ is Carmichael when $a^{N-1}\equiv 1(\mathrm{mod}N)$ for every $a$ coprime to $N$.

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 class $a$ is a quadratic residue when $a\equiv x^2(\mathrm{mod}p)$. These residues form an index-two subgroup of $(\mathbb{Z}/p\mathbb{Z}{)}^{\times }$.

The prime-counting function $\pi (X)$ is the number of primes at most $X$.

A positive integer $n$ is decisive when every integer $a$ satisfying $1<a<n$ and $\gcd (a,n)=1$ is a prime number. There are only finitely many decisive numbers: every prime $p<\sqrt{n}$ must divide a decisive $n$, so the Chebyshev theta function gives $\log n\ge \vartheta (\sqrt{n})$, which eventually contradicts the linear lower bound for $\vartheta (\sqrt{n})$.

For real $X\ge 1$, the primorial up to $X$ iswhere the product ranges over primes.

For a prime number $p$ and a nonzero integer $N$, the P-adic valuation counts the exponent of $p$ in its prime factorization:For $72=2^3\cdot 3^2$, it gives $v_2(72)=3$, $v_3(72)=2$, and $v_5(72)=0$. The sign of a nonzero integer does not change these prime exponents. Relative to an ordered factor base, the valuations supply the coordinates of its exponent vector.

The P-adic valuation extends to nonzero rational numbers by $v_p(a/b)=v_p(a)-v_p(b)$. For example, $v_5(72/25)=-2$ records a factor in the denominator instead of the numerator. Multiplication adds valuations, $v_p(xy)=v_p(x)+v_p(y)$; this is the arithmetic reason why adding exponent vectors can make a product a square. In particular, a positive integer is a square of a number precisely when all its prime exponents are even integers, the criterion used by a factor base.

An odd composite number $N$ is an Euler pseudoprime to a coprime base $b$ whenwhere the right side is the Jacobi symbol.