start from the prime power factorisation:
The above product expression only includes primes above 1 to avoid double counting on the next step.
By definition any part of the above product is a divisor of n. The full set of divisors are formed by varying the powers of each prime factor (other than 1) between 0 and
, ie the divisors are:
The total number of divisors that can be constructed by varying those powers is
)
. The construction includes all possible divisors since the prime factorisation of n is unique. No divisor is constructed twice since the prime factorisation of each divisor is unique. So D is the correct total of unique divisors. NB: the total (D) counts both
n and
1 as divisors of n. If you dont consider those "real" divisors then you can subtract 1 or 2 from the total.
Getting the number of square divisors is a simple extension. Define
A number is square iff its prime factorsation has even powers, so the possible square divisors are
Anything constructed in this way is a divisor of n since
. Using the same arguments as before the total number of square divisors is
)
Now it's just a probability problem. We want P(square then non-square) + P(non-square then square).
 + \left(1-\frac{S}{D}\right) \cdot \frac{S}{D-1})
LinkBack URL
About LinkBacks
Originally Posted by Chris11
has no square factors...
has exactly one square factor...
has more than one square factor...
