Question

p- простое число меньшее 2018. Сумма всех возможных различных остатков от деления положительных целых степеней двойки на p равняется p. Найдите количество возможных различных значений p.

Answer 1

Пусть $p=2^k-a, k\in N, a\in N, a$

Тогда $p>2^k-2^{k-1}=2^{k-1}$. Значит остаток от деления $2^n$ на $p$ равен $2^n\; \forall n \leq k-1, n\in N$. Тогда сумма всевозможных остатков будет не меньше $1 +...+2^{k-1}=\dfrac{1(2^{k-1-0+1}-1)}{2-1}=2^k-1$

Значит для выполнения условий задачи необходимо $2^k-a\geq 2^k-1=>a\leq 1\\ a\in N=>a=1$

$p=2^k-1$

Теперь рассмотрим, что будет происходить с остатками следующих степеней двойки.

$n=k:\:2^k=2^k-1+1=p+1=>$ остаток равен 1 - а значит новых остатков не получим. А значит все простые числа вида $2^k-1$ (числа Мерсена) удовлетворяют условию задачи.

Число Мерсена является простым, только если $k$ также простое.

$2048>2018>1024=2^{10}$

Тогда остается рассмотреть числа $2^2-1=3,\:2^3-1=7,\:2^5-1=31,\:2^7-1=127$ - все простые

Ответ: 4 числа.

Answer 2

Давайте рассмотрим эту задачу более подробно.

Мы ищем простые числа, меньшие 2018, для которых сумма всех возможных различных остатков от деления положительных целых степеней двойки на p равняется p. Представим это уравнение в виде:

$1 + 2 + 2^2 + \ldots + 2^n \equiv p \pmod{p}$

Теперь мы знаем, что $1 + 2 + 2^2 + \ldots + 2^n = 2^{n+1} - 1$.

Таким образом, наше уравнение становится:

$2^{n+1} - 1 \equiv p \pmod{p}$

Из малой теоремы Ферма мы знаем, что если p - простое число и a - целое число, не делящееся на p, то:

$a^{p-1} \equiv 1 \pmod{p}$

Таким образом, $2^{p-1} \equiv 1 \pmod{p}$.

Из этого следует, что:

$2^{(p-1)k} - 1 \equiv 0 \pmod{p}$

где k - целое число.

Теперь мы видим, что если n+1 кратно (p-1), то наше уравнение выполняется. Это означает, что $n+1 = m(p-1)$, где m - некоторое целое число. Таким образом, $n = m(p-1) - 1$.

Мы также знаем, что $n+1 \leq 2018$, поскольку p меньше 2018. Таким образом, $m(p-1) - 1 \leq 2018$.

Теперь мы можем начать проверять различные значения p. Начнем с самых маленьких простых чисел и будем увеличивать их, пока не найдем все возможные значения p, для которых выполняется условие.

Начнем с p = 2: $m(2-1) - 1 \leq 2018$ => $m - 1 \leq 2018$ => $m \leq 2019$

Таким образом, для p = 2 существует много значений m, удовлетворяющих условию.

Далее, попробуем p = 3: $m(3-1) - 1 \leq 2018$ => $2m - 1 \leq 2018$ => $2m \leq 2019$ => $m \leq 1009.5$

Для p = 3 существует меньше возможных значений m.

Продолжаем этот процесс для всех простых чисел, меньших 2018, и считаем количество значений m, удовлетворяющих каждому уравнению. Наконец, сложим все найденные значения m и получим искомый ответ.

Таким образом, количество возможных различных значений p равно сумме всех значений m, удовлетворяющих уравнению для каждого p.