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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Задача 1#104744

Пусть $P$ — нечётное, большее единицы число и $P =p p ...p 1 2 n$ — его разложение на простые множители (среди $p ,p ,...,p 1 2 n$ могут быть равные). Тогда для произвольного целого числа $a$ символ Якоби определяется равенством:

(a) (a)( a) ( a) P- = p1 p2 ...pn ,

где $( ) api$ — символы Лежандра. По определению считаем $( ) a1 = 1$ для всех $a.$ Докажите, обобщённый квадратичный закон взаимности: если $P,Q$ — взаимно простые нечётные числа, то

( ) ( ) Q- =(−1)(P−1)4(Q−1)⋅ P- P Q

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

Сначала проверим случай, когда одно из чисел $1.$ Пусть $P =1.$ Тогда $( Q)= 1, (-1)= 1, (− 1)0 = 1. 1 Q$ То есть действительно всё сходится.

Теперь пусть $P =p1p2...pn$ и $Q= q1q2 ...qk.$ Из взаимной простоты следует, что $pi ⁄= qj.$ Мультипликативность символа Якоби следует из определения и мультипликативности символа Лежандра: $(a1a2) (a2)(a1) P = P P .$ Тогда

( )( ) ∏n ( ) ∏n ( ) ∏n ∏k( )( ) Q- P- = Q- ⋅ pi = qj pi P Q i=1 pi i=1 Q i=1j=1 pi qj

По квадратичному закону взаимности для простых чисел получаем, что

(Q )( P) ∑n ∑k pi−1 qj−1- -P Q- = (− 1) i=1 j=1 2 2

Значениие степени $− 1$ зависит от чётности показателя, то есть нам нужно доказать, что

∑n k∑ pi−-1qj −-1≡ P-− 1Q-−-1 (mod 2) i=1j=1 2 2 2 2

Для нечётных $a, b$ заметим, что $a−21+ b−21≡ ab−21(mod 2)$ (можно явно проверить, рассмотрев остатки по модулю $4:$ при равных остатках с обеих сторон получится $0,$ при различных остатках — $1).$ Тогда заметим, что в сумме можно вынести $pi2−1$ за второй индекс суммирования:

∑n k∑ p − 1q − 1 ∑n p− 1∑k q − 1 ∑n p − 1Q − 1 -i2---j2--= i2--- -j2--≡ -i2----2-- (mod 2) i=1 j=1 i=1 j=1 i=1

из нашего тождества. Теперь общий множитель $Q−1 2$ можно тоже вынести:

∑n pi− 1 Q− 1 Q − 1∑n pi− 1 Q− 1P − 1 --2---2--= --2-- -2---≡ -2----2-- (mod p) i=1 i=1

снова по тождеству. То есть у нас получилось в точности то, что и требовалось доказать:

( ) ( ) Q- P- = (−1)(P−1)(4Q−1) P Q

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

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

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

Задача 2#108630

Пусть $p$ — простое число, а $m > 1,x >1,y > 1$ — натуральные числа. Оказалось, что

xp+yp- (x+-y)m 2 = 2

Докажите, что $m = p.$

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

Подсказка 1

Для начала попробуйте разобрать случай, когда у чисел x и y есть общий простой нечетный делитель.

Подсказка 2

Если у x и y есть общий простой нечётный делительно, то достаточно посмотреть на его степень вхождения в обоих частях нашего равенства. Теперь пусть у x + y есть нечетный простой делитель q. Что тогда можно сказать про степени вхождения q в нашем равенстве (давайте пока считать, что p > 2)?

Подсказка 3

Для этого достаточно выяснить, как вычислить степень вхождения q в x^p + y^p. Что же может нам помочь в этом?

Подсказка 4

Правильно, лемма об уточнении показателя! Применив ее, легко получить, что m может быть только 1. Теперь можно считать, что x + y вообще не имеет нечётных простых делителей. То есть x + y является степенью двойки. Из нашего равенства также будет следовать, что x^p + y^p тоже степень двойки. Попробуйте осознать, что это бывает довольно редко.

Подсказка 5

Не забудьте рассмотреть случай p = 2. Чтоб разобрать этот случай достаточно на самом деле понять, что при m > 2 правая часть точно больше левой.

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

Пока будем считать, что $p> 2.$ Пусть $q$ — простой общий делитель чисел $x$ и $y.$ Тогда $x = qa ⋅x 1$ и $y = qb⋅x 2$ ( $a≤ b).$ Теперь посмотрим на степень вхождения $q$ в нашем равенстве. Мы получаем, что $am = ap,$ а значит, $m =p.$

Следовательно, достаточно доказать задачу для $α (x,y)= 2 ,$ где $α≥ 0.$ Предположим, что $x +y$ имеет простой множитель $q >2.$ Тогда $x$ и $y$ по отдельности на $q$ не делятся. Тогда по лемме об уточнении показателя получаем

p p vq(x + y )= vq(x+ y)+vq(p)

поэтому $m = 1,$ что неверно. Пусть $(x,y) =2α,$ а значит, $x =2α ⋅x 1$ и $y =2β ⋅y 1$ ( $α ≤ β).$ Мы разобрали случай, когда у $x +y$ есть нечётный простой делитель, поэтому можно считать, что $α= β$ и $k x1+ y1 = 2.$ Следовательно, из нашего равенства мы получаем, что $p p s x1+ y1 = 2,$ где $s$ — какое-то число. Тогда мы знаем, что $p k p s x1+ (2 − x1)= 2 .$ После раскрытия скобок получаем, что степень вхождения двойки справа равна $k,$ а слева равна $s.$ Значит, $s= k.$ Так как $p> 1,$ то $p k p k x1 +(2 − x1) > 2,$ а значит, $x1 = 1,$ и аналогично $y1 = 1,$ то есть $x= y.$ Тогда из условия сразу следует, что $m = p.$

Если же $p =2,$ то мы получаем $2 2 x+ym x +y = ( 2 ).$ Заметим, что $3 2 2 (x +y) > 4(x + y)$ в силу того, что $x> 1$ и $y > 1.$ А значит, левая часть нашего равенства при $m > 2$ точно больше правой. То есть $m$ тоже равно двум.

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

Задача 3#108631

Найдите все натуральные $a,b,c$ и простые $p$ такие, что $2apb =(p+ 2)c+ 1.$

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

Подсказка 1

В случае нечетного c правая часть делится на p+3, а тогда оно является степенью двойки или произведением степени двойки и числа p. Предположим, что это степень двойки. Какие числа тогда заведомо являются вычетами или невычетами по модулю p?

Подсказка 2

Верно! -1 является вычетом, а 2 — невычетом. Тогда -2 — невычет. Возможно ли такое?

Подсказка 3

Конечно же, нет! Пусть теперь p+3 - это произведение степени двойки и p. Легко видеть, что p = 3. Можно ли найти теперь степень вхождения 3 в правую часть?

Подсказка 4

Верно! По лемме об уточнении показателя степень вхождения 3 в правую часть равна степени вхождения 3 в c, увеличенной на 1. Следовательно, с не меньше, чем (b-1)-я степень числа 3. При каких a, b, c это возможно?

Подсказка 5

Остается случай четного c. Обозначим степень вхождения 2 в c через n. Заметим, что если в правой части заменить c на n-ю степень 2, то получится делитель правой части. Тогда мы знаем разложение этой правой части с заменой c на n-ю степень 2 на простые множители. Какие выводы напрашиваются?

Подсказка 6

Верно! Мы видим, что при p > 2 можно применять LTE-лемму по модулю 2! Тогда можно получить уравнение на степени вхождения 2, а что из него следует?

Подсказка 7

Точно! Из этого уравнения легко получается, что степень вхождения 2 в показатель 2 по модулю p равна n+1. Тогда p-1 делится на (n+1)-ю степень 2. Кроме того, можно заметить, что степень вхождения p в левую часть с заменой c на n-ю степень двойки четна. Как тогда можно оценить степень вхождения 2 в b из имеющихся условий?

Подсказка 8

Конечно! Степень вхождения 2 в b, увеличенная на 2, не меньше 3 и не больше степени вхождения 2 в p+3. Отсюда получаем, что p-1 не делится на 8. Какое тогда получается уравнение из исходного?

Подсказка 9

Верно! Мы получаем n = 2 и после подстановки легко видеть, что при p > 5 решений нет (одна из частей уравнения точно больше другой). Остается разобраться со случаями p = 3 и p = 5!

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

Предположим, что $c$ нечетное. Тогда правая часть делится на $p +3,$ откуда $p+3 =2k$ или $p+ 3= 2kpl.$

В первом случае получаем, что $p ≡5 (mod 8).$ Тогда $− 1$ является квадратичным вычетом по модулю $p,$ а $2$ — не является, откуда $− 2$ является квадратичным невычетом по модулю $p,$ но

( c+1)2 2 2 ≡ −2 (mod p)

откуда получаем противоречие.

Во втором случае получаем, что $p+ 3$ делится на $p,$ откуда $p= 3.$ Тогда имеем уравнение $c a b 5 +1= 2 3.$ Заметим, что $v2(5c+ 1)= 1,$ откуда $a= 1.$ По лемме об уточнении показателя получаем, что

v3(5c+ 1)=v3(6)+ v3(c)= 1+v3(c)

откуда $b−1 c≥ 3 .$ То есть $3b−1 b 5 < 2⋅3,$ что возможно только при $a= b= c= 1$ и $p =3.$

Разберем случай четного $c.$ Пусть $v2(c)=n,$ то есть $n c =2 ⋅m.$ Заметим, что $2n (p+ 2) + 1$ делит $c (p+ 2) + 1,$ откуда

n (p+ 2)2 +1= 2k⋅pl

Заметим, что $2n (p+2) + 1≡ 2 (mod 4)$ при $p> 2,$ откуда $k= 1.$ Тогда $2n b (p+2) − 1=2 ⋅(p − 1).$ Тогда

2n v2((p +2) − 1)= v2(p+ 1)+v2(p+3)+ v2(n)− 1

С другой стороны

v2(2 ⋅(pl− 1))= v2(p− 1)+ v2(p+ 1)+v2(l)

откуда

v2(p+3)+ n− 1= v2(p− 1)+v2(l)

Заметим, что $2n+1 2 ≡1 (mod p),$ а $2n 2 ⁄≡ 1 (mod p),$ откуда следует, что $v2(ordp2)= n,$ то есть $p− 1$ делится на $n+1 2 .$ Тогда $p ≡1 (mod 4).$ Посмотрим на наше равенство по модулю $p+ 1.$ Имеем $l 2≡ 2⋅(−1),$ откуда $l$ — четное. Тогда из только что полученного равенства на степени вхождения следует, что

v2(p+ 3)≥ 2+ v2(b)≥ 3

То есть число $p − 1$ не может делиться на $8.$ Значит, $n+ 1=2,$ откуда $n= 1.$ Тогда имеем уравнение

(p+ 2)2+ 1= 2pl

Заметим, что при $p> 5$

l 2 2 2p≥ 2p > (p+ 2) +1

Если $p= 3,$ то $26=2 ⋅3l$ — нет решений.

Если $p= 5,$ то $50=2 ⋅5l,$ откуда $l= 2.$

Вернемся к исходному уравнению

72m +1 =2a⋅5b

Посмотрев по модулю $4,$ получаем $a= 1.$ Далее $72m + 1= 5t⋅(72+1).$ Но по лемме об уточнении показателя

v5(72m +1)= v5(72+ 1)+v5(m )

откуда $m ⋅(72+ 1)≥72m+1,$ что не может быть правдой. Значит, $c= 2m =2,$ $a= 1,$ $b= 2,$ $p= 5.$

Ответ:

$(1,1,1,3),$ $(1,2,2,5)$

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

Задача 4#118930

Дано простое число $p.$ Для каждого натурального $x ∈{1,2,...,p− 1}$ рассмотрим выражение $x2+ 3x +1.$ Оказалось, что ровно $1$ из них делится на $p.$ Найдите все возможные значения $p.$

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

Пусть $a2+ 3a+ 1≡ 0, p$ рассмотрим обратный вычет $a−1$ (он существует, так как $a⁄≡ 0 p$ и $p -простое число$ ) и выражение $−2 −1 a + 3a + 1.$

−2 − 1 a2+ 3a+ 1 a + 3a +1 ≡p----a2----≡p 0,

но по условию такое число одно, получаем, что $−1 2 a≡p a ⇒ a − 1 ≡p 0⇒ a ≡1 или a≡ −1.$

Пусть $a≡p 1,$ тогда $1+ 3+ 1≡p 0 ⇒ p= 5,$ проведем проверку, что для $x∈ {2,3,4}$ неверно $x2+ 3x+ 1 ≡p 0.$

$2 x =2 ⇒ x +3x+ 1≡5 1$
$x =3 ⇒ x2+3x+ 1≡5 −1$
$x =4 ⇒ x2+3x+ 1≡5 −1$

Пусть $a≡p − 1,$ тогда $a2+ 3a+1 =1 − 3+ 1= −1≡p 0,$ что невозможно при любом $p.$

Ответ:

$p =5$

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

Задача 5#118941

Даны натуральные числа $a,$ $b$ и $c$ такие, что $ab+9b+ 81$ и $bc+ 9c+81$ делятся на $101.$ Докажите, что тогда и $ca+ 9a +81$ тоже делится на $101.$

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

Так как $101$ это простое число, то у всех ненулевых вычетов есть обратный. Тогда $ab+9b+ 81 ≡ 0⇒ b⁄≡ 0, 101 101$ поэтому перейдём к обратному остатку

−81− 9b a ≡101 ---b---

Аналогично $b+ 9$ взаимно просто с $101,$ откуда

−81 bc+ 9c +81≡101 0⇒ c(b+9)≡101 − 81 ⇒ c≡101 b+-9

Тогда то, что нам нужно доказать, действительно, верно

ca +9a+ 81≡101 81(81+-9b)− 9⋅81-+81b+ 81 ≡101 b(b+9) b

812-+9⋅81b−-9⋅81b−-81b2−-812− 9⋅81b+-81b2+-9⋅81b b(b+9) ≡101 0

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

Задача 6#118946

Докажите, что для любого простого $p> 3$ существует бесконечно много натуральных $n$ таких, что $2n+ 3n +6n − 1$ делится на $p.$

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

По малой теореме Ферма: если $a⁄≡ 0⇒ ap−1 ≡ 1. p p$ Тогда $2n+p−1 ≡ 2n,3n+p−1 ≡ 3n,6n+p−1 ≡ 6n, p p p$ то есть

n n n n+p−1 n+p− 1 n+p−1 2 +3 + 6 − 1≡p 2 + 3 +6 − 1

значит, надо найти одно $n$ такое, что $2n+ 3n +6n − 1≡p 0.$

Рассмотрим $n= −1,$ пусть оно и ненатуральное, последующие будут натуральными:

−1 −1 −1 3+-2+1- 2 + 3 +6 − 1≡p 6 − 1≡p 0

Курсы

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

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

Задача 7#118947

Пусть $p$ — простое число, большее $2.$ Докажите, что существует такая перестановка $(x,x ,...,x ) 1 2 p−1$ чисел $(1,2,...,p − 1),$ что

x1x2+ x2x3 +...+ xp−2xp−1 ≡2 (mod p)

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

Пусть $x = 1 modp. i i$ Условие перепишется следующим образом:

-1- -1- -----1----- x1x2+ x2x3+ ...+ xp−2xp−1 ≡p 1⋅2 +2 ⋅3 +...+ (p− 2)⋅(p− 1)

Заметим, что

---1-- ≡p--1-− 1, j(j+1) j+ 1 j

тогда

-1-+ -1-+ ...+ -----1----- ≡p 1− 1 + 1− 1+ ...+-1--− -1--≡p 1⋅2 2⋅3 (p− 2)⋅(p− 1) 2 2 3 p− 2 p− 1

1 1 1− p−-1 ≡p 1− −1-≡p 2

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

Задача 8#119614

Для каждого натурального $n$ определим число $φ(n),$ равное количеству целых чисел $m,1 ≤m ≤ n$ взаимно простых с $n.$ Найти $φ(1947).$

Источники: Росатом - 2025, 11.3 (см. olymp.mephi.ru)

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

Подсказка 1

Заметим, что у 1947 в разложении на простые ровно 3 простых делителя. Давайте попробуем решить задачу в общем виде для чисел с 3 простыми делителями в некоторых степенях.

Подсказка 2

В данном случае будет проще посчитать, сколько всего чисел, не взаимно простых с n, и потом вычесть.

Подсказка 3

Как насчёт того, чтобы сначала отдельно посчитать количество чисел, делящихся на первый простой делитель, затем — на второй, третий, после — на первый и второй и так дальше.

Подсказка 4

А как теперь найти количество не взаимно простых, зная результаты вычислений из предыдущей подсказки? Нужно немного манипуляций с формулой включения-исключения.

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

Пусть $n =pr1⋅pr2 ⋅pr3, 1 2 3$ где $p,p ,p 1 2 3$ — различные простые числа, $r ,r ,r 1 2 3$ — их (натуральные) кратности. Количество чисел, не больших $n,$ делящихся на $p1 :$

r1−1 r2 r3 n1 = p1 ⋅p2 ⋅p3

Количество чисел, не больших $n,$ делящихся на $p : 2$

r1 r2−1 r3 n2 = p1 ⋅p2 ⋅p3

Количество чисел, не больших $n,$ делящихся на $p3 :$

r1 r2 r3−1 n3 = p1 ⋅p2 ⋅p3

Количество чисел, не больших $n,$ делящихся на $p1⋅p2 :$

n = pr1−1⋅pr2−1⋅pr3 4 1 2 3

Количество чисел, не больших $n,$ делящихся на $p1⋅p3 :$

n5 = pr11−1⋅pr22⋅pr33−1

Количество чисел, не больших $n,$ делящихся на $p2⋅p3$

n6 = pr11 ⋅pr22−1⋅pr33−1

И наконец, количество чисел, делящихся на $p1⋅p2⋅p3 :$

n7 = pr11−1 ⋅pr22−1⋅pr33−1

Общее количество чисел, не взаимно простых с $n,$ по формуле включений-исключений равно

n1+ n2+n3 − n4− n5− n6+n7 =pr11−1⋅pr22−1⋅pr33−1(p1⋅p2+ p1⋅p3+p2⋅p3− p1− p2− p3+ 1)

Тогда

φ(n)= n− n1− n2 − n3+ n4+ n5+n6 − n7 =

= pr1−1⋅pr2−1⋅pr3−1(p ⋅p ⋅p − p ⋅p − p ⋅p − p ⋅p +p + p +p − 1)= 1 2 3 1 2 3 1 2 1 3 2 3 1 2 3

= pr1−1⋅pr2−1⋅pr3−1(p1− 1)(p2− 1)(p3− 1) 1 2 3

Таким образом, при $n =1947= 3⋅11 ⋅59$ имеем

φ(1947)= (3− 1)(11− 1)(59− 1)= 1160

Ответ:

1160

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

Задача 9#121044

Пусть $a ,a,...,a 1 2 p−21$ — все квадратичные вычеты по модулю $p.$ Для $k= 1,$ $2,$ $3,$ …, $p−1 2$ найдите

σk(a1,a2,...,ap−12 ) (mod p)

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

Квадратичными вычетами по модулю $p$ являются те и только те числа, которые удовлетворяют сравнению $a p−21-≡1 (mod p).$ Давайте рассмотрим многочлен $p−21- x − 1.$ Его корни $a1,a2,...,ap−21.$ Если вспомнить теорему Виета, становится ясно, что $σk(a1,a2,...,ap−21) (mod p)$ — модуль коэффициента при $p−1 x 2 −k$ у рассмотренного многочлена, умноженный на $(−1)k.$ Все коэффициенты, кроме свободного члена, равны $0,$ значит, соответствующие сигмы сравнимы с $0,$ а $σp−1≡ (−1)p−21-(mod p). 2$

Ответ:

$σ ≡ 0 (mod p) k$ при $k < p−1- 2$ и $σ ≡(−1)p−21(mod p) p−21-$

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

Задача 10#121643

Найдите все пары числел $(p,n),$ где $p−$ простое, а $n−$ целое и при этом $p4+ 211= n2+ 5pn.$ В ответе укажите значения $n.$ Если их несколько, перечислите их в любом порядке через запятую.

Источники: ИТМО-2025, 11.6(см. olymp.itmo.ru)

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

Подсказка 1

Хотим использовать малую теорему Ферма (МТФ). Посмотрим на левую часть: по какому модулю удобно рассматривать остаток?

Подсказка 2

Рассматриваем остаток по модулю 5 (тогда возникает требование, что p не равно 5), так как по МТФ p⁴ дает остаток 1 по модулю 5. Вся левая часть, получается, дает остаток 2 по модулю 5. Теперь посмотрим на правую часть. Сразу видно, что второе слагаемое дает остаток 0 по модулю 5 (так как имеет вид 5*q). Что тогда можно сказать о n²?

Подсказка 3

Получается, n² должно давать остаток 2 по модулю 5. Рассмотрим различные случаи остатков. Какой вывод можем сделать?

Подсказка 4

Да, n² не может давать остаток 2 по модулю 5. Тогда у нас остается единственное возможное значение p: p = 5. Тогда наше уравнение превращается в квадратное, которое легко решается!

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

Согласно малой теореме Ферма, если $p⁄= 5,$ число $p4$ даёт остаток 1 при делении на 5. Число 211 также даёт остаток 1 при делении на 5. И $5pn$ делится на $5.$ Значит, если $p⁄= 5,$ мы получаем, что $2 n$ даёт остаток 2 при делении на 5, что невозможно.

Осталось разобрать случай $p =5.$ В этом случае нам надо решить квадратное уравнение

2 n +25n− 625 − 211= 0

−25±-√3125+-4⋅211 n1,2 = 2

Откуда получаем два решения: $(p,n)=(5,−44)$ и $(p,n)= (5,19).$

Ответ:

$− 44,19$

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

Задача 11#122423

Три простые числа $p,q$ и $r$ больше трех и удовлетворяют условию $2p+ 5q = r.$ Для какого наибольшего $n$ число $p+q+ r$ всегда будет делиться на $n?$

Источники: СПбГУ - 2025, 11.3(см. olympiada.spbu.ru)

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

Подсказка 1

Чтобы угадать ответ, попробуйте записать число p + q + r, используя равенство из условия.

Подсказка 2

Скорее всего, вы поняли, что работать надо с делимостью на 3. Быть может, повезёт и даже с девяткой получится.

Подсказка 3

Рассмотрите варианты остатков p и q при делении на 3. Чтобы доказать, что больше 9 нельзя, подберите два примера, чтобы НОД значений p + q + r был 9.

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

Покажем, что $p+ q+ r$ всегда делится на $9.$ Действительно, по условию $2p+ 5q =r,$ поэтому

p +q+ r= 3p+6q = 3(p+2q)

Заметим, что

2p+ 5q = 2(p+ q)+3q

поэтому если $p$ и $q$ дают остатки $1$ и $2$ от деления на три, то $2p+ 5q$ делится на три и больше трех, поэтому $r$ не может быть простым числом. Значит, $p$ и $q$ дают одинаковые остатки от деления на три. Тогда $p+ 2q$ делится на три, а, значит, $p+q+ r$ делится на $9.$

Подберем две различных тройки простых: если $p =11$ и $q = 5,$ то $r= 2p+5q = 47$ — простое число и $p+q+ r= 63.$ Если $p= 17$ и $q = 5,$ то $r= 2p+ 5q =59$ — простое число и $p+ q+r =81.$ Поэтому для чисел из условия задачи $p+ q+r$ гарантированно может делиться только на $Н ОД(63,81)=9.$

Ответ:

$9$

Интенсивы

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

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

Задача 12#125072

Найдите все такие пары целых чисел $m$ и $n >2$ , что $((n − 1)!− n)⋅(n− 2)!= m(m − 2).$

Источники: Всеросс, 2025, РЭ, 9.5 (см. olympiads.mccme.ru)

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

Подсказка 1:

Давай заметим, что в правой части равенства почти полный квадрат. Не хватает 1. Давайте добавим её слева и справа.

Подсказка 2:

Также хотелось бы разложить на скобочки левую часть, притом желательно на взаимно простые. Если не получается угадать разложение, рассмотрите выражение слева как квадратный трёхчлен относительно (n-2)!.

Подсказка 3:

Итак, вы получили равенство ((n - 1)! - 1)((n - 2)! - 1) = (m - 1)². Являются ли скобки в левой части взаимно простыми?

Подсказка 4:

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

Подсказка 5:

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

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

Заметим, что

((n − 1)!− 1)((n− 2)!− 1)=(n− 1)!⋅(n− 2)!− (n− 1)!− (n− 2)!+1 =

2 2 ((n− 1)!− n)⋅(n − 2)!+ 1= m − 2m +1 =(m − 1) .

Пусть $n> 4.$ Заметим, что числа $(n − 1)!− 1$ и $(n− 2)!− 1$ взаимно просты. Предположим, что это не так, и оба этих числа делятся на простое число $p.$ Тогда число

(n− 1)!− 1− ((n− 2)!− 1)⋅(n− 1)= n− 2

тоже делится на $p.$ Тогда $(n− 2)!$ делится на $p,$ а $(n− 2)!− 1$ не кратно $p,$ противоречие. Таким образом, произведение взаимно простых чисел $(n − 1)!− 1$ и $(n− 2)!− 1$ —– точный квадрат, тогда и каждое из них точный квадрат. Однако, число $(n − 1)!− 1$ при $n >4$ даёт остаток 3 при делении на 4, поэтому оно точным квадратом быть не может. Остаётся разобрать случаи $n ≤ 4.$ При $n= 4$ получается $(m − 1)2 = 5,$ решений нет. При $n =3$ мы получаем: $(m − 1)2 = 0,$ что даёт единственное решение $m = 1$ , $n =3.$

Ответ:

$m = 1,n = 3.$

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

Задача 13#126313

Найти все натуральные числа $n ≥3$ такие, что для любого целого числа $m ≥0$ существуют $n$ целых чисел $x,...,x 1 n$ таких, что $x1+ ⋅⋅⋅+ xn = 0$ и $x1x2+ x2x3+⋅⋅⋅+$ $xn−1xn+ xnx1 = −m.$ Среди чисел $x1,...,xn$ могут быть совпадающие.

Источники: Всесиб - 2025, 10.4 ( см. sesc.nsu.ru)

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

Подсказка 1

Давайте попробуем пойти снизу-вверх. Что, если n = 3?

Подсказка 2

Попробуйте обозначить x₁, x₂ и x₃. Какими должны быть это обозначения, чтобы x₁ + x₂ + x₃ = 0?

Подсказка 3

Например, x₃ = - x₁ - x₂.

Подсказка 4

Попробуйте посмотреть на остатки от деления.

Подсказка 5

Быть может, с n = 4 нам подойдут аналогичные иксы?

Подсказка 6

Попробуйте увидеть полный квадрат.

Подсказка 7

Кажется, что с n = 5 противоречий не находится. Может, стоит попробовать придумать пример в общем виде?

Подсказка 8

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

Подсказка 9

А давайте вспомним пример для n = 3.

Подсказка 10

Чтобы он работал и для n = 4, можно, например, докинуть 0.

Подсказка 11

А можем ли мы при помощи 0 доказать, что и для n ≥ 5 условия выполняются?

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

Пусть $n =3.$

Положим $x1 = a,x2 =b,x3 = −a− b,$ тогда

x1x2+ x2x3+ x3x1 =ab− b(a +b)− a(a+ b) =

2 2 = −a − b − ab= −m

m = a2+ b2+ ab= (a − b)2+3ab

Из последнего равенства следует, что остаток от деления числа $m$ на 3 совпадает с остатком от деления $(a − b)2$ на 3, а он может быть равен только 0 и 1. Следовательно, числа $− m$ для всех $m,$ дающих при делении на 3 остаток 2, не могут быть представлены требуемым в условии образом, поэтому $n =3$ не подходит.

Пусть $n= 4.$

Положим $x1 = a,x2 =b,x3 = c,x4 = d= −a − b− c.$ Тогда

ab+bc+ cd +da= (a+c)(b+ d)=

=− (a +c)2 =− m

m =(a+ c)2

Следовательно, в требуемом в условии виде представляются только те числа $− m,$ для которых $m$ является точным квадратом, поэтому случай $n = 4$ тоже нам не подходит.

Пусть $n≥ 5$

Для произвольного $m ≥ 0$ рассмотрим $n$ целых чисел:

{− m;1;0;m − 1;0;0;...;0}

Их сумма равна 0, а сумма попарных проиведений по циклу равна $− m,$ следовательно, любое $n≥ 5$ удовлетворяет условию задачи.

Ответ:

$n ≥5$

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

Задача 14#126643

Коля выписал каждый натуральный делитель числа $2025n$ по одному разу, после чего покрасил некоторые из них в красный цвет, а остальные — в синий. При этом он действовал так, чтобы разность между суммой всех красных делителей и суммой всех синих делителей оказалась минимально возможным (при данном $n$ ) положительным числом. Какими могут оказаться две последние цифры этой разности? (Найдите все варианты и докажите, что других нет.)

Источники: ФЕ - 2025, 10.5 ( см. www.formulo.org)

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

Подсказка 1

Разложите 2025 на простые множители. Как выглядит сумма всех его делителей? Почему максимальный делитель 2025ⁿ больше суммы остальных? Сумма делителей растёт медленнее, чем само число, из-за степеней в разложении.

Подсказка 2

Чтобы разность сумм красных и синих делителей была минимальной положительной, как нужно раскрасить делители? Что произойдёт, если покрасить только 2025 в красный, а остальные — в синий? Разность будет 2 × 2025ⁿ.

Подсказка 3

Докажите, что искомая разность = 70n + 81 (mod 100). Какие остатки при делении на 100 могут быть у 70n + 81 при разных n? Переберите n от 1 до 20. Остатки будут циклически повторяться!

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

Если $n = 0,$ разность равна $1.$ Пусть $n >0.$ Сумма всех делителей числа 2025 равна

2 4n 2 2n (1 +3+ 3 + ...+ 3 )(1+ 5+ 5 +...+5 )=

n−1 n−1 =(1+ 120(1+ 81+...+81 ))(1 +30(1 +25+ 25 ))≡

≡ 1+ 120n+ 30(6+ 5n)≡ 81 +70n (mod 100)

По формуле суммы геометрической прогрессии, сумма делителей меньше, чем

( ) ( ) 34n⋅ 3 52n⋅ 5 =2025n⋅ 15 2 4 8

Значит, максимальный делитель (само число $2025n)$ превосходит сумму остальных, поэтому для получения минимального положительного результата перед ним должен стоять плюс, а перед остальными делителями — минус. Получается, что ответ имеет вид $50− 81− 70n (mod 100) ∈$ ${9;19;29;39;49;59;69;79;89;99}.$ Заметим, что разность больше $2025 8 > 9,$ то есть по крайней мере двузначная.

Ответ:

1, 09, 19, 29, 39, 49, 59, 69, 79, 89, 99

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

Задача 15#126939

Докажите, что для каждого натурального $a >1$ существует простое $p$ такое, что число $1+ a+ a2+ ...+ap−1$ — составное.

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

Заметим, что для $a= 2$ подойдет $p= 11,$ действительно:

0 1 10 2 +2 + ...+ 2 = 2047=23⋅89.

Далее $a >2.$

Выберем в качестве $p$ простой делитель числа $a− 1>1.$ Тогда:

1+a +a2+ ...+ ap−1 ≡1 +1+ ...+ 1≡ 0 (mod p). ◟----◝◜p----◞

Значит, наше число кратно $p,$ осталось лишь показать, что это число больше $p.$ Это действительно так, поскольку $a$ уже больше $p.$

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

Задача 16#127166

Покажите, что при всех натуральных $a,n> 1$ число $φ(an − 1)$ делится на $n$ .

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

Рассмотрим модуль $m= an− 1.$ Заметим, что:

n НОД(a − 1,a)= НОД (1,a)= 1

Значит, применима теорема Эйлера $aφ(m) ≡ 1 (mod m).$

С другой стороны $ordm a= n,$ так как при $k <n$ имеем $ak < an− 1.$ Тогда получаем, что $n$ делит $φ(an− 1),$ что и требовалось.

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

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

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

Задача 17#127175

Найдите все натуральные $n,$ для которых числа $n$ и $2n− 1$ имеют один и тот же набор простых делителей.

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

Подсказка 1.

Рассмотрите простой делитель p у числа n. Как можно использовать, что 2ⁿ−1 делится на p?

Подсказка 2.

Правильно! Ввести показатель и получить условия на него.

Подсказка 3.

Получаем, что n и p−1 делятся на этот показатель, а дальше непонятно, что делать... Было бы отлично, если бы n и p−1 были взаимно просты.

Подсказка 4.

Воспользуйтесь принципом крайнего на стадии выбора p.

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

Очевидно, что $n = 1$ подходит. Пусть теперь $n≥ 2,$ рассмотрим минимальный простой делитель $p$ числа $n.$ Пусть $ord 2= s. p$ Тогда $φ(p)$ делится на $s,$ то есть $p− 1$ делится на $s.$ По условию $n 2 − 1$ делится на $p,$ значит, $n$ делится на $s.$ Заметим, что $(n,p− 1)= 1,$ так как $p$ — минимальный простой делитель $n.$ Отсюда получаем, что $s= 1,$ значит, $1 2 − 1= 1$ делится на $p.$ Получаем противоречие, значит, таких $n≥ 2$ не существует.

Ответ:

$n =1$

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

Задача 18#127177

Докажите, что для простого $p$ уравнение $ap +bp = cp$ не имеет решений в натуральных числах при $a$ , $b$ , $c≤ p.$

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

Подсказка 1

Иногда полезно рассмотреть крайние случаи. Может ли равенство достигаться, если одно из чисел равно p?

Подсказка 2

Если ни одно из чисел не равно p, то они точно меньше. Может тогда посмотреть на делимость, ведь у нас есть малая теорема Ферма.

Подсказка 3

Из малой теоремы Ферма легко получается, что a + b ≡ c (mod p). Но все числа меньше p, какие есть варианты?

Подсказка 4

Полезно бы сравнить aᵖ + bᵖ и cᵖ при полученных условиях, кажется одна из частей будет намного больше другой.

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

Предположим противное: пусть существуют натуральные числа $a,b,c≤p,$ удовлетворяющие уравнению $ap+bp = cp.$

Рассмотрим случаи, когда одно из чисел $a,$ $b,$ $c$ равно $p.$

Пусть $a= p.$ Тогда $p p p p + b = c.$ Так как $c≤ p,$ то $p p c ≤p .$ Следовательно,

p p p p p p +b ≥ p + 1> p ≥c ,

что невозможно. Аналогично для $b= p.$

Пусть $c=p,a⁄= p,b ⁄=p.$ Тогда

p p p p a +b ≤ 2(p− 1) <p ,

так как

(-p--)p = (1+--1-)p > 1+--p-> 2. p− 1 p− 1 p− 1

Теперь $a,b,c< p$ и $p$ – простое, значит, $a,b,c$ не делятся на $p.$ По малой теореме Ферма:

ap ≡a (mod p), bp ≡b (mod p), cp ≡ c (mod p).

Подставляя в исходное уравнение, получаем:

a +b≡ c (mod p).

Так как $1≤ a,b,c≤ p− 1,$ то $2≤a +b≤ 2(p− 1).$ Возможны два случая:

$a +b= c,$
$a +b= c+ p.$

а) Пусть $a+b= c.$

Тогда $ap +bp = (a +b)p.$ По биному Ньютона:

(a +b)p =ap +bp+ p−∑ 1(p)ap−kbk > ap +bp, k=1 k

так как все дополнительные слагаемые положительны при $a,b> 0$ и $p >1.$

б) Пусть $a+b= c+ p.$

Обозначим $s= a+ b,$ тогда $c =s− p, 2p− 1>s >p.$ Уравнение принимает вид:

p p p a +b = (s− p) .

При фиксированном $s$ минимум $ap+ bp$ достигается при $a =b = s, 2$ и тогда

p p (s)p 1−pp a +b ≥ 2 2 = 2 s .

Рассмотрим убывающую при $x> p$ функцию

( x )p f(x)= x-− p .

Так как функция убывает, то

( )p f(s)> f(2p)= 2p = 2p > 2p− 1 =⇒ p

21−psp > (s− p)p = cp,

что завершает доказательство.

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

Задача 19#127237

Как изменятся частное и остаток, если делимое и делитель увеличить в $5$ раз?

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

Пусть число $a$ даёт остаток $r$ при делении на $b,$ то есть $a= b⋅c+ r.$ Увеличим делимое в пять раз, тогда получим $5a= 5b⋅c+ 5r.$ Так как по условию делитель стал равен $5b,$ видим, что частное осталось неизменным, а остаток увеличился в пять раз. Важно отметить, что так как $0 ≤r <b,$ $0≤ 5r< 5b,$ то есть $5r$ действительно является остатком при делении на $5b.$ В силу однозначности определения остатка полученный нами результат — единственно возможный.

Ответ:

Остаток увеличиться в пять раз

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

Задача 20#127238

Число $a$ даёт остаток $3$ при делении на $5.$ Какой остаток оно может давать при делении на $15?$

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

По условию $a= 5c+ 3,$ пусть частное при делении $a$ на 15 равно $x,$ а остаток равен $r,$ то есть $a =15x+ r.$ Приравняем правые части имеющихся равенств:

5c+ 3= 15x+ r

5c− 15x= r− 3

Заметим, что $5c− 15x$ кратно пяти, а, значит, $r− 3$ тоже нацело делится на 5. Учитывая, что $r$ — остаток при делении на 15, то есть $0 ≤r< 15,$ получаем три возможных варианта: $r= 3;$ $8;$ $13.$

В самом деле, число $a =3$ имеет остаток 3 при делении на 5 и 15, число $a= 8$ имеет остаток 3 при делении на 5 и остаток 8 при делении на 15, и наконец, число $a= 13$ имеет остаток 3 при делении на 5 и остаток 13 при делении на 15.

Ответ:

3; 8; 13

Следующая подтема