Sum of two squares theorem Created 2026-09-24 Updated 2026-11-05
A positive integer is a sum of two squares of integers exactly when every prime factor congruent to three modulo four has an even prime exponent in its prime factorization. The zero-square convention permits ; zero itself separately has .
For necessity, let divide . If , then , contradicting Euler's criterion for minus one at such a prime. Hence , and then as well. Divide both coordinates by and repeat. Each removal subtracts two from the prime valuation of , forcing it to be even.
For sufficiency, two is . A prime number congruent to one modulo four has a square root of minus one by Euler's criterion, and the congruence lattice proof of the prime sum of two squares turns that root into a representation of the prime. Each even power of a prime congruent to three modulo four is already a perfect square, hence a sum of two squares with a zero term. Finally, the Brahmagupta-Fibonacci identity combines the representations across all prime powers in .
For example, qualifies, while does not. The criterion examines prime exponents, rather than only the residue of the whole number modulo four.
Total number of prime factors Created 2026-10-06 Updated 2026-11-05
The total number of prime factors counts every occurrence of a prime factor in the prime factorization of a positive integer . Equivalently, it adds the prime valuations:
One may also write over all prime numbers, since only finitely many prime valuations are nonzero. The empty sum gives . By contrast, the prime omega function has and counts distinct prime factors. [ref]
Expanding into shows , whereas and . The same calculation for the comparison examples gives
The total number of prime factors agrees for and , although their prime supports of an integer differ. Meanwhile and have the same radical of an integer and prime omega function, but different values of the total number of prime factors. These examples show exactly which information each arithmetic function forgets.
Figure 1.
One box per prime factor occurrence: the total number of prime factors counts boxes, the prime omega function counts groups, and the radical of an integer multiplies one prime number from each group
. Details.
The total number of prime factors is a completely additive arithmetic function:
The proof is that multiplication adds each prime valuation, , and summing preserves that equality. No coprimality condition is needed. For example, and both have total number of prime factors three; their product has six. By comparison, the prime omega function is only an additive arithmetic function: here .
There is a useful way to see the total number of prime factors as a count of elementary building blocks: any expression of as a product of prime numbers has exactly factors, by the fundamental theorem of arithmetic. Equivalently, every factorization tree for has leaves. Repeated prime factors increase this count without introducing new kinds of prime number. The difference is the existing excess prime-factor multiplicity:
Every summand is nonnegative, so if and only if is a squarefree integer, including . In particular, a prime power with has , and .
Historically, Hardy and Ramanujan's 1917 paper explicitly separated the prime omega function from the total number of prime factors, writing them as and , respectively. Their example has counts three and six. That distinction let them compare two measures of how an integer is built from prime factors. [ref]
Trial division 2026-10-14
Trial division searches for divisors of an integer by testing candidate divisions. For primality testing of an integer , testing the prime numbers up to suffices: any composite number has a prime factor in that range. After finding a prime factor, repeated division removes its prime power, and testing the remaining quotient gives an elementary integer factorization method. This is useful for small inputs, but the number of candidates can grow rapidly with the input's digit count.
Trial-division divisor counting Created 2026-10-25 Updated 2026-11-05
Factor a positive integer while multiplying the exponent-plus-one contributions to its divisor count. After removing all prime factors below the current trial factor, a trial factor that divides the remainder must itself be prime. Remove its full power and advance. Once the trial factor's square exceeds the remainder, any remainder greater than one is prime and contributes a factor two. The invariant separates the original integer into removed prime powers and the remaining coprime factor; no factor array is necessary.
Unitary divisor 2026-10-20
A divisor of a positive integer is unitary when . Each prime power in the prime factorization of must therefore be included in completely or omitted completely. Consequently, the sum of the -th powers of unitary divisors is .
Von Mangoldt divisor identity Created 2026-09-24 Updated 2026-10-14
For every positive integer , the divisor sum of its Von Mangoldt function weights recovers its natural logarithm:
The sum runs over the positive integer divisors of . For , its only term is . Equivalently, if and is the constant-one arithmetic function, then , where is Dirichlet convolution. [ref]
For , the positive integer divisors are . Only contribute:
Thus the vanishing of loses no information here: the divisor sum retrieves both copies of the prime factor from the integer divisors and .
Figure 1.
The Von Mangoldt divisor identity assembles from three nonzero divisor weights
. The six positive integer divisors of appear in increasing order. Blue bars contribute at and ; the orange bar contributes at . The remaining three weights are zero. The adjacent stacked bar shows the total . Details.
Proof outline: by the fundamental theorem of arithmetic, write with distinct prime numbers and positive exponents . Among the positive integer divisors, the ones with nonzero Von Mangoldt function weights are exactly . Consequently
The natural logarithm turns the prime factorization product into a sum, and the prime powers greater than one supply exactly the required multiplicities.
Von Mangoldt function Created 2026-09-24 Updated 2026-11-05
The Von Mangoldt function assigns a natural logarithm weight to each positive power of a prime number. For a positive integer ,
Here and throughout the Chebyshev functions, means the natural logarithm. In particular, : the exponent must be positive, even though the convention in prime power allows exponent zero. The support of a function of therefore consists precisely of the prime powers greater than one. [ref]
For example, and , whereas . A composite number can have a nonzero weight: has just one distinct prime factor. But has two distinct prime factors, so its weight is zero. At the weight is , not . This choice lets successive powers record successive copies of the same prime factor in the Von Mangoldt divisor identity.
The Von Mangoldt function is useful because it connects two views of the prime numbers: the prime factorization of an individual integer, through a divisor sum, and the accumulated weights below a cutoff, through the second Chebyshev function. The latter turns questions about the distribution of prime numbers into questions about a partial sum of an arithmetic function.