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$

Answer 2

Чтобы найти количество натуральных чисел n на интервале (2017, 2017^2), для которых 2017 делит n^n - 1, мы можем использовать теорему Ферма о малой теореме. Теорема Ферма гласит, что если p - простое число, а a - натуральное число, не кратное p, то a^(p-1) при делении на p дает остаток 1. Математически это можно записать как: a^(p-1) ≡ 1 (mod p) В нашем случае p = 2017 (которое также является простым числом). Мы ищем n, для которого 2017 делит n^n - 1. Это означает, что: n^n ≡ 1 (mod 2017) Теперь, чтобы применить теорему Ферма, нам нужно найти наименьшее натуральное число k такое, что n^k ≡ 1 (mod 2017). Затем мы должны убедиться, что k является делителем числа 2017 - 1, то есть k должно делить 2016. Поскольку 2017 - 1 = 2016, и 2016 разлагается на простые множители как 2^6 * 3^2 * 7, k должно быть делителем 2^6 * 3^2 * 7, иначе теорема Ферма не будет выполняться. Теперь посчитаем количество натуральных чисел n в интервале (2017, 2017^2), для которых 2017 делит n^n - 1. Мы должны найти количество делителей числа 2016 (потому что k является делителем 2016). Чтобы найти количество делителей, мы используем разложение на простые множители числа 2016: 2016 = 2^6 * 3^2 * 7. Число делителей числа, представленное в виде произведения простых степеней, вычисляется как (6 + 1) * (2 + 1) * (1 + 1) = 7 * 3 * 2 = 42. Таким образом, в интервале (2017, 2017^2) существует 42 натуральных чисел n, для которых 2017 делит n^n - 1.