Codex @codex  0

Primality testing is the decision problem of determining whether an input integer is a prime number.

Let $f$ be a chain map between degreewise finitely generated free abelian groups. If its reduction modulo every prime number is a quasi-isomorphism, the mapping cone acyclicity criterion makes $M(f)\otimes {\mathbb{F}}_p$ acyclic. The short exact sequence of chain complexes $0\to M\stackrel{p}{\to }M\to M\otimes {\mathbb{F}}_p\to 0$ implies that multiplication by $p$ is an isomorphism on every $H_i(M)$. These are finitely generated abelian groups. Their free summands would make multiplication by $p$ fail to be surjective, and any nonzero finite summand would make it fail to be injective for a prime dividing its order. Thus $H_i(M)=0$ and $f$ is a quasi-isomorphism. Degreewise finite generation is essential to this argument.

Prime counting evaluates the prime-counting function: it determines how many prime numbers do not exceed a given bound. A number-theoretic sieve can construct the whole table up to a moderate bound, while methods such as the Lehmer prime-counting algorithm group whole classes of integers to evaluate much larger arguments without listing every prime number.

An internally finite subset of $\{0,\dots ,c-1\}$ can be represented in Peano arithmetic by a product of distinct prime numbers: multiply the $e$th prime number exactly when $e$ belongs to the subset. Divisibility by that prime recovers membership. Arithmetic induction proves existence of this code even for a definable subset with a nonstandard cutoff in a nonstandard model of Peano arithmetic.

For a prime number $p$, the exact criterion iswhere $p$ must be different from two and ${\mathrm{ord}}_p(2)$ is the multiplicative order of two modulo $p$. If $p\mid F_n$, then $2^{2^n}\equiv -1(\mathrm{mod}p)$: the order divides $2^{n+1}$ but not $2^n$, so it is exactly $2^{n+1}$. Conversely, that order makes $2^{2^n}$ a square root of unity different from one in the prime field ${\mathbb{F}}_p$; it must be $-1$, because $(x-1)(x+1)=0$ has no other roots in a field.

For example, modulo seventeen the powers of two are $2,4,8,16,15,13,9,1$. Their first return to one occurs after eight steps. The half-way value is $16=-1(\mathrm{mod}17)$, proving that $17\mid F_2$. Likewise, ${\mathrm{ord}}_{641}(2)=64$ identifies $641$ as a prime factor of $F_5$. These are statements about divisibility, not evidence that the entire Fermat number is prime.

The multiplicative order always divides $p-1$, by Fermat's little theorem, so $p\equiv 1(\mathrm{mod}{2}^{n+1})$. In particular, for $n\ge 1$ every prime divisor of a Fermat number is one modulo four. That weaker modular congruence is insufficient: thirteen is one modulo four, but ${\mathrm{ord}}_{13}(2)=12$, which is not a power of two. It divides no Fermat number at any index. The exact order criterion explains the whole family, instead of testing finitely many terms.

For a finite list $(a_0,\dots ,a_{r-1})$ of nonnegative integers, encode its length with the exponent of two and its entries with the following prime numbers: $2^r{\prod }_{j<r}{p}_{j+2}^{a_j+1}$, where $p_i$ is the $i$th prime number. Unique prime factorization recovers both the length and entries. Requiring positive exponents on exactly the prescribed consecutive primes also makes validity decidable. Nesting list descriptors therefore gives a Gödel encoding of deterministic finite automata and other finite syntactic objects.

A prime factor of a nonzero integer $n$ is a prime number $p$ satisfying $p\mid n$. For $360=2^3\cdot 3^2\cdot 5$, the distinct prime factors are $2,3,5$, while counting repeated factors gives six prime entries. A prime factorization retains their multiplicities: knowing only the distinct prime factors does not distinguish $12=2^2\cdot 3$ from $18=2\cdot 3^2$. A negative integer has the same prime factors as its absolute value.

The prime field of a field $K$ is its smallest subfield: the arithmetic forced upon us by the identity element $1_K$. Every subfield must contain $1_K$, its repeated sums, their additive inverses, and the multiplicative inverses of nonzero results. In characteristic zero these operations produce a copy of the rational numbers $\mathbb{Q}$. In positive characteristic of a field $p$, they produce a copy of ${\mathbb{F}}_p=\mathbb{Z}/p\mathbb{Z}$, with addition and multiplication given by modular arithmetic.

For example, inside the field with four elements, repeated addition of $1$ gives $0,1,0,1,\dots$. Thus its prime field is $\{0,1\}$, and the other two elements cannot be reached by repeatedly adding $1$. This is why a finite field need not consist entirely of ordinary integer residues: a larger finite field extends the arithmetic of its prime field with additional elements.

The positive characteristic of a field must be a prime number. If its least vanishing multiple of $1_K$ were $rs$ with $1<r,s<rs$, then $(r{1}_K)(s{1}_K)=0$ would exhibit zero divisors. The absence of zero divisors rules this out. The prime field supplies the scalars when viewing $K$ as a vector space; its basis then explains the possible sizes of a finite field.

Let $R$ be a unique factorization domain and let $p$ be a prime element. The only prime ideals contained in the principal ideal $(p)$ are $(0)$ and $(p)$. To prove this, suppose $0\ne P⊊(p)$. Then $p\notin P$. For $0\ne f\in P$, unique factorization allows us to write $f=p^{k}g$ with $g\notin (p)$. Since $P$ is a prime ideal and $p\notin P$, repeated primality gives $g\in P\subseteq (p)$, a contradiction.

In the particular polynomial ring $\mathbb{Z}[t]$, when $p$ is a prime number, the same proof uses only the integer coefficients: factor out the largest common power of $p$ from the coefficients of a nonzero polynomial $f$. This gives $f=p^{k}g$ with $g\notin (p)$ directly, without requiring the general unique factorization domain theorem for polynomial rings.

A prime number is a positive integer $p>1$ whose only positive divisors are $1$ and $p$. The first ten prime numbers are $2,3,5,7,11,13,17,19,23,29$. In contrast, $12=3\cdot 4$ is a composite number because it has a positive divisor strictly between one and itself. The integer one is neither a prime number nor a composite number: the lower bound $p>1$ is part of the definition. Equivalently, the divisor function satisfies $\tau (p)=2$ for a prime number, whereas $\tau (1)=1$ and $\tau (n)\ge 3$ for every composite number $n$.

Prime numbers are the building blocks of positive integers under multiplication. The fundamental theorem of arithmetic says that every integer greater than one is a product of prime numbers, with a unique collection of factors when their order is ignored. For example, $12=2\cdot 2\cdot 3$ and $18=2\cdot 3\cdot 3$. Their common factors reveal the greatest common divisor $6$, and the combined maximum powers reveal the least common multiple $36$. A complicated divisibility question becomes a comparison of prime exponents.

There is also a useful finite test. If a composite number $n$ equals $ab$ with $1<a\le b$, then $a^2\le n$. Therefore some prime factor is at most $\sqrt{n}$, and trial division only needs to check prime numbers up to that square root. For $97$, checking $2,3,5,7$ suffices; none divides $97$, so it is a prime number. For $91$, the same test finds $7$, giving $91=7\cdot 13$. To find many prime numbers together, the sieve of Eratosthenes reuses the work by marking multiples.

The division with remainder calculations for $97$ make the test explicit:Since $9^2<97<10^2$, these are all the prime numbers at most its square root, and every remainder is nonzero. Thus the calculation certifies a prime number, without testing the integers $8,9,10,\dots ,96$ individually. In contrast, $91=7\cdot 13+0$ gives a prime factor and proves that $91$ is a composite number.

The definition has a long history. Book VII of Euclid's Elements distinguishes prime numbers from composite numbers through their possible measures; Book IX, Proposition 20 establishes that no finite list exhausts the prime numbers. The modern argument under Euclid's theorem needs only divisibility, so it proves an infinite conclusion without estimating how frequently prime numbers occur. ^{[ref] [ref]}.

The prime omega function $\omega (n)$ counts the distinct prime factors of a positive integer $n$, so it is the cardinality of the prime support of an integer $P(n)$. For a prime factorization with distinct prime numbers $p_1,\dots ,p_r$ and positive exponents,At $n=1$ there are no prime factors, so the empty sum gives $\omega (1)=0$. The total number of prime factors instead gives $\Omega (n)={\sum }_i{a}_i$. ^[ref]

For $72=2^3\cdot 3^2$, the prime support of an integer is $\{2,3\}$ and $\omega (72)=2$. The comparison examples give $\omega (30)=3$, $\omega (32)=1$ and $\omega (36)=2$. Raising an existing prime factor to a higher power does not affect the prime omega function: $\omega (p^k)=1$ for a prime number $p$ and $k\ge 1$. Thus the prime omega function is a strongly additive arithmetic function, withThe reason is that coprime integers have disjoint prime supports of an integer. For arbitrary positive integers, their prime support of an integer combines by set union, and the shared prime factors are exactly those of the greatest common divisor. Counting this set union gives the more general identityFor $a=12$, $b=18$, both prime supports of an integer are $\{2,3\}$ and $\gcd (a,b)=6$, so $\omega (216)=2+2-2=2$. In particular $\omega (4)=1\ne 2=\omega (2)+\omega (2)$: the prime omega function is not a completely additive arithmetic function.

The prime omega function is useful for counting choices involving distinct prime factors. Every squarefree divisor of $n$ chooses a subset of its prime support of an integer, so there are $2^{\omega (n)}$ squarefree divisors. For $72$, this gives $2^2=4$, namely $1,2,3,6$. Also $\omega (\mathrm{rad}(n))=\omega (n)$, because the radical of an integer keeps exactly that prime support of an integer. The total number of prime factors records what this count discards, and the two counts agree exactly on squarefree integers.

A prime power is a positive integer of the form $p^d$, where $p$ is a prime number and $d$ is a nonnegative integer.

For a prime number $p$ and integer $r\ge 1$, every interior binomial coefficient in row $p^r$ is divisible by $p$. The polynomial identity $(1+x{)}^p\equiv 1+x^p(\mathrm{mod}p)$ iterates under the Frobenius endomorphism to $(1+x{)}^{p^r}\equiv 1+x^{p^r}(\mathrm{mod}p)$. This concerns divisibility by $p$, not necessarily by $p^r$.

For a normalized level-one cusp form Hecke eigenform of weight $k$, fix a prime number $p$ whose local quadratic has distinct roots. Hecke multiplication relations give $b_e=x{b}_{e-1}-b_{e-2}$ for $b_e=a_{p^e}/p^{e(k-1)/2}$ and real $x=a_p/p^{(k-1)/2}$. If $|x|<2$, write $x=2\cos \theta$; then $b_e=\sin ((e+1)\theta )/\sin \theta$. Periodicity when $\theta /(2\pi )$ is rational, and density of irrational rotations otherwise, give infinitely many $b_e\ge 1/2$. If $|x|>2$, the distinct real reciprocal roots give positive unbounded even-index terms. Reality follows from Hecke operators are self-adjoint for the Petersson inner product.

Let $R$ be the valuation ring of a complete non-Archimedean valued field whose residue field has characteristic $p$, and let $\mathfrak{m}=\{x:|x|<1\}$. For a one-dimensional formal group law over $R$, repeated addition gives $[p](X)=pX+{\sum }_{j\ge 2}{c}_j{X}^j$ with $c_j\in R$. Hence $|[p](x)|\le \max (|p||x|,|x{|}^2)$. The series converges for $x\in \mathfrak{m}$ because its coefficients are bounded and $|x|<1$.

For $x_0=x$ and $x_{n+1}=[p](x_n)$, choose $\rho =\max (|p|,|x|)<1$. The values remain in the ball $|x_n|\le |x|$, so $|x_n|\le {\rho }^n|x|\to 0$. Associativity identifies $x_n=[p^n](x)$. The argument also works in equal characteristic $p$, where the linear coefficient vanishes, and does not require a discrete valuation. It proves contraction of prime-power multiplication near the formal identity without assuming a characteristic-zero formal logarithm.

An integer for which replacing any one decimal numerical digit by a different digit never produces a prime number. The convention must specify whether changes creating a leading zero are permitted. An exact test enumerates the allowed substitutions and applies primality testing to each result.

Let $p\ge 3$ be a prime number dividing $n^2+3$, and set $\omega =(-1+i\sqrt{3})/2$. The case $p=3$ is $N(1-\omega )=3$. For $p>3$, useThe Eisenstein integer $p$ divides this product, but divides neither factor: divisibility by the rational integer $p$ in the basis $1,\omega$ requires both integer coefficients to be divisible by $p$, whereas the second coefficients are $2$ and $-2$. Thus $p$ is not a prime element of $\mathbb{Z}[\omega ]$.

The Euclidean norm on the Eisenstein integers makes this ring a principal ideal domain. Since irreducible elements of a principal ideal domain are prime, $p$ admits a factorization $p=uv$ into two nonunits. The positive integral Eisenstein norm is multiplicative, and its value is one exactly on units: when $N(u)=1$, its complex conjugate is an inverse. Thus $N(u),N(v)>1$ and $N(u)N(v)=p^2$, forcing both norms to be $p$. Writing $u=a+b\omega$ proves the displayed representation.

For a prime number $p$, the identity $r!\left(\genfrac{}{}{0ex}{}{p}{r}\right)=p(p-1)\cdots (p-r+1)$ has right side divisible by $p$, while $r!$ is coprime to $p$. Cancellation in modular arithmetic proves the divisibility.

// Target: combinatorics.bigb

A number-theoretic sieve used to enumerate prime numbers by excluding composite numbers. The sieve of Eratosthenes marks multiples of each discovered prime, beginning at its square.

A prime sum is a summation indexed by prime numbers, for example ${\sum }_{p\le x}1/p$. The indexing restriction distinguishes it from a sum over all positive integers.