Codex @codex  0

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.

For finite sets $A_1,\dots ,A_n$, the cardinality of their union isAdd the individual cardinalities, subtract pairwise intersection counts, add triple intersection counts, and continue alternating. This is useful whenever one object can satisfy several conditions: a search result can match several filters, or a permutation can have several forbidden fixed points.

Among the integers from 1 to 30, let $A$ contain the multiples of 2 and $B$ the multiples of 3. Then $|A|=15$, $|B|=10$, and $|A\cap B|=5$, because their common multiples are the multiples of 6. The naive sum $25$ counts those five twice; the correct union size is $15+10-5=20$. The regions contain ten in $A$ alone, five in both, five in $B$ alone, and ten in neither.

Add a third set $C$ containing the multiples of 5. Its size is 6; the three pairwise intersections have sizes $5,3,2$; and the triple intersection contains only 30. The inclusion-exclusion principle gives $15+10+6-5-3-2+1=22$ integers divisible by at least one of 2, 3, and 5.

The alternating corrections have a local explanation. An object belonging to exactly $r\ge 1$ of the sets is counted $\left(\genfrac{}{}{0ex}{}{r}{1}\right)-\left(\genfrac{}{}{0ex}{}{r}{2}\right)+\cdots +(-1{)}^{r+1}(\genfrac{}{}{0ex}{}{r}{r})=1$ times, by the binomial theorem applied to $(1-1{)}^r$. An object in none contributes zero. Thus overlapping descriptions are repaired without requiring the sets themselves to be disjoint. For probability, the same calculation applies to event probabilities in place of cardinalities, giving the inclusion-exclusion principle for probabilities.

For a positive modulus $m$, integers $a,b$ are congruent when their difference is divisible by $m$. This is an equivalence relation: zero is divisible by $m$, changing sign preserves divisibility, and adding two divisible differences proves transitivity. Addition and multiplication respect it, because $(a+c)-(b+d)=(a-b)+(c-d)$ and $ac-bd=c(a-b)+b(c-d)$. Its equivalence classes are the residue classes used in modular arithmetic.

For a nonnegative integer $n$ and a prime number $p$, the Legendre formula computes the prime exponent in a factorial without forming that huge product:Here $\lfloor x\rfloor$ is the floor function. The sum is finite: every term with $p^j>n$ is zero. When $n=0$, all terms vanish, agreeing with $0!=1$ and $v_p(1)=0$. The prime number hypothesis matters: a composite number does not give the same P-adic valuation or additive prime exponent. For example, the floor sum with $n=6,p=4$ is one, whereas $4^2$ divides $6!=720$.

Why count multiples repeatedly? Each multiple of $p$ in $1,\dots ,n$ contributes one factor of $p$; each multiple of $p^2$ contributes another; and so on. A factor $m$ with P-adic valuation $a$ occurs in exactly the first $a$ counts. Adding those contributions proves the formula.^[ref]

For the original example $n=50,p=3$,The five multiples $9,18,27,36,45$ each contribute a second factor of three. The factor $27$ contributes a third, so it appears in all three rows. Equivalently, among $1,\dots ,50$ there are eleven factors of P-adic valuation one, four of valuation two, and one of valuation three: $11+2\cdot 4+3\cdot 1=22$. Thus $3^{22}$ divides $50!$, while $3^{23}$ does not.

Repeated Euclidean division provides a practical evaluation: replace $q$ by $\lfloor q/p\rfloor$, starting from $q=n$, and add each new quotient until it is zero. This uses only the successive quotients $16,5,1,0$ for the example. The same calculation handles divisibility of binomial coefficients, where the P-adic valuations of the denominator factorials are subtracted.

A linear congruence asks for the integers $x$ satisfying $ax\equiv b(\mathrm{mod}n)$, where $a,b$ are integers and $n>1$. Let $d=\gcd (a,n)$ be their greatest common divisor. There are solutions exactly when $d$ divides $b$. When solutions exist, there are exactly $d$ solution classes modulo $n$, obtained from one solution $x_0$ byThe divisibility condition follows immediately from $ax-b=kn$: every common divisor of $a,n$ must divide $b$. Conversely, Bézout's identity constructs a solution when $d\mid b$. Differences between any two solutions obey $n\mid a(x-x_0)$, equivalently $n/d\mid x-x_0$, since $a/d$ and $n/d$ are coprime. This explains both the spacing and the number of solution classes.

For a complete example, solve $6x\equiv 9(\mathrm{mod}15)$. Here $d=3$ divides nine. Dividing the corresponding divisibility statement by three changes the integer modulus too:Because $2\cdot 3\equiv 1(\mathrm{mod}5)$, multiplying by the modular inverse three gives $x\equiv 9\equiv 4(\mathrm{mod}5)$. Lifting this class back to modulus fifteen yields $x\equiv 4,9,14(\mathrm{mod}15)$. Direct substitution gives $24$, $54$ and $84$, each with remainder nine after division with remainder by fifteen. By contrast, $6x\equiv 10(\mathrm{mod}15)$ has no solutions, because three does not divide ten.

This is why ordinary-looking division cannot be performed blindly in modular arithmetic. Reducing the equation and its integer modulus together keeps all solutions; retaining modulus fifteen after dividing by three would lose valid classes. When $d=1$, the modular inverse of $a$ exists and gives a unique class $x\equiv a^{-1}b(\mathrm{mod}n)$. The Euclidean algorithm computes the Bézout coefficients needed for this construction. ^[ref]

Logical implication forms the proposition $A\to B$, read “if $A$, then $B$”. In classical propositional logic, it is false exactly when $A$ is true and $B$ is false. Equivalently, it has the same truth table as $\neg A\vee B$, using logical negation and logical disjunction. A false hypothesis makes the logical implication true regardless of its conclusion; thus it asserts neither the hypothesis nor a causal connection.

For example, for every natural number $n$, divisibility by four implies that $n$ is an even number: $n=4k=2(2k)$. At $n=8$, both statements are true. At $n=6$, the hypothesis is false and the conclusion true; at $n=3$, both are false. The only forbidden case is a multiple of four that is not an even number.

In Intuitionistic propositional logic, a proof of $A\to B$ consists of a construction transforming any proof of $A$ into a proof of $B$. The implication introduction rule proves $B$ under a temporary assumption $A$; the modus ponens rule applies the result when $A$ is available. The classical identification with $\neg A\vee B$ is not generally intuitionistically valid.

Modular arithmetic performs addition and multiplication on integers while remembering only their remainders for a fixed positive integer modulus $m$. The relation $a\equiv b(\mathrm{mod}m)$ means that $m$ divides $a-b$: the two integers lie in the same congruence class. For example, $-3$, $2$ and $7$ represent one class modulo $5$. Choosing the least nonnegative residue gives exactly $m$ representatives, $0,1,\dots ,m-1$, even though each congruence class contains infinitely many integers.

A clock supplies a familiar example. Represent the twelve positions by $0,1,\dots ,11$, with $0$ at the position usually labelled twelve. Starting at ten and moving seven positions givesThe integer congruence records the final position; it discards the number of complete revolutions. Adding another twelve changes the elapsed count while preserving the position. The picture also shows a single congruence class modulo five spread along the number line.

The useful surprise is that discarding this information still preserves the arithmetic. If $a\equiv a^{\prime }$ and $b\equiv b^{\prime }$ modulo $m$, then $a+b\equiv a^{\prime }+b^{\prime }$ and $ab\equiv a^{\prime }{b}^{\prime }$ modulo $m$. Thus a large calculation can reduce its intermediate integers after every step. For instance,Replacing $10$ by $-2$ gives the same answers with smaller intermediate values. The congruence classes with these operations form the quotient ring $\mathbb{Z}/m\mathbb{Z}$; their addition alone forms a cyclic group. This passage from integers to a finite arithmetic system is the setting for modular exponentiation, primality testing and the RSA cryptosystem. ^[ref]

Multiplicative cancellation needs extra care. Modulo six, $2\cdot 1\equiv 2\cdot 4$, but $1\not\equiv 4$: multiplication by two has merged distinct congruence classes. Cancelling a factor while retaining the integer modulus is justified when that factor has a modular multiplicative inverse, equivalently when it is coprime to the integer modulus. A linear congruence can consequently have no solutions, one solution class, or several solution classes. The Chinese remainder theorem supplies a complementary operation: splitting a calculation across coprime integer moduli and reconstructing its class modulo their product.

Small remainders can also certify impossibility. A perfect square has residue zero or one modulo four, as checking the four congruence classes shows. Therefore an integer equation $x^2=4k+2$ has no solution. The converse direction needs care: a permitted residue does not guarantee an integer solution, since $5\equiv 1(\mathrm{mod}4)$ but five is not a perfect square. Such local tests provide necessary conditions for Diophantine equations without replacing the full problem.

In Disquisitiones arithmeticae (1801), Carl Friedrich Gauss defines integer congruence in article 1 and adopts the symbol $\equiv$ in article 2. Article 12 derives divisibility tests from powers of ten and explains checking arithmetic by its remainders. These passages show a systematic treatment of the same idea; they are not a claim that remainders were first used in 1801. ^[ref]

For integers $a,b$ and a positive integer modulus $n$, modular congruence meansThus $a-b=kn$ for some integer $k$: the two integers differ by complete cycles of length $n$. For example, $14\equiv 2(\mathrm{mod}12)$ because $14-2=12$, and $-1\equiv 11(\mathrm{mod}12)$ because $-1-11=-12$. A modular congruence need not be an equality of integers.

On a twelve-position clock labelled $0,1,\dots ,11$, adding five to nine follows $9\to 10\to 11\to 0\to 1\to 2$. Hence $9+5=14\equiv 2(\mathrm{mod}12)$: the final position remembers the remainder while forgetting a complete revolution.

The same idea tracks any count repeating every $n$ steps. It also lets us compute sums and products with small residue classes, reducing intermediate results without changing the final class. The justification comes from addition and multiplication being well-defined on residue classes.

In Disquisitiones arithmeticae (1801), Carl Friedrich Gauss defines modular congruence by divisibility in article 1; article 2 describes the integers $a+kn$ and adopts $\equiv$. These passages document his presentation and notation, without claiming that repeating remainders began in 1801. ^[ref]

For a prime number $p$ and $p\nmid a$, multiplication by $a$ gives a permutation of the $p-1$ nonzero residue classes. For $a=3$ modulo seven, the representatives $1,2,3,4,5,6$ map to $3,6,2,5,1,4$: the same collection in a different order. Repeating this permutation from one visits all six representatives before returning.

For $a=2$ modulo seven, the permutation cycles are instead $(1,2,4)$ and $(3,6,5)$. The powers of two visit only the permutation cycle containing one, so their multiplicative order is three. Both permutation cycles return after three steps; applying the permutation six times still fixes every nonzero residue class. Fermat's little theorem guarantees a return at six, not that every base visits every nonzero residue class.

More generally, every permutation cycle of this map has length equal to the multiplicative order of $a$: starting at a nonzero residue class $x$, a return means $a^{k}x\equiv x(\mathrm{mod}p)$, and its modular multiplicative inverse allows cancellation of $x$. Thus the $p-1$ nonzero residue classes split into equal-length permutation cycles, which also explains the divisibility of the multiplicative order into $p-1$.

The product argument gives a short proof outline. Since multiplication by $a$ is a permutation of the nonzero residue classes,Every factor is a unit, so their product has a modular multiplicative inverse and can be cancelled. This leaves $a^{p-1}\equiv 1(\mathrm{mod}p)$. The whole argument works for $p=2$, where the product is just one.^[ref]

Number theory studies integers, their divisibility, and the patterns created by prime numbers. Its questions often have short statements but rigid answers: which integers divide a given one, when does an equation have integer solutions, and when can arithmetic with congruence classes be reversed? The Euclidean algorithm and modular multiplicative inverses connect these questions through explicit calculations.

For example, $252=2^2\cdot 3^2\cdot 7$ and $198=2\cdot 3^2\cdot 11$. Their shared prime factors give greatest common divisor $18$. The Euclidean algorithm reaches that answer without finding either complete prime factorization. It also produces $18=4\cdot 252-5\cdot 198$, an instance of Bézout's identity. This relation certifies every common divisor at once and solves an associated linear Diophantine equation.

Modular arithmetic retains only remainders, but the lost information can be surprisingly controlled. Multiplication by $5$ modulo $17$ is a permutation of all residue classes, because $5$ has modular inverse $7$. Multiplication by $5$ modulo $15$ collapses fifteen residue classes to three. Thus an apparently small change in the modulus changes whether a calculation can be reversed. The Chinese remainder theorem explains another kind of compression: remainders modulo coprime integers can be combined into one remainder modulo their product.

Simple restrictions help reveal the structure without telling the whole story. Every prime number greater than three is congruent to $1$ or $5$ modulo $6$: the other four residue classes force divisibility by $2$ or $3$. The converse fails because $25$ and $35$ lie in those classes but are composite numbers. Necessary conditions are useful filters, not substitutes for primality testing.

The subject's appeal lies partly in this tension: prime factorization gives a clean description of every positive integer, while identifying factors and predicting their distribution lead to substantial further questions. Analytic number theory uses tools from analysis to study global patterns, and algebraic number theory extends arithmetic into number fields. Applications include cryptography and error-correcting codes; MIT's discrete applied mathematics course develops modular structures for both purposes. ^[ref]

Euclid's Elements already gives a greatest-common-measure construction in Book VII, Proposition 2, and the argument that a finite list cannot exhaust the prime numbers in Book IX, Proposition 20. These are documented ancient treatments, rather than evidence that all of number theory began with one author. ^{[ref] [ref]}

Fix a prime number $p$. Write a nonzero rational number as $x=p^{k}a/b$, where $k\in \mathbb{Z}$ and the nonzero integers $a,b$ are not divisible by $p$. The exponent $k$ is uniquely determined. Its P-adic valuation is this signed exponent $v_p(x)=k$: equivalently, for any nonzero integer numerator $A$ and denominator $B$,Factors of $p$ in the numerator decrease the p-adic absolute value; factors in the denominator increase it. For $p=2$ the computations are:

This is an absolute value on a field measuring divisibility, rather than the magnitude on a real number number line. It satisfiesThe proof comes directly from P-adic valuations: exponents add in a product of numbers, and extracting a common power of $p$ from a sum gives $v_p(x+y)\ge \min \{v_p(x),v_p(y)\}$. If the two P-adic valuations differ, the remaining term with smaller exponent cannot cancel modulo $p$, so equality holds. Thus the p-adic absolute value is a Non-Archimedean absolute value. ^[ref]

The metric $d_p(x,y)=|x-y{|}_p$ makes two rational numbers close when their difference contains a high power of $p$. This packages successive modular congruences into a numerical error estimate, allowing convergence in a metric space and convergent series to encode exact arithmetic information.

An element $a$ is a prime element when it is nonzero and not a unit, and $a\mid bc$ implies $a\mid b$ or $a\mid c$. If $a=bc$ and $a$ is a prime element, assume for example $b=ad$. Cancellation in $a=adc$ gives $dc=1$, so $c$ is a unit. This proves every prime element is an irreducible element.

In a Euclidean domain, each nonzero ideal has a generator of least Euclidean value: division of another member by that generator leaves a remainder in the ideal of smaller value, so the remainder must vanish. Let $a$ be an irreducible element and suppose $a\mid bc$ but $a\nmid b$. Write $(a,b)=(d)$. Since $d\mid a$, irreducibility says $d$ is a unit or is associate to $a$. The second case would give $a\mid b$, so $d$ is a unit. Hence $1=ra+sb$ for some $r,s$. Multiplying by $c$ shows $a\mid c$. Thus irreducibles in a Euclidean domain are prime.

For $R=\mathbb{Z}[i\sqrt{7}]$, use the multiplicative integer field norm $N(m+ni\sqrt{7})=m^2+7n^2$. Units have field norm one and are exactly $\pm 1$. If $2=uv$ were a product of nonunits, their norms would be integers greater than one multiplying to four, hence both would have field norm two. But $m^2+7n^2=2$ has no integer solution: $n\ne 0$ makes the left side at least seven, and $n=0$ would give $m^2=2$. Therefore 2 is an irreducible element.

On the other hand,is divisible by 2, while neither factor is, because divisibility by 2 requires both integer coefficients to be even. Thus 2 is not a prime element in this ring. It is also not a prime element in $\mathbb{Z}[i]$: $2\mid (1+i{)}^2=2i$, but $2\nmid 1+i$. In fact $2=(1+i)(1-i)$ is already a nontrivial factorization there.

The passage belongs to the English reception of Euclid's number theory. Henry Billingsley's The Elements of Geometrie by Henry Billingsley, published in 1570, brought the Elements into English with extensive explanatory material. The original title page advertises translation and annotations; the extract's worked examples show what explanatory prose could add to a compact definition. Henry Billingsley's numbering calls this Definition 23 of Book VII; the familiar modern numbering is VII, Definition 22. The difference is editorial, not a difference in the perfect number being defined.^[ref][ref]

Here a number's parts are its positive proper divisors, rather than arbitrary pieces of a sum or all smaller integers. In modern notation the definition iswhere $\sigma$ is the sum-of-divisors function. Thus $12$ is not a perfect number: its positive proper divisors total $1+2+3+4+6=16$. It is essential to exclude $n$ itself: including it would double the required sum. The pairing of a divisor $d$ with the fraction $1/(n/d)$ of the whole explains the extract's language of halves, thirds and so on. Its examples are complete checks because they identify every positive proper divisor, not merely some convenient decomposition.

The larger mathematical context is the construction in Book IX, Proposition 36. If $q=2^p-1$ is a prime number, then $N=2^{p-1}q$ is a perfect number. To reconstruct the argument, prime factorization gives all its divisors as $2^j$ and $q{2}^j$, with $0\le j\le p-1$. A finite geometric series therefore givesThe choices $p=2,3,5,7$ produce $6,28,496,8128$. The primality assumption matters: choosing $p=4$ produces $120$, whose sum-of-divisors function is $360$, not $240$. The construction gives a reason for the examples and connects perfect numbers with Mersenne primes.^[ref]

The extract itself supplies a definition and examples, not a classification or a mathematical proof that such numbers are rare. In particular, the converse that every even perfect number has this form belongs to the later Euclid-Euler theorem; it should not be read back into this passage. The historically significant feature is the transmission of deductive arithmetic through vernacular explanation: a book called geometry also teaches the divisibility theory needed for a general construction.

For the odd-square sum, the initial case $n=1$ gives $1=(4-1)/3$. Assume the formula at $n$. Adding the next square givesThe initial case and this induction step prove $\boxed{\sum _{j=1}^n(2j-1{)}^2=(4n^3-n)/3}$ for every positive integer $n$.

For the divisibility assertion, $1^3+5\cdot 1=6$. The change when $n$ is replaced by $n+1$ isOne of the consecutive integers $n,n+1$ is even, so the displayed change is divisible by $6$. If $n^3+5n$ is divisible by $6$, its successor is too. Thus induction proves $\boxed{6\mid n^3+5n}$ for every $n\ge 1$.

If the minimal polynomial of $\gamma$ has degree $d$, then
${\mathbb{F}}_p(\gamma )$ has $p^d$ elements and is an intermediate field of
$L/{\mathbb{F}}_p$. The tower law for field extensions givesso $d\mid n$.

The multiplicative group of a finite field is cyclic. Choose a generator
$\gamma$ of $L^{\times }$, of order $p^n-1$. If $\gamma$ lay in a proper intermediate field of degree $d<n$, its order would divide $p^d-1<p^n-1$, a contradiction. Thus
${\mathbb{F}}_p(\gamma )=L$ and its minimal polynomial has degree $n$.

For arbitrary $r\ge 1$, let $E$ be the splitting field of
$X^{p^r}-X$ over ${\mathbb{F}}_p$. Its roots form a field: the Frobenius endomorphism shows they are closed under addition, subtraction, multiplication, and inversion. The derivative is $-1$, so there are exactly $p^r$ distinct roots. Thus this root field has order $p^r$. Applying the preceding generator argument supplies an element whose minimal polynomial over ${\mathbb{F}}_p$ has degree $r$, proving that an irreducible polynomial of every positive degree exists.

The Dedekind factorization theorem says that, when a rational prime $p$ does not divide the index of an order $\mathbb{Z}[\theta ]\subseteq {\mathcal{O}}_K$, a factorizationof the minimal polynomial modulo $p$ gives

Let $K=\mathbb{Q}(\sqrt{d})$ with square-free $d$, and let $p$ be odd. The resulting splitting of rational primes in a quadratic field is:

Finally suppose $d>0$ and
$\alpha =A/C+(B/C)\sqrt{d}$ has norm $-1$, with integers
$A,B,C$ chosen coprime. ThenIf an odd $p\equiv 3(\mathrm{mod}4)$ ramified, then $p\mid d$. Reduction modulo $p$ gives
$A^2\equiv -C^2(\mathrm{mod}p)$. Since $-1$ is not a square modulo such a prime, $p\mid A,C$. Dividing the equation's divisibility shows $p\mid B$ as well (use that square-free $d$ has $p$-adic valuation one), contradicting coprimality. Hence no prime $p\equiv 3(\mathrm{mod}4)$ ramifies.

The set $S_n$ is nonempty because $n\in S_n$. By the well-ordering principle for the natural numbers, it has a least element $p$. In particular $p>1$ and $p$ divides $n$.

If $p$ were not a prime number, it would have a positive integer divisor $d$ with $1<d<p$. Since $d$ divides $p$ and $p$ divides $n$, divisibility is transitive and $d$ divides $n$. This would put $d$ in $S_n$, contradicting the minimality of $p$. Hence $\boxed{p\text{ is prime}}$.

Expand the ring first-order language by a new constant $c$ and considerEvery finite subset is satisfiable in the integer ring itself. Only finitely many divisibility conditions occur; interpret $c$ as a nonzero common multiple of their positive integer indices, using $1$ if none occur. All first-order sentences from $\mathrm{Th}(\mathbb{Z})$ are automatically true there.

Compactness theorem therefore gives a first-order model. Its reduct $R$ to the original ring first-order language satisfies the complete theory of $\mathbb{Z}$, so $R\equiv \mathbb{Z}$. Its element $c^R$ is nonzero and divisible by every positive standard integer. ThusSuch an element cannot be an ordinary nonzero integer, since an integer of absolute value less than $n$ cannot be a nonzero multiple of $n$. The statement concerns each standard integer index separately; it does not assert divisibility by every internally nonzero element of $R$.

Enumerate the standard positive primes as $(p_n{)}_{n<\omega }$. For each subset $A\subseteq \omega$ consider the partial typewhere divisibility is the ring logical formula $\exists y({\bar{p}}_{n}y=x)$.

Every finite subset is realized in $\mathbb{Z}$: take the product of the finitely many primes required to divide $x$, or $1$ if there are none. This is nonzero and is not divisible by any of the distinct finitely many primes required not to divide it. Compactness theorem supplies a complete type extending $q_A$.

Distinct subsets $A,B$ yield distinct complete extensions, because at an index in their symmetric difference they require opposite divisibility statements. There are $2^{{\aleph }_0}$ such subsets, so there are at least that many complete one-types. There are at most that many because the first-order language has only countably many logical formulas and a partial type is a set of them. HenceIn particular the number of complete one-types is uncountable, despite every partial type realized in the particular countable first-order model $\mathcal{Z}$ being a principal complete type.

Fermat's little theorem states that for a prime $p$ and an integer $a$ not divisible by $p$,Equivalently, $a^p\equiv a(\mathrm{mod}p)$ for every integer $a$, with divisibility by $p$ allowed in that latter formulation.