proof that is the number of positive divisors of
The following is a proof that counts the positive divisors of its input (which must be a positive integer).
Proof.
Recall that behaves according to the following two rules:
- 1.
If is a prime and is a nonnegative integer, then .
- 2.
If , then .
Let be a prime. Then . Note that 1 is the only positive divisor of 1 and .
Suppose that, for all positive integers smaller than with , the number of positive divisors of is . Since , there exists a prime divisor of . Let be a positive integer such that exactly divides . Let be a positive integer such that . Then . Thus, . Since , by the induction hypothesis, there are positive divisors of .
Let be a positive divisor of . Let be a nonnegative integer such that exactly divides . Thus, , and there are choices for . Let be a positive integer such that . Then . Since divides and divides , we conclude that divides . Since divides and , it must be the case that divides . Thus, there are choices for . Since there are choices for and there are choices for , there are choices for . Hence, there are positive divisors of . Since , it follows that, for every positive integer , the number of positive divisors of is .∎