Numbers, phi(n) and sigma(n)

phi(n) and sigma(n)

For any positive integer n, the function div(n) is the number of positive divisors of n, including 1 and n.

The function φ(n) is the number of elements relatively prime to n. This is also called the Euler totient function.

The function σ(n) is the sum of all the divisors of n.

A number is perfect if σ(n) is exactly twice n. The number is deficient if σ(n) is less than 2n, and abundant if σ(n) exceeds 2n. N is "almost perfect" if σ(n) = 2n-1, and "quasi perfect" if σ(n) = 2n+1. If n is a power of 2, such as 16, σ(n) is 1+2+4+8+16 = 31, making n almost perfect. No quasi perfect numbers are known.

Once n is factored, div, φ, and σ are easily calculated. Consider 45 = 3 squared times 5. Each factor has zero one or two instances of the prime 3, and zero or 1 instances of the prime 5. That's 3 possibilities cross 2 possibilities, or 6 distinct factors. The factors are 1, 3, 9, 5, 15, and 45. If the factorization of n includes j primes, having exponents e1 e2 … ej, add one to all the exponents and multiply them together to get div(n). Compute φ(n) by counting the numbers below n that are coprime to n. Verify that c is coprime to n iff it is coprime to all the prime factors of n. Thanks to the chinese remainder theorem, the values of c mod n are determined by the values of c mod the prime factors of n. Thus we can count the values coprime to pe, for each p dividing n, and multiply these quantities together to obtain the number of values coprime to n. The values coprime to pe are precisely the numbers not divisible by p, namely pe-pe-1. Returning to φ(45), multiply 9-3 by 5-1 to obtain 24.

To compute σ(45), realize that the divisors can be partitioned into those that are not divisible by 3, those that have one factor of 3, and those that have 2 factors of 3. In each case, the powers of 3, if any, are applied to 1 and 5. Thus σ(45) is (1+3+9) × (1+5), or 13×6, or 78. Verify this by adding 1+3+9+5+15+45. since 78 is less than 90, 45 is deficient, as are most numbers.

Like div(n) and φ(n), σ(n) is a product of expressions, one expression for each distinct prime dividing n. In this case the expression associated with p^e is the sum of the powers of p: 1+p+p²+p³+…+p^e. For instance, σ(168) = (1+2+4+8) × (1+3) times (1+7) = 480, an abundant number.

Verify that σ(s×t) is σ(s) × σ(t), provided s and t are relatively prime. This is called a multiplicative function. Note that div(n) and φ(n) are also multiplicative functions.

If x = σ(n), and k is coprime to n, σ(kn) > kx. In other words, bringing in more factors increases σ faster than n. This is because each prime factor p in k contributes at least p+1 to σ. Similarly, increasing the exponent on a prime in n increases σ faster than n. If σ includes the factor 1+p, and we bring in another p, n is multiplied by p, but σ(n) is multiplied by (1+p+p²)/(1+p), which is a ratio larger than p. Once a number is abundant, all multiples of that number are abundant.