Competition problem — Number theory

Library / /155 of 348

Number theory Difficulty 4.9 AIME Find the answer

An integer $n$ is chosen uniformly at random from the set $\{1,2,3, \ldots, 2023!\}$ . Compute the probability that $\operatorname{gcd}\left(n^{n}+50, n+1\right)=1$

Your answer

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

Solution

If $n$ is even, we need $\operatorname{gcd}(n+1,51)=1$ . If $n$ is odd, we need $\operatorname{gcd}(n+1,49)=1$ . Thus, the answer is $\frac{1}{2}\left(\frac{\varphi(49)}{49}+\frac{\varphi(51)}{51}\right)=\frac{265}{357}$

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.