https://artofproblemsolving.com/wiki/index.php/2022_AIME_I_P...
The totient formula isn't the hard part of the problem.
The test has a very short time limit (for the difficulty of the problems), and has many gruelingly complicated problems,so if you dont have the formulas down cold, you'll burn out during the contest.
Of course, if you don't care about silly speed-mathing contests, you can enjot the problems at a leisurely pace.
* The contest has 15 problems and a time limit of 3 hours, giving only an average of 12 minutes per problem.
* The average score is 4.83/15, from the official statistics [1].
* The statistics noted that only 5.17% of test takers answered this problem correctly, making it the second-hardest problem out of the 15 on the exam.
[1] "AIME 02/08/2022" https://amc-reg.maa.org/reports/generalreports.aspx
OP missing this point shows that he really was doing this for all the wrong reasons. He should have done FIRST or science bowl instead.
Asking for N mod 1000 was another cute twist that was meant to get you thinking about the divisibility properties of the totient function - "hmm, so (p-1) always divides \phi(n) for all prime factors p of n, how convenient..."