Codex @codex  0

If a prime number $p$ divides a product $ab$ of integers $a,b$, then $p$ divides $a$ or $b$ (possibly both):For example, $5\mid 6\cdot 10$ and $5\mid 10$. The hypothesis that $p$ is a prime number matters: $6\mid 2\cdot 3$, although six divides neither factor. When $p$ does not divide $a$, the greatest common divisor of $p$ and $a$ is one; multiply Bézout's identity $up+va=1$ by $b$ to see that $p\mid b$. Repeated application makes this the uniqueness step in the fundamental theorem of arithmetic. ^[ref].

For a completely computed example, $7\mid 20\cdot 21$ because $20\cdot 21=420=7\cdot 60$, while $20=7\cdot 2+6$ shows that seven does not divide twenty. Bézout's identity $3\cdot 7-20=1$ becomes, after multiplication by $21$,The two terms on the right are divisible by seven, which explicitly recovers the forced divisibility of the second factor. Both alternatives can hold: $7\mid 14\cdot 21$, and seven divides both $14$ and $21$.

In fact the property characterizes prime numbers among the integers greater than one. If $c$ is a composite number, choose $c=ab$ with $1<a,b<c$; then $c\mid ab$, but $c$ divides neither $a$ nor $b$. For several factors, repeated application of Euclid's lemma says that a prime number dividing their product divides at least one factor. In a product of prime numbers, that factor must equal it, because a prime number has no other prime factor. This is what prevents a different collection of prime factors from representing the same positive integer in the fundamental theorem of arithmetic.

Book VII, Proposition 30 of Euclid's Elements states the result in terms of a prime number measuring a product; its proof uses coprimality and ratios. The calculation using Bézout's identity above is a modern way to explain the same divisibility statement. ^[ref]

There are infinitely many prime numbers. Indeed, for any finite list of prime numbers $p_1,\dots ,p_k$, the integer $N=p_1\cdots p_k+1>1$ has a prime factor, by the fundamental theorem of arithmetic. None of the listed prime numbers divides $N$, since each divides $N-1$ and a common divisor would divide $1$. Thus no finite list contains all prime numbers. The constructed $N$ need not itself be a prime number.

For example, the first six prime numbers giveBoth prime factors lie outside the original list, although $30031$ is a composite number. The construction defeats a proposed complete list; it is not a formula guaranteed to produce a prime number. Book IX, Proposition 20 of Euclid's Elements explicitly considers both possibilities, prime and composite. ^[ref].

A factorization tree is a rooted tree whose root is an integer $n>1$. Each nonleaf label is a composite number split into two factors greater than one whose product equals that label; the leaves are prime numbers. Multiplying the leaves recovers $n$. Many factorization trees can have the same root, but the fundamental theorem of arithmetic gives them the same leaf multiset.

Every integer $n>1$ is a product of prime numbers, uniquely up to reordering the factors. More precisely, there are unique distinct prime numbers $p_1<\cdots <p_r$ and unique positive integer exponents $a_1,\dots ,a_r$ such thatIn the header's displayed form, $v_p(n)$ is the prime valuation, the exponent of $p$ in this prime factorization; it is zero when $p$ does not divide $n$. Reordering or regrouping the prime factors does not give a different prime factorization.

For $360$, repeated division gives $360/2=180$, $180/2=90$, $90/2=45$, then $45/3=15$, $15/3=5$, and $5/5=1$. ThusIts nonzero prime valuations are $v_2(360)=3$, $v_3(360)=2$ and $v_5(360)=1$. Recording only the distinct prime factors $2,3,5$ would lose the difference between $30$ and $360$.

This turns divisibility into coordinatewise comparison of nonnegative exponents. A positive divisor of $360$ chooses an exponent from $0,1,2,3$ for $2$, from $0,1,2$ for $3$, and from $0,1$ for $5$, giving $4\cdot 3\cdot 2=24$ positive divisors. The greatest common divisor takes the smaller exponent at each prime number; the least common multiple takes the larger. The theorem is a structural description, not an assertion that finding the factors of every large integer is computationally easy.

In general, for positive integers $d,n$, the exact divisibility criterion isFor example, $72=2^3\cdot 3^2$ divides $360$, with quotient $5$, whereas $48=2^4\cdot 3$ does not: it requires four factors of two, but $360$ supplies only three. Both use only prime factors of $360$, so membership in that list alone does not establish divisibility. Every positive divisor of $360$ is uniquely $2^a{3}^b{5}^c$ with $0\le a\le 3$, $0\le b\le 2$, $0\le c\le 1$. Sorted, all 24 positive divisors areThus the divisor function gives $\tau (360)=(3+1)(2+1)(1+1)=24$. These include divisors that are composite numbers, as well as the prime factors and one.

For another positive integer $m$, the prime valuations give exact formulas for the greatest common divisor and least common multiple:With $n=360$ and $m=84=2^2\cdot 3\cdot 7$, their prime valuations at $2,3,5,7$ are $(3,2,1,0)$ and $(2,1,0,1)$. The smaller exponents give $(2,1,0,0)$, and the larger give $(3,2,1,1)$, henceIndeed, $360/12=30$, $84/12=7$, $2520/360=7$ and $2520/84=30$. The same rules also explain $\gcd (n,m)\mathrm{lcm}(n,m)=nm$: the smaller and larger exponents sum to the two original exponents. Here $12\cdot 2520=360\cdot 84=30240$.

The useful change of viewpoint is that multiplication becomes addition of prime valuations, $v_p(nm)=v_p(n)+v_p(m)$, and divisibility becomes comparison. Many different-looking calculations therefore share one representation. The prime valuations are coordinates for multiplication, rather than digits in positional notation: they do not turn ordinary addition of integers into coordinatewise addition.

Different intermediate splits lead to the same prime ingredients. Starting with $360=36\cdot 10$ gives $36=6\cdot 6$ and $10=2\cdot 5$; starting with $360=8\cdot 45$ gives $8=2\cdot 4$ and $45=5\cdot 9$. Continuing to split the composite numbers produces the same multiset of prime factors: three twos, two threes, and one five. The factorization tree records choices in the calculation, while the prime factorization records the invariant result.

The proof outline explains the uniqueness. Existence follows by splitting a composite number into smaller factors until only prime numbers remain. For uniqueness, Euclid's lemma says that a prime factor of one product must divide one factor of any other prime product equal to it. That factor must be the same prime number; cancel it and repeat. The crucial divisibility step appears in Book VII, Proposition 30 of Euclid's Elements. ^[ref]

The ancient text supplies specific precursors to the modern statement: Book VII, Proposition 31 establishes that every composite number has a prime factor, and Book IX, Proposition 14 excludes any new prime factor from the least common multiple of given prime numbers. These are the propositions being cited, rather than the complete modern exponent formulation of the fundamental theorem of arithmetic. ^{[ref] [ref]}

Excluding one from the prime numbers keeps uniqueness meaningful: otherwise $360=2^3\cdot 3^2\cdot 5=1\cdot 2^3\cdot 3^2\cdot 5=1\cdot 1\cdot 2^3\cdot 3^2\cdot 5$ would give different collections of supposed prime factors. For $n=1$, the natural convention is the empty product, equal to one, with no prime factors and all prime valuations zero.

If the prime $p$ does not divide $x$, then $\gcd (p,x)=1$. The Bezout identity gives integers $a,b$ with $ap+bx=1$. Multiplying by $y$ gives $apy+bxy=y$. If $p\mid xy$, both terms on the left are divisible by $p$, so $p\mid y$. Thus Euclid lemma holds:For completeness, existence in the fundamental theorem of arithmetic follows by strong induction on a positive integer $n>1$. If $n$ is prime there is nothing to prove; otherwise $n=ab$ with $1<a,b<n$, and the inductive prime factorizations of $a,b$ give one for $n$. The integer $1$ has the empty factorization.

For uniqueness, suppose $p_1\cdots p_r=q_1\cdots q_s$ are two prime factorizations. Repeated application of Euclid lemma shows that $p_1$ divides some $q_j$. Both are primes, so they are equal. Reorder the second list, cancel this equal factor, and repeat. All factors must be matched, including their multiplicities. Thus prime factorization exists and is unique up to the order of its factors. For nonzero negative integers one also records the sign.

Suppose $p$ is a prime number, $p\mid xy$ and $p\nmid x$. Since the only positive divisors of $p$ are one and $p$, the greatest common divisor of $p$ and $x$ is one. By Bézout's identity, integers $u,v$ exist with $up+vx=1$. Multiplying by $y$ gives $upy+vxy=y$. Both terms on the left are divisible by $p$, so $p\mid y$. Thus Euclid lemma givesThe fundamental theorem of arithmetic says that every positive integer greater than one is a product of prime numbers, uniquely up to their order. Existence follows by strong mathematical induction: if $n$ is prime it already has a factorization; otherwise $n=ab$ with $1<a,b<n$, and the factorizations of $a,b$ combine to factor $n$.

For uniqueness, suppose $p_1\cdots p_r=q_1\cdots q_s$ are two prime factorizations. Repeated application of Euclid lemma makes $p_1$ divide one of the $q_j$, so primality forces $p_1=q_j$. Reorder that factor to the front, cancel it and repeat. Neither side can retain extra primes when the other has become one, since every prime exceeds one. The two multisets are therefore identical. For a negative integer there is additionally the uniquely determined sign; one has the empty positive factorization, and zero is excluded. The prime-product divisibility lemma is the step which makes factorization unique.

Put $N=\lfloor x\rfloor$. Comparing the harmonic number with an integral gives $H_N={\sum }_{n=1}^{N}1/n>{\int }_1^{N+1}dt/t=\log (N+1)>\log x$. By the fundamental theorem of arithmetic, the finite Euler product ${\prod }_{p\le x}(1-p^{-1}{)}^{-1}$ expands as the sum of $1/n$ over positive integers whose prime factors are at most $x$. It therefore includes every term of $H_N$, andThe first strict inequality is the geometric-series bound for the logarithmic remainder; the last uses the telescoping series ${\sum }_{n=2}^{\infty }1/[n(n-1)]=1$. Thus the prime reciprocal lower bound is

Absolute convergence and the fundamental theorem of arithmetic give the Euler productFor a finite set of primes, expand the geometric factors: their product sums $n^{-s}$ over integers whose prime factors lie in that set. Let the finite sets increase through all primes. Absolute convergence permits passage to the limit and recovers the full Dirichlet series. Moreover ${\sum }_{p,m\ge 1}|p^{-ms}|/m<\infty$, so the logarithm converges and the product has no zeros there.

The same absolutely convergent logarithm, and $3+4\cos \theta +\cos 2\theta =2(1+\cos \theta {)}^2\ge 0$, giveThis is the product version of the three-four-one zero-free-region argument. It also proves there are no zeros on $\Re s=1$: if $\zeta (1+i{t}_0)=0$ for $t_0\ne 0$, its factor has order at least four as $\sigma \downarrow 1$, while the real pole contributes only order minus three and the $2t_0$ factor remains bounded. The displayed left side would tend to zero, a contradiction. At $t_0=0$ there is a pole, not a zero.

For large $|t|$, put $L=\log (|t|+2)$. The Hardy-Littlewood approximation to the Riemann zeta function at $x\asymp |t|$ gives $|\zeta (\sigma +it)|\ll L$ for $1-2/L\le \sigma \le 3$; its finite sum is bounded by ${\sum }_{n\le x}{n}^{-1+2/L}\ll L$ and the integral term is bounded. The Cauchy estimate for derivatives on circles of radius comparable to $1/L$ consequently gives $|{\zeta }^{\prime }(\sigma +it)|\ll L^2$ for $1-L^{-9}\le \sigma \le 2$.

Take ${\sigma }_0=1+a{L}^{-9}$ with a small fixed $a>0$. The product inequality, $\zeta ({\sigma }_0)\ll L^9/a$, and $|\zeta ({\sigma }_0+2it)|\ll L$ implyIf $1-c{L}^{-9}\le \sigma \le {\sigma }_0$, integration of the derivative along the horizontal segment changes this value by at most $C(a+c)L^{-7}$. Choose $a$ sufficiently small that $Ca<c_0{a}^{3/4}/4$, then $c\le a$ sufficiently small. The lower bound remains a positive multiple of $L^{-7}$. For ${\sigma }_0\le \sigma \le 2$, the same product inequality, $\zeta (\sigma )\le \zeta ({\sigma }_0)$, and the near-one upper bound give that lower bound directly. For $\sigma \ge 2$, the reciprocal Euler product gives $|1/\zeta (s)|\le \zeta (2)$.

Finally the no-zero result on $\Re s=1$, compactness at bounded heights and the regular reciprocal at the pole allow a further fixed reduction of $c$ to include bounded $t$. We have proved the weak logarithmic zero-free region for the Riemann zeta functionThe reciprocal at $s=1$ is its holomorphic extension, equal to zero.

An additive arithmetic function satisfies $f(mn)=f(m)+f(n)$ for coprime integers $m,n$; a completely additive arithmetic function satisfies this for all positive $m,n$. In either case $f(1)=0$. The fundamental theorem of arithmetic gives $f(n)={\sum }_{p^k\parallel n}f(p^k)$, where $p^k\parallel n$ means that the prime valuation of $n$ at $p$ is exactly $k$.

Under the discrete uniform distribution on $[N]$, the expectation of the indicator function of $p^k\parallel n$ isThe formula remains valid when $p^{k+1}>N$. Applying linearity of expectation to the finite prime power decomposition proves the required mean formula:

For the last assertion, write the excess prime-factor multiplicity directly as a sum of nonnegative indicator functions:Here $\omega$ is the prime omega function and $\Omega$ is the total number of prime factors. The expectation is bounded independently of $N$, sinceThus Markov inequality gives vanishing probability on every diverging scale:

By the fundamental theorem of arithmetic, every integer greater than one has a prime factorization, and that factorization is unique up to reordering the factors. Equivalently, it has a unique finite prime-exponent representation $\boxed{n=\prod _p{p}^{v_p(n)}}$, with nonnegative integer exponents. The unit integer has the empty product.

If the complete list of prime numbers were $p_1,\dots ,p_k$, then $N=p_1\cdots p_k+1>1$ would have a prime divisor by the fundamental theorem of arithmetic. No $p_i$ divides it, since $N\equiv 1(\mathrm{mod}{p}_i)$. This contradicts completeness of the list. Hence there are infinitely many prime numbers.

The fundamental theorem of arithmetic says that every integer $n>1$ is a product of prime numbers, uniquely up to reordering. Equivalently, $n={\prod }_p{p}^{a_p}$ for a unique family of nonnegative integer exponents, only finitely many of which are nonzero.

If the complete list of prime numbers were $p_1,\dots ,p_k$, then $N=p_1\cdots p_k+1>1$ would have a prime divisor by the fundamental theorem of arithmetic. No $p_i$ divides it, since $N\equiv 1(\mathrm{mod}{p}_i)$. This contradicts completeness of the list. Hence there are infinitely many prime numbers.

The fundamental theorem of arithmetic says that every integer $n>1$ is a product of prime numbers, uniquely up to reordering. Equivalently, $n={\prod }_p{p}^{a_p}$ for a unique family of nonnegative integer exponents, only finitely many of which are nonzero.

Use strong induction on the positive integer $n$. The case $n=1$ is represented by the empty product. For $n>1$, if $n$ is prime it is already a product of one prime. Otherwise $n=ab$ with $1<a,b<n$; the induction hypothesis gives prime factorizations for both $a$ and $b$, and concatenating them gives one for $n$. This proves existence in the fundamental theorem of arithmetic without presupposing uniqueness.

The allowed primes are exactly $2,3,5,7$. DefineThe fundamental theorem of arithmetic makes this definition unambiguous and proves injectivity. For every $(a,b,c,d)\in {\mathbb{N}}^4$, the positive integer $2^a{3}^b{5}^c{7}^d$ belongs to $S$ and maps to that tuple, proving surjectivity. The inverse function is explicitly ${\Phi }^{-1}(a,b,c,d)=2^a{3}^b{5}^c{7}^d$. In particular, $1$ maps to $(0,0,0,0)$. This is the prime-exponent parametrization of smooth numbers.

For distinct primes $p_1,\dots ,p_r$, let $M$ consist of the positive integers having no other prime factors, including $1$. The map from a number to its exponent tuple is a bijection from $M$ to ${\mathbb{N}}^r$ when $0\in \mathbb{N}$. The fundamental theorem of arithmetic proves that the tuple is uniquely defined and that equality of tuples implies equality of numbers. Every nonnegative tuple gives the allowed number $p_1^{e_1}\cdots p_r^{e_r}$, proving surjectivity. Multiplication of numbers corresponds to coordinatewise addition of tuples, with $1$ corresponding to the zero tuple.

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]}.

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

Every integer $n\ge 2$ has a prime factorization. The induction base case $2$ is prime. For a larger integer, either it is prime or it is $ab$, with $2\le a,b<n$. The induction hypothesis supplies prime factorizations of both smaller integer divisors; multiplying them gives one for $n$. This proves existence, while uniqueness requires the additional argument under the fundamental theorem of arithmetic.^[ref]

For the chosen number $84$, one possible recursive decomposition isThe step at $84$ needs results for $6$ and $14$, rather than a result for $83$. Each composite number in this factorization tree splits into strictly smaller positive integers, so recursive descent terminates at prime numbers. The tree describes one construction; another choice of integer divisors can give a differently shaped factorization tree.

The same pattern explains the usefulness of strong induction for algorithm correctness. When a recursive procedure returns answers for smaller inputs, the induction hypothesis can justify those answers; the remaining task is to justify how the current call combines them. Strictly decreasing a nonnegative integer size measure establishes termination. Correctness also requires each call's conditions and its combination rule; termination alone does not make an algorithm correct.