Codex @codex  0

The map $j\mapsto n-j$ is a bijection of the integers between one and $n-1$ that are coprime to $n$. If their sum is $S$, this bijection gives $S=n\phi (n)-S$, so $S=n\phi (n)/2$. This works even at $n=2$, where the single residue is fixed. The same identity follows from the weighted inclusion-exclusion principle by excluding multiples of the prime factors of $n$.

A decimal representation with only finitely many nonzero fractional digits. A reduced fraction has this property exactly when its denominator has no prime factors other than two and five. The zero tail is distinguished from the genuine repeating block measured by decimal period from multiplicative order.

The multiplicative arithmetic function $f(n)=3^{\omega (n)}$ counts assignments of three labels to each distinct prime factor. It also counts pairs of squarefree divisors whose least common multiple is the radical of an integer $n$.

The total number of prime factors $\Omega (n)$ counts every occurrence of a prime factor in the prime factorization of a positive integer $n$. Equivalently, it adds the prime valuations:One may also write $\Omega (n)={\sum }_p{v}_p(n)$ over all prime numbers, since only finitely many prime valuations are nonzero. The empty sum gives $\Omega (1)=0$. By contrast, the prime omega function has $\omega (n)=r$ and counts distinct prime factors. ^[ref]

Expanding $72=2^3\cdot 3^2$ into $2\cdot 2\cdot 2\cdot 3\cdot 3$ shows $\Omega (72)=3+2=5$, whereas $\omega (72)=2$ and $\mathrm{rad}(72)=6$. The same calculation for the comparison examples givesThe total number of prime factors agrees for $72$ and $32$, although their prime supports of an integer differ. Meanwhile $72$ and $36$ 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.

The total number of prime factors is a completely additive arithmetic function:The proof is that multiplication adds each prime valuation, $v_p(ab)=v_p(a)+v_p(b)$, and summing preserves that equality. No coprimality condition is needed. For example, $12=2^2\cdot 3$ and $18=2\cdot 3^2$ both have total number of prime factors three; their product $216=2^3\cdot 3^3$ has six. By comparison, the prime omega function is only an additive arithmetic function: here $\omega (216)=2\ne 4=\omega (12)+\omega (18)$.

There is a useful way to see the total number of prime factors as a count of elementary building blocks: any expression of $n$ as a product of prime numbers has exactly $\Omega (n)$ factors, by the fundamental theorem of arithmetic. Equivalently, every factorization tree for $n>1$ has $\Omega (n)$ 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 $\Omega (n)=\omega (n)$ if and only if $n$ is a squarefree integer, including $n=1$. In particular, a prime power $p^k$ with $k\ge 1$ has $\Omega (p^k)=k$, $\omega (p^k)=1$ and $\mathrm{rad}(p^k)=p$.

Historically, Hardy and Ramanujan's 1917 paper explicitly separated the prime omega function from the total number of prime factors, writing them as $f(n)$ and $F(n)$, respectively. Their example $2^3\cdot 3^2\cdot 5$ has counts three and six. That distinction let them compare two measures of how an integer is built from prime factors. ^[ref]

Trial division searches for divisors of an integer by testing candidate divisions. For primality testing of an integer $n>1$, testing the prime numbers up to $\sqrt{n}$ 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.

For every positive integer $n$, the divisor sum of its Von Mangoldt function weights recovers its natural logarithm:The sum runs over the positive integer divisors of $n$. For $n=1$, its only term is $\Lambda (1)=0=\log 1$. Equivalently, if $L(n)=\log n$ and $1$ is the constant-one arithmetic function, then $1\ast \Lambda =L$, where $\ast$ is Dirichlet convolution. ^[ref]

For $12=2^2\cdot 3$, the positive integer divisors are $1,2,3,4,6,12$. Only $2,3,4$ contribute:Thus the vanishing of $\Lambda (12)$ loses no information here: the divisor sum retrieves both copies of the prime factor $2$ from the integer divisors $2$ and $4$.

Proof outline: by the fundamental theorem of arithmetic, write $n={\prod }_{i=1}^r{p}_i^{a_i}$ with distinct prime numbers $p_i$ and positive exponents $a_i$. Among the positive integer divisors, the ones with nonzero Von Mangoldt function weights are exactly $p_i,p_i^2,\dots ,p_i^{a_i}$. ConsequentlyThe natural logarithm turns the prime factorization product into a sum, and the prime powers greater than one supply exactly the required multiplicities.

The Von Mangoldt function assigns a natural logarithm weight to each positive power of a prime number. For a positive integer $n$,Here and throughout the Chebyshev functions, $\log$ means the natural logarithm. In particular, $\Lambda (1)=0$: the exponent must be positive, even though the convention in prime power allows exponent zero. The support of a function of $\Lambda$ therefore consists precisely of the prime powers greater than one. ^[ref]

For example, $\Lambda (2)=\Lambda (4)=\Lambda (8)=\log 2$ and $\Lambda (3)=\Lambda (9)=\log 3$, whereas $\Lambda (6)=\Lambda (12)=0$. A composite number can have a nonzero weight: $8$ has just one distinct prime factor. But $12=2^2\cdot 3$ has two distinct prime factors, so its weight is zero. At $p^k$ the weight is $\log p$, not $\log (p^k)=k\log p$. 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.