Suppose we have the number $36$, which can be broken down into ($2^{2}$)($3^{2}$). I understand that adding one to each exponent and then multiplying the results, i.e. $(2+1)(2+1) = 9$, yields how many divisors the number $36$ has. I can make sense of a number which can be expressed as the product of two powers of the same prime, i.e. $343$, because $7^{3}$ allows us to see that: $7$ is a divisor, $7^{2}$ is a divisor, and the always present $1$ and $343$ are divisors, leaving us with a total number of $4$ divisors for $343$. What is the best way to gain intuition behind using this method for a number like $36$?
Elementary Number Theory – Why Multiplying Prime Factors Yields Total Divisors
divisor-counting-functionelementary-number-theoryprime numbers
Related Solutions
This may give you more of the theory or logic that you want behind this (I give an explanation of your example specifically at the end), although Marco does provide a nice, intuitive combinatorial analysis.
As someone pointed out, $\sigma$ is the sum of divisors function, which is defined by setting $\sigma(n)$ equal to the sum of all the positive divisors of $n$.
Now, we have that $\tau$ is the number of divisors function, which is defined by setting $\tau(n)$ equal to the number of positive divisors of $n$.
First note that $\sigma(n)$ and $\tau(n)$ may be expressed in summation notation: $$ \sigma(n)=\sum_{d\mid n}d\quad\text{and}\quad \tau(n)=\sum_{d\mid n}1. $$ I am going to assume that you know $\sigma(n)$ and $\tau(n)$ are multiplicative functions (if not, proofs of this fact are easy to find); that is, $$ \sigma(mn)=\sigma(m)\sigma(n)\quad\text{and}\quad\tau(mn)=\tau(m)\tau(n),\tag{1} $$ where $m$ and $n$ are relatively prime positive integers (such functions are called completely multiplicative if $(1)$ holds for all positive integers $m$ and $n$).
With that out of the way, we can develop what you learned more rigorously by starting out with a lemma, then a theorem, and then a simple example.
Lemma: Let $p$ be prime and $a$ a positive integer. Then $$ \sigma(p^a)=1+p+p^2+\cdots+p^a=\frac{p^{a+1}-1}{p-1},\tag{2} $$ and $$ \tau(p^a)=a+1.\tag{3} $$ Proof. The divisors of $p^a$ are $1,p,p^2,\ldots,p^{a-1},p^a$. Hence, $p^a$ has exactly $a+1$ divisors, so that $\tau(p^a)=a+1$. Also, we note that $\sigma(p^a)=1+p+p^2+\cdots+p^{a-1}+p^{a}=\frac{p^{a+1}-1}{p-1}$ (the sum of terms in a geometric progression).
Theorem: Let the positive integer $n$ have prime factorization $n=p_1^{a_1}p_2^{a_2}\cdots p_s^{a_s}$. Then we have that $$ \sigma(n)=\frac{p_1^{a_1+1}-1}{p_1-1}\cdot\frac{p_2^{a_2+1}-1}{p_2-1}\cdot\cdots\cdot\frac{p_s^{a_s+1}-1}{p_s-1}=\prod_{j=1}^s\frac{p_j^{a_j+1}-1}{p_j-1},\tag{4} $$ and $$ \tau(n)=(a_1+1)(a_2+1)\cdots(a_s+1)=\prod_{j=1}^s(a_j+1).\tag{5} $$ Proof. Since $\sigma$ and $\tau$ are both multiplicative, we can see that $$ \sigma(n)=\sigma(p_1^{a_1}p_2^{a_2}\cdots p_s^{a_s})=\sigma(p_1^{a_1})\sigma(p_2^{a_2})\cdots\sigma(p_s^{a_s}), $$ and $$ \tau(n)=\tau(p_1^{a_1}p_2^{a_2}\cdots p_s^{a_s})=\tau(p_1^{a_1})\tau(p_2^{a_2})\cdots\tau(p_s^{a_s}). $$ Inserting the values for $\sigma(p_i^{a_i})$ and $\tau(p_i^{a_i})$ found in $(2)$ and $(3)$, we obtain the desired formulas.
Example: Calculate $\sigma(200)$ and $\tau(200)$.
Solution. Using $(4)$ and $(5)$, we have that $$ \sigma(200)=\sigma(2^35^2)=\frac{2^4-1}{2-1}\cdot\frac{5^3-1}{5-1}=15\cdot 31=465, $$ and $$ \tau(200)=\tau(2^35^2)=(3+1)(2+1)=12. $$
For your observation specifically, calculating $\sigma(12)$ and $\tau(12)$ yields the following:
- $\displaystyle \sigma(12)=\sigma(2^23^1)=\frac{2^3-1}{2-1}\cdot\frac{3^2-1}{3-1}=7\cdot 4=28$.
- $\tau(12)=\tau(2^23^1)=(2+1)(1+1)=3\cdot 2 = 6$.
The most brute force procedure that is not inefficient for completely naive reasons is trial division up to $\lfloor \sqrt{n} \rfloor$, because if $n$ has a factor greater than or equal to $\sqrt{n}$ then it must also have a factor less than or equal to $\sqrt{n}$. (For example, $\lfloor \sqrt{91} \rfloor = 9$. Although $91$ has a factor of $13$ which is larger than $9$, it also has a factor of $7$, and dividing by this factor reveals the factor of $13$.)
The difficulty is that if $n$ has 100 digits then $\sqrt{n}$ is like $10^{50}$, so if you try a trillion numbers per second then it will take you more than $10^{30}$ years to finish trying all the factors less than $\sqrt{n}$.
There are much better algorithms out there, though, especially for the problem of primality testing (as opposed to factorization of a number which is known to be composite).
Best Answer
If $d$ divides $36$, then no prime numbers other than $2$ and $3$ can divide $d$. On the other hand, $36=2^23^2$ and so $d=2^\alpha3^\beta$, with $\alpha,\beta\in\{0,1,2\}$. Since there are three possibilities for $\alpha$ and another $3$ for $\beta$, there are $9(=3\times3)$ possibilities for $d$.