## You are here

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

## Primary tabs

# 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. If $p$ is a prime and $k$ is a nonnegative integer, then $\tau(p^{k})=k+1$.

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<z$, 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)$. ∎

## Mathematics Subject Classification

11A25*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections