# proof that $\tau(n)$ is the number of positive divisors of $n$

The following is a proof that $\tau$ counts the positive divisors of its input (which must be a positive integer).

###### Proof.

Recall that $\tau$ behaves according to the following two rules:

1. 1.

If $p$ is a prime and $k$ is a nonnegative integer, then $\tau(p^{k})=k+1$.

2. 2.

If $\gcd(a,b)=1$, then $\tau(ab)=\tau(a)\tau(b)$.

Let $p$ be a prime. Then $p^{0}=1$. Note that 1 is the only positive divisor of 1 and $\tau(1)=\tau(p^{0})=0+1=1$.

Suppose that, for all positive integers $m$ smaller than $z\in\mathbb{Z}$ with $z>1$, the number of positive divisors of $m$ is $\tau(m)$. Since $z>1$, there exists a prime divisor $p$ of $z$. Let $k$ be a positive integer such that $p^{k}$ exactly divides $z$. Let $a$ be a positive integer such that $z=p^{k}a$. Then $\gcd(a,p)=1$. Thus, $\gcd(a,p^{k})=1$. Since $1\leq a, by the induction hypothesis, there are $\tau(a)$ positive divisors of $a$.

Let $d$ be a positive divisor of $z$. Let $y$ be a nonnegative integer such that $p^{y}$ exactly divides $d$. Thus, $0\leq y\leq x$, and there are $k+1$ choices for $y$. Let $c$ be a positive integer such that $d=p^{y}c$. Then $\gcd(c,p)=1$. Since $c$ divides $d$ and $d$ divides $z$, we conclude that $c$ divides $z$. Since $c$ divides $p^{k}a$ and $\gcd(c,p)=1$, it must be the case that $c$ divides $a$. Thus, there are $\tau(a)$ choices for $c$. Since there are $k+1$ choices for $y$ and there are $\tau(a)$ choices for $c$, there are $(k+1)\tau(a)$ choices for $d$. Hence, there are $(k+1)\tau(a)$ positive divisors of $z$. Since $\tau(z)=\tau(p^{k}a)=\tau(p^{k})\tau(a)=(k+1)\tau(a)$, it follows that, for every positive integer $n$, the number of positive divisors of $n$ is $\tau(n)$. ∎

Title proof that $\tau(n)$ is the number of positive divisors of $n$ ProofThattaunIsTheNumberOfPositiveDivisorsOfN 2013-03-22 13:30:24 2013-03-22 13:30:24 Wkbj79 (1863) Wkbj79 (1863) 11 Wkbj79 (1863) Proof msc 11A25