Arithmetic Functions

$72 = 2^3\cdot3^2$, and $2^3$, $3^2$ are coprime, so each function is a product of two prime-power values. $\tau = (3 + 1)(2 + 1) = 12$. $\sigma = (1 + 2 + 4 + 8)(1 + 3 + 9) = 15\cdot13 = 195$ — in the grid, each row sums to $15$ times its power of $3$. $\varphi = (8 - 4)(9 - 3) = 24$.

Show $496$ is perfect. $496 = 16\cdot31 = 2^4\cdot31$ with $31$ prime. So $\sigma(496) = \sigma(2^4)\sigma(31) = 31\cdot32 = 992 = 2\cdot496$. The divisors other than $496$ itself sum to $496$. Every even perfect number has this shape, $2^{k-1}(2^k - 1)$ with $2^k - 1$ prime (Euclid and Euler).

Since $\varphi(n)/n = \prod_{p \mid n}(1 - 1/p)$ depends only on WHICH primes divide $n$, look for prime sets with $\prod(p - 1)/p = 1/3$, i.e. $3\prod(p - 1) = \prod p$. The right side must be a multiple of $3$, so $3$ is in the set; cancelling it leaves $2\prod_{\text{rest}}(p - 1) = \prod_{\text{rest}} p$, so $2$ is in too, and then $\prod(p-1) = \prod p$ over the remaining primes forces there to be none. So $\varphi(n) = n/3$ exactly when $n = 2^a3^b$ with $a, b \ge 1$ — e.g. $\varphi(12) = 4$.

The fractions $\tfrac1{12}, \tfrac2{12}, \ldots, \tfrac{12}{12}$ reduce to fractions whose denominators divide $12$. A reduced fraction $\tfrac kd$ with $1 \le k \le d$ has $\gcd(k, d) = 1$, so exactly $\varphi(d)$ of them have denominator $d$. Column by column: $\varphi(1) + \varphi(2) + \varphi(3) + \varphi(4) + \varphi(6) + \varphi(12) = 1 + 1 + 2 + 2 + 2 + 4 = 12$.

List: the divisors of $12$ are $1, 2, 3, 4, 6, 12$, sum $28$. Factor: $\sigma(12) = \sigma(4)\sigma(3) = (1 + 2 + 4)(1 + 3) = 7\cdot4 = 28$. Expanding $(1 + 2 + 4)(1 + 3)$ produces each product $2^i3^j$ exactly once — which is each divisor exactly once. That is the whole proof of multiplicativity in one line.

$\tau(72) = 12$. Pair each divisor $d$ with $72/d$: $1\cdot72$, $2\cdot36$, $3\cdot24$, $4\cdot18$, $6\cdot12$, $8\cdot9$ — six pairs, each with product $72$. So the product of all divisors is $72^6$, in agreement with $n^{\tau(n)/2} = 72^{12/2}$.

Factor the count: $12 = 12 = 6\cdot2 = 4\cdot3 = 3\cdot2\cdot2$, so the exponent patterns are $(11)$, $(5, 1)$, $(3, 2)$, $(2, 1, 1)$. Put the biggest exponent on the smallest prime: $2^{11} = 2048$, $2^5\cdot3 = 96$, $2^3\cdot3^2 = 72$, $2^2\cdot3\cdot5 = 60$. The smallest is $60$.

Which $n \le 100$ have an odd number of divisors? Pair each divisor $d$ with $n/d$. The pairs account for an even number of divisors, and a divisor is unpaired only when $d = n/d$, i.e. $d^2 = n$. So $\tau(n)$ is odd exactly when $n$ is a perfect square: $1, 4, 9, \ldots, 100$, ten numbers. (The classic "lockers" puzzle is this fact in disguise.)

How many $n \le 1000$ have exactly $3$ divisors? $3$ is prime, so the only pattern is $e + 1 = 3$: $n = p^2$. Need $p^2 \le 1000$, i.e. $p \le 31$ (as $31^2 = 961$ and $37^2 > 1000$). The primes $2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31$ give $11$ such $n$.