I didn't know that till now

Let n n be a natural number (positive integer) and m m be the number of distinct prime divisors of n n . For example, if n = 12 = 2 2 3 n = 12 = 2^2 \cdot 3 , then m = 2 m = 2 . In how many ways can n n be expressed as a product of two relatively prime natural numbers?

m m m 1 m-1 2 m 1 2^{m-1} 2 m 2^{m}

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.

2 solutions

Joel Toms
Jan 5, 2016

Let n = Π i = 1 m p i r i n=\Pi_{i=1}^m{p_i}^{r_i} , where the p i p_i are distinct primes and r i N r_i\in\mathbb{N} .

Suppose n = a × b n=a\times b , where a a and b b are coprime. Each prime factor p i p_i may appear in only one of a a or b b (otherwise they would have a common factor greater than 1). In fact, each element p i r i {p_i}^{r_i} must appear in exactly one of a a or b b .

Therefore, for i = 1 , 2 , 3 , m i=1,2,3,\dots m , decide whether the element p i r i {p_i}^{r_i} should be a factor of a a or b b . There are 2 m 2^m possibilities for this. Since for every pair ( a , b ) (a,b) we have also counted the pair ( b , a ) (b,a) , each pair has been counted twice, so our result needs to be halved: 2 m 1 2^{m-1} .

Davin Shaun
Jan 4, 2016

Slightly cheating but, for twelve, the only way to express in coprime positive integers is 1x12 or 3x4. This means since m = 2, the answer is either m or 2^m-1. Taking 60 as an example, if the answer was m, you would predict there to be 3 ways (m = 3, {2^2, 3, 5}) to express in coprime integers, whereas if answer is 2^m-1, you expect there to be 2^2 = 4 ways to express. As it turns out, 60 can be expressed as 1x60, 3x20, 4x15, or 5x12. Therefore, answer is 2^m-1.

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...