Competition problem — Number theory

Library / /1 of 1394

Number theory Difficulty 4.5 AIME Find the answer United States

Problem:
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. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

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: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.