11. $[7]$ Define $\phi^{\prime}(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^{!}(n)
$$
is divided by 50 .
Answer:
12
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 .