Codex @codex  0

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

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

The nonnegative arithmetic function $\Omega (n)-\omega (n)$ counts the repeated occurrences beyond the first of each prime factor. Its expectation under uniform sampling from $[N]$ is bounded by ${\sum }_{p}1/(p(p-1))\le 1$, independently of $N$.

A factor base is a finite set of small prime numbers over which selected auxiliary integers are completely factored. Some methods also record a sign coordinate for $-1$, which is not a prime number. A positive integer supported entirely on the chosen factor base gives an exponent vector; reducing that vector modulo two records which prime exponents are odd integers. The product is a square of a number precisely when every prime exponent is an even integer.

For the original toy $N=77$, use factor base $\{2,3,5\}$ and the two relationsThe residues have exponent vectors $(0,1,1)$ and $(2,1,1)$ in the order $(2,3,5)$. Adding the two vectors modulo two gives $(0,0,0)$, so multiplying the residues gives $15\cdot 60=900=30^2$. Consequentlyand $\gcd (X-Y,77)=7$ and $\gcd (X+Y,77)=11$. Neither individual residue was a square; combining the relations made all exponents even.

In a larger collection, choose relations $x_i^2\equiv r_i(\mathrm{mod}N)$ with positive residues $r_i={\prod }_{j=1}^B{p}_j^{e_{ji}}$. If a nonempty selection $I$ has an even sum in every exponent coordinate, setThen $X^2\equiv Y^2(\mathrm{mod}N)$. Finding such a selection is a linear dependence problem over the finite field ${\mathbb{F}}_2$: the indicator vector of the chosen relations belongs to the kernel of a linear map given by the parity matrix. This is why a problem about prime factors recruits linear algebra. The final congruence of squares may still be trivial, so another selection can be needed. ^[ref].

There is a tradeoff: a small factor base gives a smaller parity matrix, but fewer auxiliary integers factor completely over it. A larger factor base accepts more relations but makes the linear algebra larger. Negative auxiliary values need an additional sign coordinate, and a selected product needs even sign parity as well as even prime exponents. Pomerance's account explains this balance and the historical development of combining smooth relations; the toy example omits algorithm-specific sieving and running-time claims. ^[ref].

A Fermat number is the positive integer $F_n=2^{2^n}+1$, indexed by a nonnegative integer $n$. The first five are $3,5,17,257,65537$, all prime numbers; the next is the composite number $F_5=4294967297=641\cdot 6700417$. This family offers a compact lesson in number theory: a very persuasive finite pattern can fail, while an exact divisibility relation settles a gigantic case with little computation.

Why does the exponent itself have the form $2^n$? Suppose $m=ab$ is a positive integer with an odd integer factor $b>1$. The polynomial factorization $x^b+1=(x+1)(x^{b-1}-x^{b-2}+\cdots -x+1)$ shows that $2^a+1$ is a proper divisor of $2^m+1$. Consequently, if $2^m+1$ is a prime number, $m$ must be a power of two. That is a necessary condition, rather than a promise that the surviving candidates are prime.

The Fermat number product identity makes distinct Fermat numbers coprime integers. Thus every term has a prime factor absent from all earlier terms, whether or not that term is itself a prime number. This gives an explicit route to infinitely many different prime numbers, without establishing that infinitely many terms of this particular sequence are prime. Meanwhile the prime divisor of a Fermat number criterion filters possible factors through a small multiplicative order calculation.

The family also links arithmetic to Euclidean geometry: a constructible regular polygon can have a number of sides equal to a power of two times a product of distinct Fermat primes. The Gauss-Wantzel theorem gives the precise criterion. For instance, $15=3\cdot 5$ and $17$ qualify, but $9=3^2$ does not. The word "distinct" matters. Carl Pomerance describes this connection in Primality testing: then and now by Carl Pomerance (slide 18).

Historically, Leonhard Euler records Pierre de Fermat's proposed primality pattern, then refutes it by finding the factor $641$ of $F_5$. His paper was presented in 1732 and published in 1738; those are different events, not competing dates for one publication.^[ref]

A short modern check needs only two representations of $641$:In modular arithmetic these give $5^4{2}^{28}\equiv 1$ and $5^4\equiv -2^4(\mathrm{mod}641)$. Substitution yields $2^{32}\equiv -1(\mathrm{mod}641)$, so $641\mid F_5$. This verifies the factor directly; it does not claim to reconstruct Euler's search process.

For the Fermat primality test, a passing base satisfies $a^{n-1}\equiv 1(\mathrm{mod}n)$. Passing proves only this modular congruence, not that $n$ is a prime number. An odd composite number that passes a coprime base is a Fermat pseudoprime to that base. A Carmichael number passes every coprime base, so even testing all the units would not certify that $n$ is a prime number. ^[ref]

This small table uses only the bases $2,3,5,11$, each reduced modulo $n$ first. A numeric entry is $a^{n-1}\mathrm{mod}n$: one passes, while any other numeric entry gives a Fermat witness. A "factor" entry records a proper greatest common divisor and stops before modular exponentiation. The prime/composite classification is independently established by trial division or the displayed prime factorization, not by the passing entries. These four bases are illustrative, with no asserted universal coverage or error probability.

For $341=11\cdot 31$, $\gcd (2,341)=1$ and $2^{10}=1024=3\cdot 341+1$, so $2^{340}=(2^{10}{)}^{34}\equiv 1(\mathrm{mod}341)$. Yet $\gcd (3,341)=1$ and $3^{340}\equiv 56(\mathrm{mod}341)$, so three is a Fermat witness. One coprime base passes and another fails: being a Fermat pseudoprime depends on the base. Choosing eleven instead reveals the proper factor through $\gcd (11,341)=11$.

For $561=3\cdot 11\cdot 17$, every coprime base passes: each of $2,10,16$ divides $560$, so Fermat's little theorem gives $a^{560}\equiv 1$ modulo each prime factor; the Chinese remainder theorem combines the three modular congruences. Equivalently, the Carmichael function gives $\lambda (561)=80\mid 560$. Bases two and five have greatest common divisor one and pass, but $\gcd (3,561)=3$, $\gcd (11,561)=11$ and $\gcd (17,561)=17$ expose factors. The qualification "coprime" is therefore crucial even for a Carmichael number.

The Fermat primality test is useful because a Fermat witness can prove compositeness using repeated squaring without finding a factor. Its failure to certify a passing candidate motivates stronger primality testing methods such as the Miller-Rabin primality test.

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.

Integer factorization seeks the prime factorization of a positive integer $N$. For $N>1$, this means identifying its prime factors and their multiplicities; one has the empty prime factorization. Finding one proper divisor $1<d<N$ is useful progress, but need not finish the job: factor $d$ and $N/d$ further until all factors are prime numbers.

For example, $77=7\cdot 11$ is a semiprime, whereas $231=3\cdot 7\cdot 11$ has three prime factors. Primality testing asks whether a proposed integer is prime; it need not return a factor when the answer is no. Trial division is a direct factoring method: try division by small prime numbers until a divisor is found. More elaborate methods obtain a proper divisor through a greatest common divisor of $N$ with a specially constructed integer.

The beautiful trick in congruence of squares is that two integers with equal squares modulo $N$ can reveal different factors through their sum and difference. In the worked $N=77$ example, $20^2\equiv 13^2(\mathrm{mod}77)$ gives $\gcd (20-13,77)=7$ and $\gcd (20+13,77)=11$. Computing those greatest common divisors uses the Euclidean algorithm; it does not require trying every potential factor. A factor base supplies a systematic way to construct useful equal-square relations. ^[ref].

This connection is useful in cryptography because recovering the factors of an RSA cryptosystem modulus defeats the factoring assumption behind its construction. That application concerns large, carefully chosen inputs; the small examples here explain the arithmetic mechanism and are not benchmarks or estimates of present cryptographic security.

A positive integer in this set has no prime factor equal to two or congruent to three modulo four. Its prime factors all lie in the residue class one modulo four. For example $5\cdot 13=65$ belongs, while $3^2=9$ does not, even though $9$ itself is congruent to one modulo four. A half-dimensional interval sieve bounds the count in an interval of length $z$ by $O(z/\sqrt{\log z})$.