There are indeed eight factors of \( 24: 1, 2, 4, 8, 3, 6, 12, 24 \) so this is a quick and easy way to calculate the number of factors based on prime factors of a number and the degrees to which each of them are raised. It's similar to the formula for calculating the number of ways in which a number can be written as the sum of two squares viz.:
The fundamental theorem on sums of two squares is:
Let \(n=2^kp_1^{a_1} \dots p_r^{a_r}q_1^{b_1} \dots q_s^{b_s}\) , where the \( p_i \) are distinct primes with \( p_i \equiv 1 \pmod{4} \) and the \( q_i \) are distinct primes with \( q_j \equiv 3 \pmod{4} \). Then \(n \) is the sum of two squares if and only if all the \( b_j \) are even. In that case, the number of distinct solutions is $$ \lceil \frac{\scriptstyle{1}}{\scriptstyle{2}} (a_1+1)(a_2+1) \dots (a_r+1) \rceil $$ where \( \lceil x \rceil \) is the ceiling function, the smallest integer greater than or equal to \( x \).
Of course by this rule, \(24\) cannot be written as a sum of two squares because it has a \(4k+3\) factor (\(3\)), raised to an odd power (\(1\)). However, \(25=5^2 \) has no \(4k+3 \) factors and its \(4k+1\) factor (\(5\)) is raised to the \(2nd\) power. This means that it can be written as the sum of two squares in two distinct ways because \( \lceil \frac{1}{2}(2+1) \rceil =2 \). The two ways are \( 5^2+0^2 \) and \(4^2+3^2 \).
Getting back to the number of divisors however, the formula quoted is actually part of a more general formula (as explained in Wikipedia):
The divisor function is multiplicative, but not completely multiplicative. The consequence of this is that, if we write $$n = \prod_{i=1}^r p_i^{a_i}$$ where \( r=\omega (n) \) is the number of distinct prime factors of \(n \), \(p_i \) is the \(i\)th prime factor, and \(a_i \) is the maximum power of \(p_i \) by which \(n\) is divisible, then we have $$\sigma_x(n) = \prod_{i=1}^{r} \frac{p_{i}^{(a_{i}+1)x}-1}{p_{i}^x-1}$$ which is equivalent to the useful formula:$$ \sigma_x(n) = \prod_{i=1}^r \sum_{j=0}^{a_i} p_i^{j x} =
\prod_{i=1}^r (1 + p_i^x + p_i^{2x} + \cdots + p_i^{a_i x}).$$ It follows (by setting \(x = 0 \)) that \(d(n) \) is: $$\sigma_0(n)=\prod_{i=1}^r (a_i+1).$$
Of course by this rule, \(24\) cannot be written as a sum of two squares because it has a \(4k+3\) factor (\(3\)), raised to an odd power (\(1\)). However, \(25=5^2 \) has no \(4k+3 \) factors and its \(4k+1\) factor (\(5\)) is raised to the \(2nd\) power. This means that it can be written as the sum of two squares in two distinct ways because \( \lceil \frac{1}{2}(2+1) \rceil =2 \). The two ways are \( 5^2+0^2 \) and \(4^2+3^2 \).
Getting back to the number of divisors however, the formula quoted is actually part of a more general formula (as explained in Wikipedia):
The divisor function is multiplicative, but not completely multiplicative. The consequence of this is that, if we write $$n = \prod_{i=1}^r p_i^{a_i}$$ where \( r=\omega (n) \) is the number of distinct prime factors of \(n \), \(p_i \) is the \(i\)th prime factor, and \(a_i \) is the maximum power of \(p_i \) by which \(n\) is divisible, then we have $$\sigma_x(n) = \prod_{i=1}^{r} \frac{p_{i}^{(a_{i}+1)x}-1}{p_{i}^x-1}$$ which is equivalent to the useful formula:$$ \sigma_x(n) = \prod_{i=1}^r \sum_{j=0}^{a_i} p_i^{j x} =
\prod_{i=1}^r (1 + p_i^x + p_i^{2x} + \cdots + p_i^{a_i x}).$$ It follows (by setting \(x = 0 \)) that \(d(n) \) is: $$\sigma_0(n)=\prod_{i=1}^r (a_i+1).$$
No comments:
Post a Comment