What a time to be alive
Find the smallest positive integer n such that ϕ ( n ) = 2 0 1 6 .
Notation : ϕ ( ⋅ ) denotes the Euler's totient function .
The answer is 2017.
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
I used the same method. This question would have been considerably hard if it was something like ϕ ( n ) = 2 0 1 7 .
Log in to reply
Yay, the value must not be 1 less than a prime number for it to be comparatively hard.
Uhh, doesn't that have no solutions for n?
Log in to reply
Probably. I haven't studied Euler's Totient function in detail yet but what I meant to say is that finding ϕ ( n ) when n + 1 is not prime is harder to find.
Log in to reply
@Arulx Z – Ohh, okayy, then have you seen this problem?
How to find out if 2017 is a prime number..
Log in to reply
There are better method but trial division is quite simple. 2 0 1 7 ≈ 4 4 . Now try diving 2017 by every prime number less than 44. If anything divides it, then 2017 is composite. Otherwise, it's prime.
Log in to reply
I have read that if we continue dividing by prime numbers, when quotient starts exceeding the divisor it must be understood that it is a prime number.is it also right?
Log in to reply
@Puneet Pinku – Yes, that is because for any positive integral n and a , if a n ≤ a then a ≥ n
Log in to reply
@Manuel Kahayon – Thanks a lot. It is a good way to determine prime numbers manually...
Since there are exactly 2016 integers less than n which are coprime to n , n ≥ 2 0 1 7 by logic. Also, we know that primes share no common factor with any integer less than it, and since 2017 is prime, our answer is 2 0 1 7
Same method. The logic is preferably nice . :)
ϕ ( 2 0 1 7 ) = 2 0 1 7 ( 1 − 2 0 1 7 1 ) = 2 0 1 6 . From the definition of Euler's totient function for prime numbers I.e. ϕ ( p k ) = p k ( 1 − p 1 ) as 2017 is prime.