Тема ТЕОРИЯ ЧИСЕЛ

Остатки и сравнения по модулю

Вспоминай формулы по каждой теме

Решай новые задачи каждый день

Вдумчиво разбирай решения

ШКОЛКОВО.
Готовиться с нами - ЛЕГКО!

Подтемы раздела теория чисел

Разделы подтемы Остатки и сравнения по модулю

Базовый аппарат сравнений по модулю

Выбор модуля для доказательства делимости / простоты / степени

Малая теорема Ферма

Функция Эйлера и теорема Эйлера из ТЧ

Китайская теорема об остатках

Обратные остатки

Квадратичные вычеты

Показатели и первообразные корни

Лемма об уточнении показателя

Решаем задачи

Ошибка.
Попробуйте повторить позже

Задача 21#127239Максимум баллов за задание: 7

Конфеты пытались раздать по $2,$ по $3,$ по $4$ и по $5$ конфет, но каждый раз оставалась одна лишняя конфета. Сколько конфет было всего, если известно, что их было точно больше одной, но меньше $100?$

Показать ответ и решение

Пусть $a$ — количество конфет. По условию задачи:

(| a =2c+ 1 |||{ a =3d+ 1 | |||( a =4e+ 1 a =5f + 1

То есть число $a − 1$ делится на 2, 3, 4 и 5. Так как числа 3, 4 и 5 не имеют общих делителей, можно сделать вывод, что число $a − 1$ делится на $3⋅4⋅5= 60,$ то есть число $a$ даёт остаток 1 при делении на 60. Среди чисел, больших 1, но меньших 100, есть всего одно число, удовлетворяющее данному условию — это число 61.

Ответ:

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

Ошибка.
Попробуйте повторить позже

Задача 22#127240Максимум баллов за задание: 7

Даша и Ксюша делят одно и то же натуральное число с остатком. Даша делит его на $8,$ а Ксюша на $9.$ Частное, которое получила Даша, и остаток, который получила Ксюша, в сумме дают $13.$ Какой остаток получился у Даши?

Показать ответ и решение

Запишем условие задачи в виде системы:

{ a =8x+ r, гдe 0≤ r< 8 a =9y+ (13− x), гдe 0 ≤13− x< 9

Приравняем правые части уравнений:

8x+ r= 9y+13− x

9(x− y) =13− r

Так как левая часть уравнения делится на 9, то $13− r$ также делится на 9, то есть 13 и $r$ дают одинаковые остатки при делении на 9. Так как $13 =1⋅9+ 4,$ то $r$ даёт остаток 4 при делении на 9. Учитывая ограничение $0≤ r<8,$ получаем $r= 4.$

Ответ:

Ошибка.
Попробуйте повторить позже

Задача 23#127569Максимум баллов за задание: 7

Докажите, что для каждого натурального $n$ число $11⋅14n+ 1$ — составное.

Показать доказательство

Заметим, что $14 ≡− 1 (mod 15),$ поэтому

n n 11⋅14 + 1≡ 11 ⋅(−1) + 1 (mod 15)

Если $n$ чётное, то $(−1)n = 1,$ и выражение сравнимо с $12 (mod 15),$ то есть делится на 3.

Если $n$ нечётное, то $(−1)n =− 1,$ и выражение сравнимо с $− 10 ≡5 (mod 15),$ то есть делится на 5.

Так как при любом $n$ значение $11⋅14n+ 1> 5,$ то делимость на 3 или 5 означает, что оно составное.

Ошибка.
Попробуйте повторить позже

Задача 24#128426Максимум баллов за задание: 7

Найдите все пары натуральных чисел $(a,b)$ такие, что $aa +bb$ делится на $ab⋅ba.$

Показать ответ и решение

Если $a =b,$ то $2aa$ делится на $aa⋅aa,$ то есть $2$ делится на $aa.$ Это возможно только при $a =1.$

Пусть теперь числа не равны, и не умаляя общности, $a> b.$ Тогда $a a$ делится на $b a ,$ значит, $b b$ должно делиться на $b a ,$ но $b b b < a.$ Противоречие.

Ответ:

$(1,1)$

Ошибка.
Попробуйте повторить позже

Задача 25#129304Максимум баллов за задание: 7

Около таверны стоят 100 эльфов, 100 гномов и 100 орков. Сначала в неё заходят 10 эльфов, 10 гномов и 10 орков. Затем каждую минуту из неё выходит одно существо и тут же заходит другое, причём всегда после выхода эльфа заходит гном, после выхода гнома — орк, а после выхода орка — эльф. Могло ли оказаться так, что в какой-то момент в таверне побывали все возможные компании из 30 существ ровно по одному разу? Все 300 существ различны.

Источники: ММО - 2025, 10.6 (см. mmo.mccme.ru)

Подсказки к задаче

Подсказка 1

Простым шагом будет вычислить количество всевозможных компаний из 30 существ. Не совсем ясно, зачем нам дан порядок выхода из таверны, как это можно перенести на математический язык?

Подсказка 2

Посмотрим на остаток разности количества эльфов и количества гномов при делении на 3, пусть это будет тип компании. Что можно сказать про компании относительно этой характеристики?

Подсказка 3

Докажем, что компаний с типом 1 и с типом 2 равное количество. А как компании чередуются относительно типа?

Подсказка 4

Вспомним, что мы знаем общее количество компаний из 30 существ, значит, нам известен и остаток при делении на 3. Попробуйте увидеть противоречие.

Показать ответ и решение

Первое решение.

Назовём типом компании остаток разности количества эльфов и количества гномов при делении на три. Заметим, что компаний типа 1 и 2 одинаковое количество, так как между ними можно построить взаимооднозначное соответствие: пронумеруем эльфов и гномов от 1 до 100 и поменяем одних на других с теми же номерами. Далее заметим, что компании меняются по циклу $0→ 1→ 2 → 0,...,$ причём, так как компаний типов 1 и 2 поровну, мы не можем закончить на 1, то есть количество всех компаний не может давать остаток 2 при делении на 3. Вычислим $30 C 300$ по модулю 3.

300⋅299⋅298⋅...⋅273⋅272 ⋅271 299⋅298⋅296⋅...⋅274⋅272⋅271 100⋅99⋅...⋅92⋅91 C33000 =----30⋅29⋅28-⋅...⋅3-⋅2-⋅1---- =----29⋅28⋅26-⋅...⋅4⋅2-⋅1---- ≡ -10⋅9⋅...⋅2⋅1--=

= 100⋅99⋅...⋅92⋅91= 100⋅98-⋅...⋅94⋅92⋅91⋅ 33⋅32⋅31≡ 10⋅9⋅...⋅2⋅1 10⋅8⋅...⋅4⋅2⋅1 3 ⋅2 ⋅1

≡ 10⋅8⋅...⋅4⋅2⋅1⋅ 33⋅32⋅31-= 11 ⋅16⋅31≡ 2 (mod 3) 10⋅8⋅...⋅4⋅2⋅1 3⋅2⋅1

Противоречие, значит, так оказаться не могло.

Замечание. Есть другой способ посчитать остаток $C30 300$ при делении на 3. Теорема Люка утверждает, что если $p$ — простое число, а числа $n$ и $k$ записываются в $p$ -ичной системе счисления как $n = ∑ nipi$ и $k= ∑ kipi,$ то $Ck≡ ∏ Ckni(mod p). n i$ Запишем 300 и 30 в троичной системе счисления: $300= (102010)3$ и $30= (1010)3.$ Таким образом,

30 1 0 1 0 1 0 C 300 ≡ C1C0C2C0C1C0 ≡2 (mod 3)

_________________________________________________________________________________________________________________________________________________________________________________

Второе решение.

Как и в прошлом решении разделим все компании на три типа. Если описанное в задаче возможно, то количества компаний разных типов отличается не более чем на 1, так как типы компаний меняются по циклу. Пронумеруем представителей всех рас от 1 до 100. Разобьем на тройки все компании, в которых множества номеров хотя бы каких-то двух рас различны, следующим образом. Возьмем некую компанию данного вида и рассмотрим максимальный номер, представленный хотя бы одной, но не всеми расами. Дважды прокрутим всех существ с этим номером, поменяв каждое существо на существо следующей расы с таким же номером. Легко видеть, что исходная и две полученные компании различных типов, причем с помощью данной операции они могут быть получены только друг из друга. При этом все компании не данного вида, коих всего $C10 , 100$ имеют тип 0, то есть компаний типа 0 ровно на $C10 100$ больше, чем других — противоречие.

Ответ:

Не могло

Ошибка.
Попробуйте повторить позже

Задача 26#129660Максимум баллов за задание: 7

Натуральное число $A$ при делении на $1981$ дало в остатке $35,$ при делении на $1982$ оно дало в остатке также $35.$ Каков остаток от деления числа $A$ на $14?$

Показать ответ и решение

Если число $A$ при делении на 1981 дало остаток 35, его можно записать в следующем виде:

A =1981a+35

Аналогично для деления на 1982:

A =1982b+35

Приравняем эти выражения:

1981a+ 35= 1982b+ 35

1981a= 1982b

Так как правая часть делится на 2, $a$ должно быть четным. Заметим, что 1981 кратно 7, следовательно, $1981a$ кратно 14. Посмотрим на остаток $A= 1981a +35$ при делении на 14:

( ) ( ) 1981a+ 35= 14 ⋅ 1981a- +14⋅2+ 7= 14⋅ 1981a-+2 +7 14 14

Следовательно, остаток от деления $A$ на 14 равен 7.

Ответ:

Курсы

Всё необходимое для достижения цели

Ошибка.
Попробуйте повторить позже

Задача 27#130350Максимум баллов за задание: 7

Докажите, что в любой “таблице умножения” вычетов по простому модулю $p$ в каждой строке все остатки различны.

Показать доказательство

Нам нужно показать, что при простом $p$ и $a ⁄≡ 0 (mod p)$ все вычеты $a,2a,...,pa$ будут различны. Предположим, что это не так и нашлись такие $x1 ⁄= x2,$ что

ax1 ≡ ax2 (mod p)

Перенесём всё в левую часть:

a(x1− x2) ≡0 (mod p)

Тогда или $a$ делится на $p,$ что не выполняется по условию, или $x1 − x2$ делится на $p,$ чего так же не может быть, поскольку $x1 ⁄= x2.$ Значит, все остатки в строчке таблицы умножения различны, что и требовалось доказать.

Ошибка.
Попробуйте повторить позже

Задача 28#130351Максимум баллов за задание: 7

Докажите, что $3003000 − 1$ делится на $1001.$

Показать доказательство

Поскольку $1001= 7⋅11⋅13,$ будем доказывать делимость на $p = 7, 1$ $p =11 2$ и $p = 13. 3$ Заметим, что 3000 делится на 6, 10 и 12, а 300 взаимно просто с 1001. Значит, для каждого из $pi$ по малой теореме Ферма

3000 300 ≡ 1 (mod pi)

Тогда $3003000− 1$ делится на 7, 11 и 13, а значит, и на их произведение, что и требовалось доказать.

Ошибка.
Попробуйте повторить позже

Задача 29#130352Максимум баллов за задание: 7

Докажите, что если $p> 5$ — простое, то число $11...1 ◟p◝−◜1 ◞$ делится на $p.$

Показать доказательство

Запишем число, состоящее из $p− 1$ единицы как $10p−1−1. 9$ Тогда из малой теоремы Ферма и условия $p >5$ получаем, что $10p−1− 1$ делится на $p.$ Поскольку $p >5,$ после деления на 9 делимость сохранится, что и требовалось доказать.

Ошибка.
Попробуйте повторить позже

Задача 30#130353Максимум баллов за задание: 7

Является ли простым число $1001200 +100?$

Показать ответ и решение

Заметим, что

НО Д(101,1001)= 1.

Рассмотрим выражение из условия по простому модулю 101. По малой теореме Ферма

2100 (1001 ) +100≡ 1+ 100 ≡0 (mod 101)

Тогда число делится на 101, при этом оно, очевидно, больше, чем 101. Значит, значение выражения является составным числом.

Ответ:

нет

Ошибка.
Попробуйте повторить позже

Задача 31#131798Максимум баллов за задание: 7

При каких натуральных $n$ число $20n+ 16n− 3n − 1$ делится на 323?

Показать ответ и решение

__________________________________________________________________________________________________

Лемма. Число $n n a − b$ кратно числу $a− b,$ где $a,b$ — натуральные, $n$ — неотрицательное целое.

Доказательство. По формуле сокращенного умножения

n n n−1 n−2 n−2 n−1 a − b =(a− b)(a + a b+ ...+ ab + b )

Значит, $an− bn$ кратно $a − b.$

______________________________________________________________________________________________________________________________________________________

Заметим, что $323= 17⋅19,$ при этом 17 и 19 взаимнопростые, откуда число делится на 323 тогда и тогда тогда, когда оно делится на 17 и на 19.

Для начала рассмотрим делимость на 17. По лемме $n n 20 − 3$ кратно $20− 3= 17,$ то есть наше число делится на 17 тогда, когда $n 16 − 1$ кратно 17. При этом $n n 16 ≡ (− 1) (mod 17),$ то есть $n 16 − 1$ кратно 17 только при чётном $n.$

Теперь рассмотрим делимость на 19. По лемме $n n 20 − 1$ делится на $20− 1= 19,$ а при $n =2k$ число $n n 2k 2k 16 − 3 = 16 − 3$ делится на $2 2 16 − 3 =13⋅19.$

Итак, исходное число делится на 323 при чётных $n.$

Ответ:

При четных $n$

Интенсивы

Глубокий разбор тем, требующих дополнительного внимания

Ошибка.
Попробуйте повторить позже

Задача 32#132585Максимум баллов за задание: 7

Пусть числа $a$ и $b$ взаимно просты. Докажите, что при делении чисел от 1 до $ab$ на $a$ и на $b$ получаются все возможные пары остатков.

Показать доказательство

Рассмотрим произвольную пару остатков $(n,k),$ где $0 ≤n <a$ и $0 ≤k <b.$ По китайской теореме об остатках для взаимно простых $a$ и $b,$ существует единственное число $c$ такое, что:

c≡ n (mod a) c≡ k (mod b),

причём $0 ≤c <ab.$

Таким образом, для каждой пары остатков $(n,k)$ найдётся ровно одно число $c$ в промежутке от $0$ до $ab− 1,$ дающее при делении на $a$ остаток $n,$ а при делении на $b$ — остаток $k.$

Всего возможных пар остатков $(n,k)$ ровно $a⋅b,$ так как $n$ может принимать $a$ различных значений, а $k$ — $b$ различных значений. Поскольку числа $a$ и $b$ взаимно просты, все эти пары различны и покрывают все числа от $0$ до $ab− 1$ без повторений.

Следовательно, при делении чисел от $1$ до $ab$ на $a$ и на $b$ получаются все возможные пары остатков, что и требовалось доказать.

Ошибка.
Попробуйте повторить позже

Задача 33#132586Максимум баллов за задание: 7

При каких целых $n$ число $n2+ 3n+ 1$ делится на $55?$

Показать ответ и решение

Чтобы число $n2 +3n+ 1$ делилось на $55,$ оно должно делиться и на $5,$ и на $11.$

Сначала рассмотрим делимость на $5$ :

2 2 n + 3n+1 ≡(n− 1) ≡0 (mod 5).

Отсюда $n≡ 1 (mod 5).$

Для делимости на $11$ :

2 2 n + 3n+ 1≡ n − 8n +12≡ (n− 2)(n− 6) (mod 11).

Отсюда $n≡ 2 (mod 11)$ или $n≡ 6 (mod 11).$

Для $n ≡1 (mod 5)$ и $n≡ 2 (mod 11)$ по китайской теореме об остатках существует единственное решение при $n <55,$ не трудно заметить, что это 46.

Для $n ≡1 (mod 5)$ и $n≡ 6 (mod 11)$ по китайской теореме об остатках существует единственное решение при $n <55,$ не трудно заметить, что это 6.

Ответ:

$n =55k+ 6$ или $n= 55k +46,$ где $k∈ ℤ.$

Ошибка.
Попробуйте повторить позже

Задача 34#132588Максимум баллов за задание: 7

Докажите, что для каждого натурального $n$ существуют натуральные $a$ и $b$ такие, что $4a2+9b2− 1$ делится на $n.$

Показать доказательство

Заметим, что достаточно доказать утверждение для случая, когда $n$ — степень простого числа. Тогда для произвольного $n$ с разложением

k1k2 k n= p1 p2 ...prr

можно решить задачу по каждому модулю $pki, i$ а затем по китайской теореме об остатках совместить решения в одно по модулю $n.$ После этого легко подобрать натуральные $a$ и $b,$ прибавив к ним по необходимости кратные $n.$

Таким образом, остаётся рассмотреть случаи $k n= p ,$ где $p$ — простое.

Рассмотрим сначала модуль $k 2 .$ Число $3$ взаимно просто с $k 2,$ то есть $k (3,2 )= 1,$ а значит, существует обратный к $3$ по модулю $k 2 .$ Возьмём $k a≡ 0 (mod 2),$ $1 k b≡ 3 (mod 2 ).$ Тогда

( 1)2 4a2+ 9b2 ≡ 0+9⋅ 3 ≡ 1 (mod 2k).

Аналогично в модуле $3k$ число $2$ обратимо, поскольку $(2,3k)= 1.$ Возьмём $a ≡ 12 (mod 3k)$ и $b≡ 0 (mod 3k).$ Тогда

( ) 4a2+ 9b2 ≡ 4⋅ 1 2+ 0≡ 1 (mod 3k). 2

Если $p⁄= 2,3,$ то также $k (3,p)= 1,$ и можно взять $k a ≡0 (mod p ),$ $1 k b≡ 3 (mod p),$ что снова даёт

2 2 ( 1)2 k 4a + 9b ≡ 0+9⋅ 3 = 1 (mod p).

Для каждого простого делителя $pi$ числа $n$ мы построили пару $(ai,bi),$ таких что

4a2i +9b2i ≡ 1 (mod pkii).

По китайской теореме об остатках существует пара $(a,b),$ такая что

a ≡ai (mod pkii), b≡ bi (mod pkii )

для всех $i,$ и при этом

4a2+ 9b2 ≡ 1 (mod n).

Ошибка.
Попробуйте повторить позже

Задача 35#132927Максимум баллов за задание: 7

Докажите, что не существует натурального $a$ такого, что

2023 2023 (2a +1) − a(2+ a)

является простым.

Подсказки к задаче

Подсказка 1.

Как можно проверять, что число не является простым?

Подсказка 2.

Можно, например, проверить, что оно делится на два различных числа, которые больше 1. Давайте попробуем это сделать. Но у нас многочлен, поэтому проверять делимость на числа, может оказаться не очень полезным... Но что же тогда надо проверять?

Подсказка 3.

Правильно! Давайте проверять делимость на многочлены первой степени от a! Попробуйте перебрать самые простые из них и понять, делится ли наш исходный многочлен на них.

Подсказка 4.

На самом деле наш многочлен делится на a + 1 и a − 1. К сожалению, задача пока не решилась. Какое условие на a позволит нам сказать, что мы решили задачу? А остальные a переберём и проверим прямой подстановкой.

Показать доказательство

Докажем, что

2023 2023 (2a +1) − a(2+ a)

делится на $a+ 1$ в смысле делимости многочленов от $a.$ Поскольку $a ≡a+1 −1$ имеем

2023 2023 (2a+ 1) − a(2+ a) ≡a+1 − 1+1 ≡a+1 0

Аналогично можно показать, что исходный многочлен делится и на $a− 1.$ Таким образом, единственный случай, когда наше число является простым, возможен лишь при $a− 1≤ 2,$ то есть при $a= 2$ или $a =3.$ При $a= 3$ число

(a− 1)⋅(a+ 1)=8,

поэтому исходное число не является простым. Пусть $a= 2.$ Тогда исходное число равно

52023 − 2⋅42023,

а, с другой стороны, оно должно быть равно 3. Ясно, что это не так, поскольку

52023 > 3+ 2⋅42023.

Ошибка.
Попробуйте повторить позже

Задача 36#133197Максимум баллов за задание: 7

(a) Докажите, что многочлен $4 3 2 x + 3x + 2x + 3x− 1$ не делится на многочлен $2 x +1.$

(b) Найдите все целые $x,$ при которых число $4 3 2 x + 3x +2x + 3x− 1$ делится на $2 x +1.$

Показать ответ и решение

(a) Заметим, что $x2 ≡ −1. x2+1$ Следовательно,

4 3 2 2 2 2 2 x +3x + 2x +3x− 1= x ⋅x + 3x ⋅x +2x + 3x +1 ≡x2+1 −2.

Откуда и следует утверждение.

(b) Как мы поняли в пункте (a), остаток от деления равен $− 2.$ Поэтому хотим найти $x$ такое, что $− 2$ делится на $x2+ 1.$ Это возможно только при $x∈ {0,1,−1}.$

Ответ:

(b) $x =0;±1$

Бандлы и наборы

Комбо-тарифы сразу по нескольким предметам

Ошибка.
Попробуйте повторить позже

Задача 37#133202Максимум баллов за задание: 7

Существует ли непостоянный многочлен с целыми коэффициентами, значения которого во всех целых точках являются простыми числами?

Показать ответ и решение

Предположим, что такой многочлен существует. Обозначим его через $P(x).$ Тогда $P (n)= p$ для некоторого целого $n$ и простого $p$ (возьмём $n$ составным). Заметим, что тогда

P(n+ pk) ≡p P(n)≡p 0, ∀k∈ℕ.

Следовательно, $P(n +pk)= p$ для любого натурально $k,$ так как другого простого числа, которое делится на $p,$ не существует. В силу непостоянности многочлена, он не может принимать в бесконечном количестве точек одно значение. Противоречие.

Ответ:

нет

Ошибка.
Попробуйте повторить позже

Задача 38#135874Максимум баллов за задание: 7

Полезное следствие из КТО. Докажите, что для любых попарно взаимно простых чисел $m ,m ,...,m 1 2 n$ и остатков $r,r,...,r 1 2 n$ по модулям $m1,m2,...,mn$ найдутся $n$ последовательных чисел $a+ 1,a+ 2,...,a +n$ таких, что $a+ i≡ ri (mod mi).$

Показать доказательство

Потребуем, чтобы для некоторых подряд идущих $n$ чисел $a+1,...,a+ n$ выполнялось $a +i≡ r (mod m ) i i$ при всех $i= 1,...,n.$

Это равносильно системе сравнений для одного числа $a$ :

a≡ − ri− i (mod mi), i= 1,...,n.

Модули попарно взаимно просты, значит, по Китайской теореме об остатках система имеет решение $a.$ Тогда числа $a+1,$ …, $a+ n$ дают нужные остатки.

Ошибка.
Попробуйте повторить позже

Задача 39#135875Максимум баллов за задание: 7

Докажите, что найдутся $2020$ последовательных натуральных чисел, каждое из которых имеет по меньшей мере три различных простых делителя.

Показать доказательство

Возьмём первые $6060$ простых чисел $p , 1$ $p, 2$ …, $p . 6060$ Потребуем, чтобы каждое из чисел $a+1,$ $a+ 2,$ …, $a+ 2020$ делилось хотя бы на три различных простых числа. Зададим систему сравнений:

(| ||||| a≡ −1 (mod pi) (i= 1,2,3) ||||| a≡ −2 (mod pi) (i= 4,5,6) |||{ ... | ||||| a≡ −k (mod pi) (i= 3k− 2, 3k− 1, 3k) ||||| ... |||( a≡ −2020 (mod pi) (i=6058, 6059, 6060)

Модули попарно просты, поэтому по следствию из КТО существует решение $a,$ причём $a$ можно взять натуральным. Тогда для каждого $k= 1,$ …, $2020$ число $a +k$ кратно трём попарно различным простым числам $p3k−2,$ $p3k−1,$ $p3k,$ следовательно, имеет по меньшей мере три различных простых делителя.

Ошибка.
Попробуйте повторить позже

Задача 40#135876Максимум баллов за задание: 7

Докажите, что

(a) множество простых делителей чисел вида $t2+ t+ 1$ бесконечно;

(b) существует $t$ такое, что $t2+ t+1$ имеет хотя бы $2020$ различных простых делителей.

Показать доказательство

(a) Пусть $f(t)= t2+t+ 1.$ Предположим, что существует лишь конечное множество простых чисел, которые делят хотя бы одно значение $f(t).$ Обозначим их $p1,$ $p2,$ …, $ps.$ Рассмотрим произведение

ˆt= p1p2...ps.

Тогда $ˆ t ≡0 (mod pi)$ для любого $i=1,...,s,$ и потому

f(ˆt)= ˆt2+ ˆt+ 1≡ 0+0+ 1≡ 1 (mod pi).

Значит, ни одно из простых $p , 1$ …, $p s$ не делит $f(ˆt).$ Следовательно, у $f(ˆt)$ найдётся простой делитель, отличный от $p1,$ …, $ps.$ Получили противоречие. Таким образом, простых, которые встречаются в значениях $ˆ f(t),$ бесконечно много.

(b) Из пункта (a) мы знаем, что таких простых бесконечно много. Выберем любые $2020$ различных простых $p1,$ $p2,$ …, $p2020,$ для которых $f(ti)≡ 0 (mod pi)$ при некоторых $ti.$ Заметим, что для любого целого $n:$