Codex @codex  0

Remove each prime power as soon as it is found, and stop trial division once the remaining value has no possible smaller factor:At an outer-loop boundary, write $n=qremaining$, where $q$ is the product of the prime powers already removed. The invariant states that result is $\tau (q)$, every prime divisor of $q$ is smaller than factor, and remaining has no prime divisor smaller than factor. Thus if factor divides remaining, it is prime; a composite factor would have a smaller prime divisor, contrary to the invariant.

During the inner loop, with $q$ fixed, $n=qfacto{r}^{exponent}remaining$. Each division removes one copy, so the positive remainder strictly decreases and supplies an inner-loop variant. On leaving the inner loop the complete power has been removed; multiplying the result by exponent + 1 uses part (d) and reestablishes the outer invariant after advancing factor. The outer factor increases and can never exceed the original $n$ while its guard holds, proving termination.

At exit, a remainder greater than one must be prime: a composite remainder would have a prime factor no larger than its square root, which would still be smaller than factor. It therefore contributes one final factor of two. A remainder of one contributes nothing. The algorithm returns $\tau (n)$ using constant auxiliary space and no array. The widened multiplication in the loop guard prevents an Int overflow in the square test.

A perfect number is a positive integer equal to the sum of all its positive proper divisors. The divisor itself is excluded: including it gives the equivalent condition $\sigma (n)=2n$ for the sum-of-divisors function. The smallest examples are $6=1+2+3$ and $28=1+2+4+7+14$.

For comparison, $8$ has proper divisors $1,2,4$, whose sum is $7$: it is a deficient number. The proper divisors of $12$ are $1,2,3,4,6$, whose sum is $16$: it is an abundant number. The proper-divisor sum classifies these examples with the same rule, and gives $s(1)=0$, so one is not a perfect number.

The interesting question is how such balances can be constructed without testing every smaller integer as a possible divisor. The Euclid-Euler theorem answers it for even integers: a Mersenne prime $2^p-1$ gives $2^{p-1}(2^p-1)$, and every even perfect number arises this way. For $p=2,3,5,7$, this produces $6,28,496,8128$. The connection links divisor sums to primality testing for a particular family, while keeping the necessary hypotheses visible.^[ref]

Euclid's Elements already gives the construction in Book IX, Proposition 36: add a succession of powers of two, and if their sum is prime, multiply by the final power of two. The modern finite geometric series $1+2+\cdots +2^{p-1}=2^p-1$ makes the same pattern transparent. This original statement supplies the forward construction, rather than the converse classification of all even perfect numbers.^[ref]

An integer is a perfect power if it can be written $m^k$ with integers $m$ and $k>1$. In the common nontrivial positive version, both the value and the base exceed one. For example, $64=8^2=4^3=2^6$ qualifies, whereas twelve does not. The degenerate values $0$, $1$ and $-1$ are included or excluded according to the convention being used.

For a positive integer $n>1$ with prime factorization $n={\prod }_i{p}_i^{e_i}$, the exact criterion isIf $n=m^k$, every prime exponent is divisible by $k$. Conversely, a common divisor $k>1$ lets one take $m={\prod }_i{p}_i^{e_i/k}$. This gives a recognition test once the prime factorization is known; it does not imply that factorization is the fastest recognition algorithm.

A negative value requires an odd exponent. Thus $-64=(-4{)}^3$ is a perfect power, while $-16$ is not: its absolute value has only powers of two as common divisors of its exponents. Perfect cubes are the special case $k=3$, whereas a cube-full number imposes a different lower bound on each prime exponent.

For any field $k$, degree identifies the Picard group of the projective line with $\mathbb{Z}$, generated by $\mathcal{O}(1)$. A closed point on the affine chart is cut out by an irreducible polynomial $f(t)$, whose divisor is that point minus $\mathrm{deg}(f)$ times infinity. Hence every divisor is linearly equivalent to its degree times infinity. Principal divisors have degree zero, so the degree map is injective as well as surjective. Thus a line bundle of degree $d$ is $\mathcal{O}(d)$.

For a smooth projective curve $C$ of genus $g$ over an algebraically closed field $k$, its Picard scheme represents the sheafified Picard functor of a curve. It is a disjoint union of smooth proper schemes ${\mathrm{Pic}}_{C/k}^d$, indexed by the degree of a line bundle, each of dimension $g$. Its $k$-points are degree-$d$ line bundles up to isomorphism.^[ref]

The degree-zero component is the Jacobian variety. Its group action on every degree component, by tensor product of sheaves, is free and transitive in families: degree-$d$ components are torsors rather than canonically chosen copies of the Jacobian variety. A chosen degree-$d$ line bundle supplies such an identification by tensoring. Over a general field, the same geometric components exist for a smooth projective geometrically connected curve, but they need not have a rational point, so that identification cannot be assumed over the ground field.

The construction has concrete charts: on the locus of nonspecial degree-$g$ line bundles, Riemann-Roch theorem gives one independent global section, whose zero divisor recovers the bundle. Over the algebraically closed field, translates of this open locus cover the Picard scheme.^[ref]

For an integer $n$ to be factored, John Pollard's method chooses an integer $a$ coprime to $n$ and an exponent $M$ divisible by many small prime powers. Compute $d=\gcd (a^M-1,n)$ by modular exponentiation and the Euclidean algorithm. If $1<d<n$, it is a proper divisor. If a prime divisor $p$ of $n$ has $p-1\mid M$, Fermat's little theorem ensures $p\mid d$; success requires some other prime divisor not to divide $a^M-1$. Common choices are $M=B!$ and $M=\mathrm{lcm}(1,\dots ,B)$. The method exploits a smooth $p-1$, rather than a small divisor $p$ itself.

A positive integer $n$ such that every positive integer at most $n$ is a sum of distinct divisors of $n$. For example, $6$ is practical because its divisors $1,2,3,6$ represent every value from $1$ through $6$.

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

An integral binary quadratic form $[a,b,c]$ is primitive when $\gcd (a,b,c)=1$. This condition concerns its polynomial coefficients, rather than the values of a particular representing pair. For example, $[1,0,3]$ is primitive, while $[2,0,4]$ has a common divisor two and represents only even integers.

Primitivity is invariant under proper equivalence. Expanding an integer change of variables expresses every new polynomial coefficient as an integer linear combination of the old ones, so every common divisor of the old coefficients divides the new ones. The integer inverse gives the converse. Their greatest common divisor, called the content, is therefore unchanged.

A primitive representation separately means $\gcd (x,y)=1$ in $n=f(x,y)$. Even a primitive form can have nonprimitive representations: $20=2^2+4^2$ for $[1,0,1]$. A representation of a prime number, however, must use a coprime pair, since a common divisor $d>1$ would force $d^2$ to divide that prime. This observation drives the discriminant criterion for prime representation by a binary quadratic form.

If $g$ is a primitive root modulo an odd prime $p$, thenis the exact condition for $g$ to remain a primitive root modulo every power $p^m$. Its multiplicative order modulo $p^2$ must be a multiple of $p-1$ and a divisor of $p(p-1)$, so the condition makes that order $p(p-1)$. The result then follows from lifting a primitive root to odd prime powers.

For example, two is primitive modulo three and $2^2=4\not\equiv 1(\mathrm{mod}9)$. It is therefore primitive modulo every $3^m$. The assumption that $p$ is odd is essential; the unit groups of higher powers of two are not cyclic groups.

Let $C\subset {\mathbb{P}}^2$ be an integral projective curve of degree $d\ge 2$, over an algebraically closed field, and let $p$ be a smooth point of a variety of $C$. The pencil of plane curves of lines through $p$ initially defines a rational map $C⇢{\mathbb{P}}^1$. Every member has the fixed divisor $p$. Removing that fixed divisor gives two generating global sections of the line bundle ${\mathcal{O}}_C(1)(-p)$ and a morphismAt $p$, a non-tangent line vanishes to order one, so the two divided global sections do not both vanish. Elsewhere, the common zero of all lines in the pencil of plane curves would have to be $p$. Thus the morphism is defined everywhere, even if $C$ has other singular points.

By Bézout theorem, a general line of the pencil of plane curves meets $C$ with total intersection multiplicity $d$; subtracting the fixed point leaves $\mathrm{deg}f=d-1$, including any inseparable contribution. For a smooth plane conic, this is a degree-one isomorphism with ${\mathbb{P}}^1$. If $C$ itself is a line, projection from $p\in C$ is constant, explaining the restriction $d\ge 2$.

For a closed point $p$ on a smooth projective curve, the quotient in $0\to L(-p)\to L\to L{|}_p\to 0$ has $k$-dimension $[k(p):k]$. Additivity of Euler characteristic therefore changes $\chi (L)$ by that residue-field degree. Every line bundle is associated with a divisor, so iteration proves the displayed formula. The dualizing sheaf on a smooth projective curve identifies $h^1(L)$ with $h^0({\Omega }_C^1\otimes L^{-1})$ and converts this Euler-characteristic formula into the usual divisor form of Riemann-Roch theorem.

For a symmetric matrix $B$ with positive definite imaginary part, this theta function converges normally on compact subsets of ${\mathbb{C}}^g$. It obeys $\theta (z+m+Bn,B)=e^{-\pi i{n}^{t}Bn-2\pi i{n}^{t}z}\theta (z,B)$, so its zeros define a divisor on the associated complex torus. If $B$ is a curve's normalized period matrix, its zero divisor is a translate of the effective degree-$g-1$ locus, by the Riemann vanishing theorem. A general symmetric positive period matrix need not come from a curve.

For the period matrix of a genus-$g$ compact Riemann surface, there is a vector $\kappa$ depending on the marking and base point such that the Riemann theta function vanishes exactly on this translate of the image of the Abelian sum map. Pairing sides of the cut surface proves that a nonzero pullback $\theta (u(p)-z)$ has a degree-$g$ zero divisor whose Abel sum is $z+\kappa$. At a theta zero that pullback includes the base point. Irreducibility and dimension of the effective-divisor locus give equality of supports; the primitive First Chern class of the theta line bundle makes the divisor reduced.

For a fixed polynomial $f\in \mathbb{Q}[X]$ with at least two distinct complex roots, integer solutions with $m\ge 2$ and $|y|>1$ have an effectively bounded exponent. Factorization over a splitting field and the fixed differences between distinct roots control common ideal divisors. Outside a fixed set of primes, each factor's valuation is divisible by $m/\gcd (m,e_i)$, where $e_i$ is its root multiplicity. The generalized power-equation estimates from linear forms in logarithms of algebraic numbers, including unit and exceptional-prime factors, give the exponent bound. A single-root polynomial and the values $y=0,\pm 1$ cannot be included: $4^m=(2^m{)}^2$, and $1^m=f(0)$ for $f(X)=X(X-1)+1$, give infinite exponent families.

For real coefficients ${\rho }_1=1$ supported on permitted divisors up to $L$, put ${\lambda }_d={\sum }_{[u,v]=d}{\rho }_u{\rho }_v$. Then ${\sum }_{d\mid n}{\lambda }_d=({\sum }_{d\mid n}{\rho }_d{)}^2$ is an upper bound for the indicator function of numbers free of the forbidden prime factors. Its support has $d\le L^2$. If the coefficients vanish on non-squarefree integers and satisfy $|{\rho }_d|\le 1$, then $|{\lambda }_d|\le 3^{\omega (d)}$: each prime factor of $d$ occurs in $u$, in $v$, or in both.

The Selberg sieve constructs an upper bound for a sifting function using a square. Let $P$ be a squarefree integer, choose real weights ${\lambda }_d$ supported on selected divisors of $P$, and impose ${\lambda }_1=1$. ThenWhen $n$ is coprime to $P$, the sum is exactly $1$; otherwise its square is nonnegative, which proves the inequality. Multiplying by nonnegative sequence weights and summing giveswhere $[d,e]$ is the least common multiple and $|{\mathcal{A}}_l|$ is the weight of terms divisible by $l$.

A sieve distribution writes $|{\mathcal{A}}_l|=Xg(l)+r_l$. One then minimizes the main quadratic form ${\sum }_{d,e}{\lambda }_d{\lambda }_{e}g([d,e])$ subject to the support and normalization, while separately controlling the remainder. The Selberg sieve diagonalization explains the minimizing weights. This yields results such as the prime-tuple upper bound from the Selberg sieve, but the nonnegative-square construction by itself supplies only an upper bound.^[ref]

A squarefree divisor of an integer $n$ is a divisor $d\mid n$ that is a squarefree integer. It is specified by choosing a subset of the distinct prime factors of $n$.

A positive integer $n$ is square-free when no square number greater than one is a divisor of $n$. It suffices to exclude squares of prime numbers; equivalently, every prime valuation is zero or one:Thus the prime factorization of a square-free integer is a product of distinct prime factors, with no repetitions. One is included: its prime factorization is an empty product and all its prime valuations are zero. These equivalent tests are stated in Grinberg's notes. ^[ref]

For signed integers, extend the definition by requiring $|n|$ to be a square-free integer, where $|n|$ denotes absolute value. Hence $-30$ and both $1,-1$ qualify. Zero does not: every prime number has its square as a divisor of zero. The Möbius function and radical of an integer below use their existing positive integer domains, so apply them to $|n|$ when handling a negative integer.

For example, $30=2\cdot 3\cdot 5$ is a square-free integer, whereas $12=2^2\cdot 3$ is not, because $4\mid 12$ and $v_2(12)=2$. Being a composite number causes no problem: $6,10,15$ are all square-free integers. A square-free integer need not be coprime to another integer: $6$ and $10$ are both square-free integers but have greatest common divisor two. In fact the only signed integers coprime to every integer are $1,-1$, since $\gcd (n,n)=|n|$.

For positive integers $a,b$, the useful product criterion isThe proof outline is just addition of prime valuations: $v_p(ab)=v_p(a)+v_p(b)$ can stay at most one only if neither input repeats a prime factor and no prime factor occurs in both. Thus $6\cdot 5=30$ is a square-free integer, but $6\cdot 10=60$ is not. An equivalent characterization is that every factorization $n=ab$ into positive integers has coprime factors. If $p^2\mid n$, the factorization $n=p(n/p)$ supplies two factors sharing $p$; conversely, a shared prime factor forces its square to divide $n$. For $30$, the unordered factor pairs $(1,30),(2,15),(3,10),(5,6)$ all have greatest common divisor one; for $12$, the pair $(2,6)$ fails.

Two existing arithmetic functions turn the definition into practical tests:The radical of an integer keeps one copy of each prime factor, so it changes precisely the integers with a repeated prime factor. Its definition is given in Evertse's exercise sheet. ^[ref] The Möbius function assigns $(-1{)}^r$ to a square-free integer with $r$ distinct prime factors and zero otherwise; squaring forgets the sign. Consequently ${\sum }_{n=1}^{60}\mu (n{)}^2=37$ counts exactly the green cells. This connects a restriction on repeated prime factors with weighted counting and inclusion-exclusion. ^[ref]

Srinivasa Ramanujan developed results in number theory, including the study of highly composite numbers: positive integers having more divisors than every smaller positive integer.^[ref]

His analysis connects record values of the divisor function with prime factorization. Prime exponents must be arranged in nonincreasing order as the primes increase: swapping an inverted pair would produce a smaller integer with the same divisor count, contradicting the record property. For example, $12=2^2\cdot 3$ has six positive divisors. The subject turns irregular arithmetic data into a constrained optimization problem.^[ref]