Question

Если 1 плюс куб натурального числа p делится на 13, найти количество
возможных значений p ≤ 2021

Answer 1

$(1+p^3)\ \vdots\ 13,\ p\in\mathbb{N}$

Разложим на множители:

$1+p^3=(1+p)(1-p+p^2)$

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

1. Предположим, что выражение в первых скобках делится на 13:

$\underset{\vdots\ 13}{\underbrace{(1+p)}}(1-p+p^2)$

В этом случае необходимо, чтобы число $p$ при делении на 13 давало остаток 12. Тогда, при добавлении к таком числу 1, результат будет делиться на 13 без остатка. Записать это можно, к примеру, так:

$1+p\equiv0\pmod{13}$

$p\equiv-1\equiv12\pmod{13}$

$p_1=12+13k,\ k\in\mathbb{Z}$

Проверим, может ли при таких значениях $p$ вторая скобка делиться на 13:

$1-p+p^2\equiv1-(-1)+(-1)^2=1+1+1=3\pmod{13}$

Как видно, вторая скобка не может одновременно с первой делиться на 13.

2. Предположим, что выражение во вторых скобках делится на 13:

$(1+p)\underset{\vdots\ 13}{\underbrace{(1-p+p^2)}}$

Тогда:

$1-p+p^2\equiv0\pmod{13}$

$p^2-p\equiv-1\equiv12\pmod{13}$

Проверим возможные решения - от 0 до 12 по модулю 13, или для упрощения расчетов от -6 до 6 по модулю 13:

$(-6)^2-(-6)=42\equiv3\not\equiv12\pmod{13};\ (-5)^2-(-5)=30\equiv4\not\equiv12\pmod{13};$

$(-4)^2-(-4)=20\equiv7\not\equiv12\pmod{13};\ (-3)^2-(-3)=12\equiv12\pmod{13};$

$(-2)^2-(-2)=6\not\equiv12\pmod{13};\ (-1)^2-(-1)=2\not\equiv12\pmod{13};$

$0^2-0=0\not\equiv12\pmod{13};\ 1^2-1=0\not\equiv12\pmod{13};$

$2^2-2=2\not\equiv12\pmod{13};\ 3^2-3=6\not\equiv12\pmod{13};$

$4^2-4=12\equiv12\pmod{13};\ 5^2-5=20\equiv7\not\equiv12\pmod{13};$

$6^2-6=30\equiv4\not\equiv12\pmod{13}$

Решения, удовлетворяющие соотношению:

$p\equiv-3\equiv10\pmod{13}\Rightarrow p_2=10+13k,\ k\in\mathbb{Z}$

$p\equiv4\pmod{13}\Rightarrow p_3=4+13k,\ k\in\mathbb{Z}$

3. Таким образом, нужно определить сколько чисел из первых 2021 натурального числа при делении на 13 дают остаток 12, 10 или 4.

Определить это достаточно просто, для этого разделим число 2021 на 13 с остатком и результат запишем в виде:

$2021=155\cdot13+6$

Разобьем 2021 число на группы:

$\{1;\ 2;\ 3;\ \ldots;\ 1\cdot13\}$

$\{1\cdot13+1;\ \ldots;\ 2\cdot13\}$

$\{2\cdot13+1;\ \ldots;\ 3\cdot13\}$

...

$\{154\cdot13+1;\ \ldots;\ 155\cdot13\}$

$\{155\cdot13+1;\ \ldots; 155\cdot13+6\}$

Во всех группах, кроме последней, содержится 13 чисел, в совокупности дающие различные остатки при делении на 13. Значит, в каждой такой группе ровно 3 числа, удовлетворяющих условию. Всего таких групп 155.

В последней группе содержится одно число, удовлетворяющее условию: $155\cdot13+4$.

Таким образом, общее количество чисел:

$155\cdot3+1=466$

Ответ: 466