Let be a natural number (positive integer) and be the number of distinct prime divisors of . For example, if , then . In how many ways can be expressed as a product of two relatively prime natural numbers?
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
Let n = Π i = 1 m p i r i , where the p i are distinct primes and r i ∈ N .
Suppose n = a × b , where a and b are coprime. Each prime factor p i may appear in only one of a or b (otherwise they would have a common factor greater than 1). In fact, each element p i r i must appear in exactly one of a or b .
Therefore, for i = 1 , 2 , 3 , … m , decide whether the element p i r i should be a factor of a or b . There are 2 m possibilities for this. Since for every pair ( a , b ) we have also counted the pair ( b , a ) , each pair has been counted twice, so our result needs to be halved: 2 m − 1 .