Среди чисел $1, 2, \ldots, p^k$ не взаимно просты с $p^k$ ровно те, которые делятся на $p$: их $p^{k-1}$ штук (это числа $p, 2p, \ldots, p^{k-1} \cdot p = p^k$). Остальные $p^k - p^{k-1}$ числа взаимно просты с $p^k$. По определению $\varphi(p^k) = p^k - p^{k-1} = p^{k-1}(p - 1)$.

💡 Авторизуйтесь, чтобы получить помощь AI-тьютора с подсказками и решениями!