I've run out of problem titles!

Find the smallest positive integer n n such that ϕ ( n ) = 120 \phi(n)=120 .

Notation : ϕ ( ) \phi(\cdot) denotes the Euler's totient function .


The answer is 143.

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.

1 solution

Manuel Kahayon
Mar 20, 2016

Obviously, since 120 120 and n n are both integers, they can be factored in the form a b c a \cdot b \cdot c \ldots for factors a , b , c , a, b, c, \ldots .

Now, since ϕ ( p k ) = p k 1 ( p 1 ) \phi(p^k) = p^{k-1} \cdot (p-1) for primes p p , we should factor 120 into the form ( p a k a 1 ( p a 1 ) ) ( p b k b 1 ( p b 1 ) (p_a^{k_a-1} \cdot (p_a-1)) \cdot (p_b^{k_b-1} \cdot (p_b-1) \ldots for some primes p a , p b p_a, p_b \ldots . Then, we get n = p a k a p b k b n = p_a^{k_a} \cdot p_b^{k_b} \ldots .

Now, since n n is to be minimized, we can get the minimum value of n n if there is only one prime factor of n n , and k = 1 k=1 , since this gives us n = p n = p for some prime p, and p 1 = 120 p-1 = 120 . But, this implies that p = 121 , p=121, , and since 121 121 is not prime, we reject this solution.

Our next smallest value of n n can be acquired f there is only one prime factor of n n , and k = 2 k=2 , since this implies that n = p 2 n = p^2 for some prime p, and ( p ) ( p 1 ) = 120 (p)(p-1) = 120 . But, since 120 cannot be factored into two consecutive integers, this idea is to be tossed into the trash bin.

Our next smallest value of n n can be acquired when there are two prime factors of n n , namely p a , p b p_a, p_b and k a = k b = 1 k_a = k_b = 1 , since this implies that n = p a p b n = p_a \cdot p_b and ( p a 1 ) ( p b 1 ) = 120 (p_a-1) \cdot (p_b-1) = 120 . Also, p a p b |p_a-p_b| must be minimized in order to minimize n n . By factoring out 120 120 , we get that 120 = 12 10 = ( 13 1 ) ( 11 1 ) 120 = 12 \cdot 10 = (13-1)(11-1) . This implies that n = 13 11 = 143 n = 13 \cdot 11 = \boxed {143} , which is our final answer.

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...