Competition problem — Number theory

Library / /269 of 860

Number theory Difficulty 5.0 AIME, harder Find the answer

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^{!}(n)$ is divided by 50 .

Your answer

A number or a short expression. Spacing and $ signs are ignored.

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 .

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.