Question

Сколько натуральных чисел n в интервале (2017, 2017^2) таких, что 2017 делит n^n-1?

Answer 1

Олимпиадная муторная задача...

Сначала заметим, что $2017$ является простым. Более того, условие эквивалентно условию $n^n \equiv 1 \mod 2017$. Кроме того, $n^{2016} \equiv 1 \mod 2017$ для всех $n \not\equiv 0 \mod 2017$. Тогда, где $n \equiv a \mod 2017$, $n \equiv b \mod 2016$, мы имеем

$n^n \equiv a^b \mod 2017$

Отсюда, учитывая, что существует биекция от чисел в интервале $(2017, 2017^2)$ к $(a,b), \; 0\le a < 2017, \; 0\le b < 2016$, это означает, что мы просто рассматриваем все $(g^a,b)$, где $0 < a < 2016, \; 0\le b < 2016$, где $g$ - первообразный корень. (Нам не важно, что $n \equiv 0 \mod 2017$). Тогда

1$\equiv n^n \equiv (g^a)^b \equiv g^{ab} \mod 2017\Rightarrow ab \equiv 0 \mod 2016$

Для некоторого $a$ допустим, что $\gcd(a,2016) = d$. Тогда все кратные $x = \frac{2016}{d}$ действительны как $b$, а таких кратных $d$. Следовательно, достаточно вычислить

$\sum\limits_{i=1}^{2016}{\gcd(2016, i)} = \sum\limits_{d|2016}{d \; \cdot \text{(\# i | gcd(i, 2016) is d)}} = \sum\limits_{d|2016}{d \; \cdot \; \phi\left( \frac{2016}{d} \right) }$

Но учитывая, что $2016 = 2^5 3^2 7^1$, получаем

$2016 \cdot \left( 5 \cdot \frac{1}{2} + 1 \right) \cdot \left( 2 \cdot \frac{2}{3} + 1 \right) \cdot \left( 1 \cdot \frac{6}{7} + 1 \right) = 30576$