HMMT-Feb 2016 guts, Problem 11

Define $\phi^{!}(n)$ as the product of all positive integers less than or equal to $n$ and relatively prime to $n$. Compute the remainder when \[ \sum_{\substack{2 \leq n \leq 50 \\ \operatorname{gcd}(n, 50)=1}} \phi^{\prime}(n) \] is divided by 50 .

Solution: First, $\phi^{!}(n)$ is even for all odd $n$, so it vanishes modulo 2 . To compute the remainder modulo 25 , we first evaluate $\phi^{!}(3)+\phi^{!}(7)+\phi^{!}(9) \equiv 2+5 \cdot 4+5 \cdot 3 \equiv 12$ $(\bmod 25)$. Now, for $n \geq 11$ the contribution modulo 25 vanishes as long as $5 \nmid n$. We conclude the answer is 12 . $\fbox{12}$.

Answer: 12