Confusion regarding a property of Euler's Totient Function

Revision en4, by Aritra741, 2020-09-04 15:16:52

I was trying to solve this problem. When I failed to come up with a memory efficient solution, I looked at some AC solutions.

Interestingly, the solutions used a property that states that the minimum number that has a phi value greater than or equal to a given number, must be the first prime number greater than the given number. For example, For 20, the answer is 23. I am looking for a proof of this property.

Edit: According to tfg's comment, the answer isn't necessarily a prime number always. But this "property" holds for the given range of numbers due to prime gap.

Tags euler-totient, eular phi

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en6 English Aritra741 2020-09-05 10:12:39 14 Tiny change: 'htOJ-1370) prob' -> 'htOJ-1370)(LightOJ 1370) prob'
en5 English Aritra741 2020-09-04 16:17:45 182
en4 English Aritra741 2020-09-04 15:16:52 182
en3 English Aritra741 2020-09-04 14:26:23 7 Tiny change: 'ing for a formal proof of ' -> 'ing for a proof of '
en2 English Aritra741 2020-09-04 14:24:40 3 Tiny change: 'solutions. \nInteres' -> 'solutions.\n \nInteres'
en1 English Aritra741 2020-09-04 14:21:47 523 Initial revision (published)