Specific coprime set

Let S S denote the set for all positive integers M M such that there exists a positive integer N N for which exactly 1 N \frac1N of the positive integers less than or equal to M M are coprime to M M itself.

For example, 4 is in the set S S because exactly 1 2 \frac12 of the positive integers in { 1 , 2 , 3 , 4 } \{1,2,3,4\} are coprime to 4 itself.

Find 100 s S 1 s \displaystyle 100 \sum_{s \in S} \dfrac1s .


The answer is 250.

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

Patrick Corn
Feb 12, 2018

Let M = p 1 a 1 p 2 a 2 p n a n M = p_1^{a_1} p_2^{a_2} \cdots p_n^{a_n} where the p i p_i are distinct primes and the a i a_i are positive integers. Suppose 1 / N 1/N of the positive integers M \le M are coprime to M . M. If N = 1 N=1 then M = 1. M=1. Now assume M 2 , M \ge 2, so N 2. N \ge 2.

Then the fraction of integers less than or equal to M M which are coprime to M M is ( p 1 1 ) ( p 2 1 ) ( p n 1 ) p 1 p 2 p n . \frac{(p_1-1)(p_2-1)\cdots(p_n-1)}{p_1p_2\cdots p_n}. If this is the reciprocal of N , N, the power of 2 2 in the numerator has to be less than or equal to the power of 2 2 in the denominator. If all the p i p_i are odd, this is impossible (unless M = 1 M=1 ). So without loss of generality p 1 = 2 p_1=2 and the denominator contains exactly one 2. 2. In this case, the numerator contains at most one even number, hence there is at most one other prime p 2 . p_2.

So we get p 2 1 2 p 2 = 1 N , \frac{p_2-1}{2p_2} = \frac1{N}, whence p 2 = N N 2 = 1 + 2 N 2 , p_2 = \frac{N}{N-2} = 1 + \frac2{N-2}, which is only an integer if ( N 2 ) 2. (N-2)|2. If N = 3 N=3 we get p 2 = 3 p_2=3 and if N = 4 N=4 we get p 2 = 2 , p_2=2, which is impossible. So p 2 = 3 p_2=3 is the only possibility.

Hence S = { 1 } { 2 a 3 b : a 1 , b 0 } . S = \{1\} \cup \{2^a 3^b : a \ge 1, b \ge 0\}.

Then 100 s S 1 s = 100 + 100 a = 1 b = 0 1 2 a 3 b = 100 + 100 a = 1 1 2 a b = 0 1 3 b = 100 + 100 1 3 / 2 = 250 . 100\sum\limits_{s \in S} \frac1{s} = 100 + 100\sum\limits_{a=1}^\infty \sum\limits_{b=0}^\infty \frac1{2^a3^b} = 100 + 100 \sum_{a=1}^\infty \frac1{2^a} \sum_{b=0}^\infty \frac1{3^b} = 100 + 100 \cdot 1 \cdot 3/2 = \fbox{250}.

Alapan Das
Apr 1, 2019

For a positive integer M we get the number of coprime or Euler function Fi(n)= M(1-1/p 1)(1-1/p 2)...... Now, 1/{(1-1/p 1)(1-1/p 2)....} would be a natural number only when p 1 and p 2 are 2 and 3. So s can be of the form (2^a)(3^b). a≥1,b≥0. An 1 is also a value of s. Then the summation becomes 2.5. So, the answer comes 250.

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...