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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Теорема о линейном разложении НОД. Для любых целых $a$ и $b$ найдутся $x$ и $y$ такие, что $ax+ by =(a,b).$

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

Первое решение. Запишем последовательно шаги алгоритма Евклида:

(a,b)−→ (a1,b1)−→ ...−→ (an,bn =0)

Тогда $(a,b)= an.$ Теперь в обратную сторону будем восстанавливать $x$ и $y.$ Возьмём $(xn,yn) =(1,0).$ Тогда $anxn+bnyn = an.$ Пусть

bn = pnbn− 1+qnan−1

a =r b +s a n n n− 1 n n−1

где все числа целые. Такие $pn,qn,rn,sn$ найдутся, поскольку $an$ и $bn$ были получены с помощью деления с остатком. Тогда

xnan+ ynbn = xn(rnbn− 1+snan−1)+yn(pnbn−1+ qnan−1)=

= an−1(xnsn+ ynqn)+ bn−1(xnrn+ ynpn)= an−1xn−1+bn−1yn−1

Таким образом, мы смогли найти линейное разложение НОД для пары чисел на шаг раньше. Сделав $n$ шагов, мы получим разложение для $a$ и $b,$ что и требовалось доказать.

_________________________________________________________________________________________________________________________________________________________________________________

Второе решение. Для начала докажем небольшую лемму.

_________________________________________________________________________________________________________________________________________________________________________________

Лемма. Пусть $(a,b)=1.$ Тогда существует целое $x$ такое, что $ax ≡1 (mod b).$

Доказательство. Рассмотрим последовательность $a,a2,...,ab.$ Ясно, что $ak ⁄≡b 0$ при всех натуральных $k.$ Тогда остается $b− 1$ возможный остаток при делении на $b,$ который может появиться у чисел этой последовательности. По принципу Дирихле для некоторых $m,n ∈ℕ$ имеем $am ≡b an.$ Будем считать, что $m > n$ и, используя взаимную простоту, получим $am−n ≡b 1.$ Положим $x =am− n− 1.$

______________________________________________________________________________________________________________________________________________________

Рассмотрим уравнение $ax+ by =(a,b).$ Можно полагать, что $(a,b)= 1$ (в противном случае разделим обе части на $(a,b)$ ). Итак, все свелось к решению уравнения $ax+ by = 1.$ По модулю $b$ получим $ax ≡b 1.$ Такое сравнение, исходя из леммы, имеет решение, что равносильно наличию решения уравнения $ax+ by = 1$ по определению сравнений по модулю.

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

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

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

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

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

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

Подсказка 1:

Из такой делимости следует, что как минимум каждая из скобок делится на p. Что с этим можно сделать?

Подсказка 2:

Но тогда можно рассмотреть, например, сумму выражений в скобках, она тоже будет делиться на p. Она равна 3(a + b + c), возникает два случая.

Подсказка 3:

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

Подсказка 4:

Например, (a + 2b) – (a + b + c) = b – c кратно p. Если рассмотреть аналогичные разности с другими скобками, получится, что все переменные имеют одинаковый остаток при делении на p. Если p не делится на 3, то a, b, c кратны p. Как насчет того, чтобы каждую из них поделить на p?

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

Будем считать, что одно из чисел не делится на $p,$ иначе можно сократить на $p.$ По условию каждая из скобок делится на $p.$ Тогда их сумма

3(a+b +c)≡ 0 (mod p)

Если $p⁄= 3,$ то

a+ b+ c≡ 0 (mod p)

Вычитая из первой скобки, получаем $b− c ≡0 (mod p).$ Из второй скобки получаем $c− a ≡0 (mod p).$ Тогда все три числа делятся на $p,$ противоречие. При $p= 3$ подойдут $a= b=c =1.$

Ответ:

$3$

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

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

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

Источники: ЮМШ-2023, 11 класс, отборочный тур (см. yumsh.ru) | ЮМШ-23/24, 11 класс, 1 отборочный тур (см. yumsh.ru)

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

Сначала докажем лемму.

_________________________________________________________________________________________________________________________________________________________________________________

Лемма.

Пусть $φ (n)$ - функция Эйлера числа $n.$ (Количество чисел от $1$ до $n$ взаимно простых с $n.$ ) Тогда для любого натурального числа $n >1$ справедливо неравенство

∑ n2 d < φ(n)- d|n

_________________________________________________________________________________________________________________________________________________________________________________

Доказательство леммы.

Запишем сумму делителей числа через произведение сумм степеней его простых делителей. Если $n =pα1pα2...pαk, 1 2 k$ то

∑ 2 α1 2 α2 2 αk d =(1+ p1+p1+ ...+ p1 )(1+ p2+ p2+ ...+ p2 )...(1+ pk +pk+ ...+ pk ) d|n

Используя формулу суммы геометрической прогрессии, получаем:

∑ d= (1+ p + p2 +...+ pα1)(1+ p +p2+ ...+ pα2)...(1+ p +p2+ ...+ pαk)= d|n 1 1 1 2 2 2 k k k

(pα11+1 − 1)(pα22+1− 1)...(pαk+1− 1) = ----(p1−-1)(p2-− 1)...(pkk− 1)--.

Функция Эйлера вычисляется по формуле $φ(n)=pα11−1(p1− 1)pα22−1(p2− 1)...pαkk− 1(pk− 1).$ Тогда чтобы получить $φ(n)$ в знаменателе, домножим числитель и знаменатель на $pα11−1pα22−1...pαkk−1$

(pα11+1−-1)(pα22+1−-1)...(pαkk+1−-1)= (p1− 1)(p2− 1)...(pk− 1)

α1−1 α2−1 αk−1 α1−1 α2−1 αk−1 = p1--p2α1−.1..pk--(pα12−1-− 1)(p2-α−k−11)...(pk---−-1)= p1 (p1− 1)p2 (p2− 1)...pk (pk− 1)

(p2α1 − pα1−1)(p2α2− pα2−1)...(p2αk− pαk−1) p2α1p2α2...p2αk n2 = --1----1-----2--φ(2n)------k----k----< -1--2φ(n)--k--= φ(n)

_________________________________________________________________________________________________________________________________________________________________________________

Решение задачи.

По условию и лемме

∑ -n2- 100n < d|nd< φ(n).

Тогда

100n< -n2-⇒ φ(n)< n-. φ(n) 100

То есть количество чисел от $1$ до $n$ взаимно простых с $n$ меньше $-n- 100.$

Рассмотрим два случая: $n$ делится на $100$ и $n$ не делится на $100.$

1. Число $n$ делится на $100.$ Тогда можно разбить числа от $1$ до $n$ на $n-- 100$ групп по $100$ идущих подряд чисел. Если количество чисел от $1$ до $n$ взаимно простых с $n$ меньше $n-- 100$ , то хотя бы в одной группе не будет числа взаимно простого с $n$

2. Число $n$ не делится на $100.$ Тогда среди чисел $2$ до $n$ можно выделить $-n- [100]$ групп по $100$ идущих подряд чисел. Если в каждой группе будет число взаимно простое с $n$ , то чисел взаимно простых с $n$ хотя бы $n [100]+ 1$ ( $1$ тоже взаимно проста с $n$ ). Это противоречит тому, что количество чисел от $1$ до $n$ взаимно простых с $n$ меньше $n 100-$

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

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

Даны взаимно простые числа $a$ и $b.$ Докажите, что для любого нечетного делителя $d$ числа $a2n + b2n$ число $d− 1$ делится на $n+1 2 .$

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

Пусть $d$ — нечетный делитель числа $a2n +b2n.$ В силу взаимной простоты чисел $a$ и $b$ будет также верно, что $d$ взаимно просто с $a$ и $b.$ Тогда по модулю числа $d$ остатки $a,b$ будут обратимы.

Пусть $c$ — такое число, что $c⋅b ≡1 (mod d).$ Тогда

2n 2n 2n a +b ≡ 0 =⇒ (ac) ≡ (− 1) (mod d)

Тогда $(ac)2n+1 ≡ 1,$ то есть число $ac$ имеет показатель по модулю $d$ равный $2n+1$ (так как $(ac)2n+1 ≡1$ означает, что $2n+1$ делится на показатель, но $(ac)2n ≡ −1$ говорит о том, что меньшие степени двойки не будут показателем)

Если $d$ — простое, то $(ac)d−1 ≡1$ и тогда $(d − 1)..2n+1 .$ делится на показатель. Если $d$ составное, то оно раскладывается, как $α1 αk d =p1 ...pk$ при этом предыдущие равенства можно рассмотреть по модулю $pi,$ тогда $n+1 pi ≡1 (mod 2 )$ для всех простых делителей числа $d.$ Тогда $n+1 d≡ 1 (mod 2 ),$ то есть $.. n+1 (d− 1).2 .$

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

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

Дано $101$ -значное число $a$ и произвольное натуральное число $b.$ Докажите, что найдется такое не более чем $102$ -значное число натуральное число $c,$ что любое число вида $caaa...ab$ — составное.

Источники: СПБГОР - 2024, 11.4 (см. www.pdmi.ras.ru)

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

Из признака делимости на $10101+1$ (необходимо рассмотреть знакочередующуюся сумму блоков по $101$ цифре с конца) следует, что числа в которых количество $a$ в записи отличается на четное число имеют одинаковые остатки при делении на $101 10 +1.$
Заметим, что $101 10 +1 ≡11 0,$ а еще по лемме об уточнении показателя $101 10 +1$ не делится на $2 11 ,$ поэтому у $101 10 + 1$ есть простой делитель $p$ отличный от $11.$
Достаточно сделать так, чтобы $cb$ и $cab$ делились на $11$ и на $p$ соответственно. Такое $c$ существует и не превосходит $101 11× p≤ 10 + 1$ по китайской теореме об остатках.

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

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

Малая теорема Ферма. Для любого простого $p$ и взаимно простого с $p$ числа $a$ верно, что $ap−1 ≡ 1$ (mod $p$ )

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

Подсказка 1

Попробуем доказать по индукции, что a^p − a делится на р. База a=1 очевидна. Как сделать переход от а к а+1?

Подсказка 2

Что мы можем сказать про делимость на p для биномиальных коэффициентов в выражении (а+1)^p?

Подсказка 3

p!/(k!(p-k)!) делится на р для всех k кроме 0 и р, поскольку числитель делится на р, а знаменатель - нет. Что тогда останется, если смотреть на выражение по модулю p?

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

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

Давайте возьмем две разные ПрСВ по одному модулю $p$ и перемножим в каждой все числа. Так как наборы остатков одинаковые, то получившиеся произведения будут сравнимы по модулю $p$ .

Тогда рассмотрим две такие ПрСВ: [1, 2, ..., $p− 1$ ] и [ $a$ , $2a$ , ..., $(p− 1)a$ ] (То, что написано справа - это $a⋅$ ПрСВ) и перемножим в каждой все числа.

Получаем, что $1⋅2⋅....⋅(p − 1)≡ a⋅2a⋅....⋅(p− 1)a$ (mod $p$ ) или $p−1 (p− 1)!≡ (p− 1)!a$ (mod $p$ ). Теперь перепишем это через разность, то есть $p−1 p−1 a (p− 1)!− (p− 1)!= (a − 1)(p− 1)!$ делится на $p$ . Из-за того, что НОД( $(p− 1)!$ , $p$ ) = 1 следует, что $p−1 a − 1$ делится на $p$ или $ap−1 ≡ 1$ (mod $p$ )

_________________________________________________________________________________________________________________________________________________________________________________

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

Зафиксируем простое число $p.$ Проверим базу индукции: $a= 1.$ Тогда действительно $1p − 1 =0$ — делится на $p.$ Пусть $ap− a$ делится на $p.$ Докажем, что $(a+1)p− (a+ 1).$ делится на $p.$ Докажем, что для $0 <k < p$ число $Ckp$ делится на $p.$ Действительно, $Ckp = k!(pp−!k)!.$ В каждом из факториалов $k!$ и $(p− k)!$ все сомножители меньше $p,$ а потому взаимно просты с $p.$ Тогда, поскольку $p!$ делится на $p,$ то и $Ckp$ делится на $p.$ Благодаря этому утверждению и биному Ньютона, получаем

(a+ 1)p =∑p Ckak ≡ ap+ 1 k=0 p p

По предположению индукции $ap+ 1≡p a+ 1,$ чтд.

Курсы

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

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

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

Докажите, что натуральные числа $1,2,...,238$ можно расставить по кругу так, чтобы для любых трех подряд идущих по часовой стрелке чисел $a,$ $b,$ $c$ число $2 b − ac$ делилось на $239.$

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

Подсказка 1

Условие задачи напоминает геометрическую прогрессию. А можно ли как-то представить остатки в виде геометрической прогрессии?

Подсказка 2

Все остатки — степени первообразного корня. Как тогда расположить числа, чтобы условие выполнилось?

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

Будем воспринимать наши числа $1,2,...,238,$ как $g,g2,...,gp−1,$ где $g$ — первообразный корень и будем их расставлять по кругу, так как нас интересует значения чисел лишь по модулю $239.$ Расставим их по кругу так $2 p−1 g,g ,...,g .$ Для чисел $i− 1 g ,$ $i g ,$ $i+1 g$ очевидно, что $2i i−1i+1 g − g g$ делится на $239,$ поэтому наша конструкция подходит для всех чисел не на стыке. На стыке все тоже хорошо, так как числа $g$ и $2 g$ можно представить, как $p g$ и $p+1 g .$

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

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

При каких натуральных $n> 1$ существуют натуральное $a$ и простое $p,$ для которых $3p +4p = an?$

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

Подсказка 1

Предположим, что p нечетно. Так как 3 + 4 = 7, удобно использовать LTE-лемму для модуля 7. Какой вывод из нее можно сделать?

Подсказка 2

Точно! Если p отлично от 7, то левая часть делится на 7, но не делится на 49, откуда n = 1. А что получается при p = 7?

Подсказка 3

Верно! Для p = 7 получаем, что левая часть делится на 49, но не делится на 343. Можно ли теперь оценить n сверху?

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

При $p= 2$ левая часть равна $32+ 42 =52,$ так что подходит и $n= 2.$ Пусть теперь $p$ нечётно. Тогда $3p+ 4p = 3p− (−4)p.$ По лемме об уточнении показателя для модуля $7,$

p p v7 (3 − (− 4) )= v7(3− (− 4))+ v7(p)

Значит, при $p⁄= 7$ выражение делится на $7,$ но не на $72,$ и $n =1.$ Если же $p=,7$ то выражение делится на $72,$ но не на $73,$ а значит, $n ≤2.$ Таким образом, мы убедились, что решения существуют только при $n= 2.$

Ответ:

$n =2$

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

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

Докажите, что не существует натурального $a <1010$ такого, что число $a2022− 1$ представимо в виде произведения $50$ последовательных натуральных чисел.

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

Подсказка 1

Предположим, что такое a существует. Тогда, как легко видеть, разница квадрата числа a и 1 делится на 12. А как связаны степени вхождения 2 и 3 в разность квадрата a и 1 и в разность 2022-ой степени a и 1?

Подсказка 2

Верно! Они совпадают. Попробуем теперь изучить именно a²-1. На какую минимальную степень 2 и 3 оно должно делиться?

Подсказка 3

Конечно! Произведение 50 последовательных чисел делится на 50!, а по теореме Лежандра степень вхождения 2 в это число больше 40. Аналогично, степень вхождения 3 больше 20. Как теперь получить противоречие?

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

Предположим противное. Пусть искомое число $a$ существует. Произведение $50$ натуральных чисел кратно $2,$ следовательно $a$ нечетно, а значит $2 a − 1$ кратно $4,$ аналогично $2 a − 1$ кратно $3.$

В силу LTE, $2022 2 2 v2(a − 1)= v2(a − 1)+ v2(1011) =v2(a − 1),$ с другой стороны, произведение 50 натуральных чисел кратно $50!,$ но в силу теоремы Лежандра

[50] [50] [50] v2(50!)= 2- + -4 + -8 + ...> 40

следовательно, $v2(a2− 1)> 40.$ Аналогично, $v3(a2− 1)> 20.$

Таким образом, $1020 ≥ a2 > a2− 1 >240320,$ то есть $100=102 > 2432 =16⋅9= 144,$ тем самым получено противоречие.

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

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

Докажите, что для любого натурального $n$ существует натуральное $k$ такое, что $51k− 17$ делится на $2n.$

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

Решение 1.

Лемма. Для любого натурального $n ≥3$ найдётся натуральное $l,$ такое что $( l ) v251 − 1 =n.$

Доказательство. Индукция по $n.$ База индукции: $n =3.$ Годится $l= 2.$ Переход индукции. Если $( l ) v2 51 − 1 = n,$ то

( 2l ) ( l ) ( l ) v2 51 − 1 = v2 51 − 1 +v2 51 +1 =n +1

Лемма доказана.

_________________________________________________________________________________________________________________________________________________________________________________

Утверждение задачи тоже доказываем индукцией по $n.$ База: $512− 17$ делится на $23 = 8$ . Переход. Пусть $51k− 17$ делится на $2n.$ Хотим добиться делимости на $2n+1.$ Пусть $l$ таково, что $( ) v251l− 1 =n.$ Можем считать, что $51k− 17$ не делится на $17,$ а также что $k >l.$ Тогда рассмотрим разность

( ) ( ) 51k− 17 − 51k−l⋅ 51l− 1 = 51k−l− 17

Так как оба числа $( ) 51k− 17$ и $( ) 51k−l⋅ 51l− 1$ делятся на $2n$ и не делятся на $2n+1,$ то $51k−l− 17$ делится на $2n+1.$

______________________________________________________________________________________________________________________________________________________

Решение 2.

Покажем, что $2n−2$ является показателем числа $51$ по модулю $2n$ (при условии $n≥ 3).$ Этот показатель является делителем числа $ϕ(2n)= 2n−1,$ т.е. является степенью двойки. Но при любом натуральном $s$ верно $( ) v2 512s − 1 = s+ 21.$ Значит, показатель в самом деле равен $2n−2.$

Таким образом, степени числа $51$ пробегают ровно четверть всевозможных остатков по модулю $2n.$ Но по модулю $8$ эти степени могут давать лишь остатки $1$ и $3,$ а значит, степени числа $51$ пробегают все остатки по модулю $2n,$ дающие $1$ или $3$ по модулю $8.$ В частности, остаток $1$ тоже пробегают.

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

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

Известно, что при всех натуральных $n$ число $4(an+ 1)$ является точным кубом. Докажите, что $a =1.$

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

Подсказка 1

Попробуем выбрать n нечетным и простое p > 2. Что можно сказать о степени вхождения p в наш куб?

Подсказка 2

Конечно! По LTE-лемме она равна сумме степеней вхождения p в a+1 и в n. Как показать, что тогда число кубом не является?

Подсказка 3

Верно! При n = p или n = p² степень вхождения p в наше число на 3 не делится, и кубом оно не является. Тогда легко видеть, что a+1 и a³+1 являются степенями двойки. Как теперь показать, что a=1?

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

Выберем какое-нибудь нечётное $n.$ Тогда $4(an +1)= 4(an − (−1)n).$ Рассмотрим разность $a− (− 1)=a +1.$ Предположим, что она делится на какое-нибудь простое $p ⁄=2.$ Тогда по LTE $n n vp(a − (−1) )=vp(a+1)+ vp(n).$ Заметим теперь, что при $n= p$ или $2 n = p$ эта сумма не делится на $3,$ а значит, число не является кубом. Значит, предположение было ошибочным, и $k a+ 1= 2.$ Выберем $n= 3t.$ Предыдущее рассуждение можно применить к числу $3 a$ вместо $a,$ и оно сработает, если $3 s a + 1⁄= 2.$ Осталось рассмотреть случай, когда $k 3 s a+ 1= 2 ,a + 1= 2 .$ Заметим, что $3 (2 ) a + 1= (a +1) a − a+ 1 .$ Значит, число $2 a − a +1$ (очевидно, нечётное), должно быть степенью двойки, то есть равняться единице.

Интенсивы

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

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

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

Пусть $a =22n + 1.$ Докажите, что $a$ простое тогда и только тогда, когда $a$ делит $322n−1 +1.$

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

Докажем, что если $a$ — простое, то $322n−1 + 1$ делится на $a.$ Заметим, что $a ⁄≡±1 (mod 12),$ то есть $3$ не является квадратичным вычетом по модулю $a.$ Тогда $(a−1)∕2 3 ≡ −1 (mod m)$ из критерия Эйлера, что и требовалось.

Пусть $a$ — составное число, и выполнена делимость. Отметим, что $3$ и $a$ взаимно просты ( $2n 2 ≡ 1 (mod 3)$ ), поэтому определено понятие показателя $3$ по модулю $a.$ Рассмотрим показатель $d$ числа $3$ по модулю $a.$ Из $22n− 1 3 ≡ −1 (mod a)$ получаем $22n 3 ≡ 1 (mod a),$ откуда $2n 2$ делится на $d,$ то есть $d$ является степенью двойки. С другой стороны из первого сравнения получаем $2n−1 d >2 ,$ откуда $2n d =2 = a− 1.$

Теперь воспользуемся теоремой Эйлера: согласно ей, $.. ϕ(a) . d.$ Поскольку $a$ – составное, то $ϕ(a) <a− 1.$ Получается, что $.. ϕ(a). a− 1,$ но $ϕ(a)< a− 1,$ причем $ϕ(a)$ – натуральное число. Это невозможно, поэтому мы достигли противоречия.

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

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

Пусть $p$ — простое число, $a$ и $n$ — натуральные числа такие, что $pa−-1= 2n. p − 1$ Каким может быть количество натуральных делителей числа $na?$

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

Подсказка 1

Очевидно, что p нечетно. Из формулы суммы геометрической прогрессии легко видеть, что a четно. А на какую степень двойки может делиться p-1?

Подсказка 2

Верно! Исходя из LTE-леммы, p-1 делится на 2, но не делится на 4. Тогда p имеет остаток 3 при делении на 4, а его квадрат остаток 1. Тогда по LTE-лемме числитель нашей дроби делится на 4. Какова степень вхождения 2 в левую часть данного уравнения?

Подсказка 3

Верно! Она равна разности суммы степеней вхождений 2 в p+1, a и 1. Степени вхождения из нашего выражения не превосходят логарифма от соответствующих чисел! Тогда наша дробь не превосходит (p+1)a/2. Как теперь получить противоречия?

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

При $p= 2$ уравнение имеет вид $2a− 1= 2n$ и не имеет решений в натуральных числах, следовательно, $p$ нечетно.

Если $a$ является нечетным, то число

pa− 1 a− 1 a−2 p-− 1-= p +p + ...+ p+1

так же нечетно, что невозможно, следовательно $a$ кратно $2.$

Предположим, что $p− 1$ кратно $4.$ Степень вхождения $2$ в правую часть равна $v2(pa− 1)− v2(p− 1),$ что, в силу LTE для числа $pa− 1,$ равно $v2(a),$ следовательно, $v2(a)= n,$ а значит $a≥ 2n.$ С другой стороны,

a 2n = p-−-1 =pa−1+ pa−2 +...+ p+ 1> a p− 1

что влечет противоречие.

Таким образом, $p$ дает остаток $3$ при делении на $4,a$ — четно. Тогда $p2 ≡ 32 ≡ 1 (mod 4),$ то есть $p2− 1$ кратно $4,$ а значит, в силу LTE,

v(pa− 1)= v (p2− 1)+v (a∕2)= v(p+ 1)+v (p− 1)+ v(a)− 1 2 2 2 2 2 2

то есть степень вхождения 2 в левую часть исходного уравнения $v2(p+ 1)+ v2(a)− 1,$ что не превосходит

log (p +1)+ log (a)− 1= log (p+1)a 2 2 2 2

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

a p-−-1= 2n ≤ (p+-1)a p− 1 2

pa− 1 ≤ a (p2− 1) 2

a a ap2 p + 2 ≤ 2 + 1

При $a> 2$ верны неравенства $a∕2> 1$ и $a 2a a 2 p =(p )2 > 2p ,$ сложив которые получим противоречие.

Если $a= 2,$ то уравнение имеет вид

p+1 =2n

В случае, если $n$ является составным (обозначим его произвольный делитель за $d$ ), имеем

n d nd p= 2 − 1= (2 ) − 1

кратно $2d− 1> 1,$ что невозможно в силу простоты $p,$ а значит $n$ — так же простое число.

При $n =2$ уравнение $p+ 1= 4$ имеет решение, количество делителей числа $an =2n$ равно $3.$

Если $n⁄= 2,$ то число делителей числа $an =2n$ равно $4$ (делителями являются числа $1,2,n$ и $2n$ ).

Ответ:

$3$ или $4$

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

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

Пусть $p$ — простое число, и $k≤ p.$ Докажите, что

k (p− k)!(k − 1)!≡ (−1) (mod p)

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

Заметим, что

(k− 1)!= 1⋅2⋅...⋅(k− 1)≡ (1− p)⋅(2− p)⋅...⋅(k− 1− p)≡

k−1 ≡ (−1) (p− 1)(p− 2)⋅...⋅(p− (k− 1)) (mod p)

Тогда, в силу теоремы Вильсона, имеем

(p− k)!(k− 1)!≡ (p− k)!(−1)k− 1(p− 1)(p− 2)⋅...⋅(p− (k − 1))≡

≡ (− 1)k−1(p − 1)!≡(−1)k (mod p)

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

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

Натуральные числа $a,b,c,$ не делящиеся на простое число $p,$ таковы, что $a3+ b3+c3$ делится на $p.$ Докажите, что существуют натуральные числа $d$ и $e,$ не делящиеся на $p,$ такие, что $3 3 d +e + 1$ делится на $p.$

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

Запишем условие в виде сравнения

3 3 3 a + b +c ≡p 0

Так как $НО Д(c,p)=1$ по условию, то по модулю $p$ существует обратный элемент для $c.$ Обозначим его $c− 1.$ Очевидно, что $Н ОД(c−1,p)= 1.$ Тогда можно умножить исходное сравнение на $c−3,$ получится

−13 −1 3 (ac ) +(bc ) + 1≡p 0

Возьмем $d ≡p ac−1$ и $e≡p bc−1,$ таким образом, требуемое сравнение разрешимо.

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

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

Пусть $p >3$ — простое число. Рассмотрим сумму

(a)

1 1 1 + 2 + ...+ p− 1

(b)

1+ 12 +-12 + ...+--1--2 2 3 (p− 1)

Пусть в несократимой записи она равна $m∕n.$ Докажите, что $m$ делится на $p.$

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

Подсказка 1, пункт а

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

Подсказка 1, пункт б

Если отбросить квадраты, то все слагаемые не сравнимы по модулю p. Тогда это сумму можно переписать в более привычном виде.

Подсказка 2, пункт б

Изначальная сумма сравнима с 1^2+2^2+…+(p-1)^2. Сверните сумму по формуле суммы квадратов.

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

(a)

_________________________________________________________________________________________________________________________________________________________________________________

Первое решение. Сгруппируем слагаемые и немного преобразуем

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

Так как $p$ — простое, то при приведении к общему знаменателю $p$ не сократится. Следовательно, числитель делится на $p.$

______________________________________________________________________________________________________________________________________________________

Второе решение. Достаточно показать, что сумма по модулю $p$ равна нулю. Заметим, что все обратные остатки не сравнимы по модулю $p,$ тогда

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

_________________________________________________________________________________________________________________________________________________________________________________

(b) Приведём дробь к общему знаменателю:

p−∑1 - 12⋅22⋅...i2...(p − 1)2 i=1----------2------- ((p− 1)!)

Знаменатель полученной дроби взаимно прост с $p,$ следовательно, достаточно показать, что числитель делится на $p.$

Рассмотрим набор $S$ чисел

{1⋅2⋅...i...(p− 1)}pi=−11

Покажем, что элементы образуют полную систему вычетов по модулю $p.$ Предположим противное, тогда найдутся два слагаемых с одинаковым остатком:

1⋅2⋅...i...(p − 1)≡ 1⋅2⋅...j...(p− 1) (mod p)

Все множители взаимно просты с $p,$ значит можно сократить: $j ≡i (mod p),$ но $i$ и $j$ — два разных остатка при делении на $p,$ противоречие. Следовательно, числитель сравним по модулю $p$ с суммой всех остатков при делении на $p,$ кроме $0.$

Числитель дроби является суммой квадратов всех чисел из $S.$ Таким образом,

p−1 ∑ 12⋅22⋅...i2...(p− 1)2 ≡12+ 22+...+(p− 1)2(mod p) i=1

По формуле суммы квадратов первых $n$ натуральных чисел имеем

(p− 1)((p− 1)+ 1)(2(p− 1)+1) p(p− 1)(2p − 1) 12+ 22 +...+(p− 1)2 =------------6-----------= ------6-----

Наконец, $p> 3,$ следовательно, $6$ взаимно просто с $p,$ что влечет делимость числителя изначальной дроби на $p.$

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

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

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

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

Пусть $p$ — простое число. Докажите, что $(2p− 1)!− p$ кратно $p2.$

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

Заметим, что

(2p − 1)!− p= p((p− 1)!(p +1)(p+ 2)...(2p − 1)− 1)

То есть достаточно показать, что вторая скобочка делится на $p.$ По теореме Вильсона

(p− 1)!(p +1)(p+ 2)...(2p − 1)− 1≡ −(p +1)(p +2)...(2p − 1)− 1

Видно, что $(p+ 1)(p+ 2)...(2p− 1) ≡(p− 1)! (mod p)$ (Вычли из каждой скобочки $p$ ). Таким образом,

(p+1)(p +2)...(2p − 1)+ 1≡ (p− 1)!+ 1≡ 0 (mod p)

что и требовалось.

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

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

На доске написаны числа $100,99-,...,-1-. 1 2 100$ Можно ли выбрать какие-то $9$ из них, произведение которых равно $1?$

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

Заметим, что наши числа представляются в виде $-x--. 101−x$ Давайте теперь посмотрим на наши дроби с точки зрения сравнения по модулю $101.$ Тогда это будет выглядеть так:

x x 101-− x-≡ −x-=− 1 (mod 101)

Значит, все дроби сравнимы со $− 1$ по модулю $101.$ Но теперь, если мы допустим смогли взять $9$ чисел, произведение которых равно $1,$ то снова рассматривая сравнение, понимаем, что выходит противоречие. Произведение остатков девяти чисел будет давать $− 1,$ а $1$ не сравнимо с $− 1$ по модулю $101.$

Ответ:

Нельзя

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

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

Дано простое число $p.$ Найдите количество решений сравнения

2 2 x +y ≡ 1 (mod p)

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

Подсказка 1

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

Подсказка 2

Можно просто перенести 1 в левую часть и применить формулу, но тогда в левой части будет находится -y², с этим так же работать сложно. Можно ли от исходного равенства перейти к разности квадратов в левой части, но так, чтобы в правой части осталась 1?

Подсказка 3

Можно умножить исходное равенство на (1/y)² - квадрат остатка, обратного к y, при ненулевом y. Сделайте необходимые преобразования и примените формулу разности квадратов.

Подсказка 4

Пара (x, y) при ненулевом y является решением тогда и только тогда, когда когда 1/y-x/y сравнимо с a и 1/y+x/y сравнимо с 1/a для некоторого данного остатка a. Таким образом, необходимо найти количество решений полученной системы.

Подсказка 5

Если a+1/a обратим, то x и y восстанавливается однозначно. Докажите, что все полученные пары различны. Что можно сказать об a, если a+1/a необратим?

Подсказка 6

Тогда -1 является квадратичным вычетом. Как известно, это возможно только при p, которые имеют вид 4k+1. Закончите разбор этого случая, не забудьте учесть решения при y = 0.

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

Рассмотрим два случая:

1) $p=2.$ Тогда решений всего два $(1;0)$ и $(0;1).$

2) $p⁄=2.$

Для начала предположим, что $y ≡p 0$ и $2 x ≡p 1.$ Тогда $x≡p 1$ или $x≡p − 1.$ Заметим, что если $p⁄= 2,$ то верно $− 1 ⁄≡p 1,$ поэтому $(1;0)$ и $(−1;0)$ — различные решения.

Теперь будем считать, что $y ⁄≡p 0,$ то есть $y$ обратим.

Тогда умножим все сравнение на $−2 y .$ Получаем

(xy−1)2+ 1≡p y−2

По формуле разности квадратов:

(y− 1− xy−1)(y−1+ xy−1)≡p 1

Таким образом, $−1 −1 y − xy$ и $−1 −1 y + xy$ взаимно обратны по модулю $p,$ то есть удовлетворяют системе

{ y−1− xy− 1 ≡ a −1 − 1 p −1 y + xy ≡p a

для некоторого обратимого $a.$ Из этой системы следует, что $2y−1 ≡p a+ a−1,$ поэтому решения существуют тогда и только тогда, когда $a+ a−1$ обратим. Отметим, что если $a+ a−1$ все-таки обратим, то $y ≡p 2−1(a+ a−1)− 1,$ и вычет $x$ тоже восстанавливается однозначно. Таким образом, система имеет единственное решение, если $a+ a−1$ обратим.

Найдем такие $p,$ для которых существуют обратимые $a$ такие, что $a+ a−1$ необратим. Для этого рассмотрим сравнение $a+ a−1 ≡ 0. p$ Оно эквивалентно сравнению $a2 ≡ −1 p$ $⇔$ $− 1$ является квадратичным вычетом по модулю $p.$ По критерию Эйлера, $− 1$ — квадратичный вычет тогда и только тогда, когда

(−1)p−21≡p 1

Очевидно, это сравнение верно только если $p$ имеет вид $4k +1,$ а во всех остальных случаях $− 1$ является невычетом. Таким образом, задача разбивается на два случая.

1.: В случае $p= 4k+ 1$ имеется ровно два решения сравнения $a2 ≡p −1.$ Таким образом, в качестве $a$ в систему можно подставить $p− 2− 1= p− 3$ различных $a$ (все кроме решений указанного сравнения и $0$ ) и получится $p− 3$ различных решения. Вспомним, что еще имеется два решения из $y ≡p 0,$ поэтому общее число решений — $p− 1.$
2.: В случае $p= 4k− 1$ сравнение $a2 ≡p − 1$ не имеет решений, поэтому можно просто подставлять любое $a$ из $p− 1$ возможного. Учтем еще 2 решения из случая $y ≡p 0,$ тогда получится $p+ 1$ решение.

Ответ:

Если $p =4k+ 1,$ то $p− 1$ решений,

если $p =4k+ 3,$ то $p+ 1$ решений.

если $p =2,$ то $2$ решения.

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

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

Пусть $p =4k+ 3$ — простое число, а $m- n$ — такая несократимая дробь, что

--1-- --1-- ----1---- m- 02+ 1 + 12+ 1 + ...+ (p− 1)2+ 1 = n

Докажите, что $2m − n$ делится на $p.$

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

Подсказка 1

Исходное равенство можно рассматривать как сравнимость левой и правой части по модулю p, где каждая дробь a/b произведение a на остаток обратный b по данному модулю.

Подсказка 2

Часто суммы можно преобразовывать благодаря разделению слагаемых на пары. Как этот метод можно применить здесь?

Подсказка 3

Можно складывать слагаемые, которые соответствуют обратным остаткам, то есть сумма слагаемых 1/(x²+1)+1/(y²+1) по всем парам различных чисел x и y, для которых xy сравнимо с 1. Чему будет равна данная сумма, все ли слагаемые будут учтены?

Подсказка 4

После приведения к общему знаменателю, несложно показать, что 1/(x²+1)+1/(y²+1) сравнимо с 1 по модулю p. В сумме будут учтены все числа кроме -1, 1, для которых обратные совпадают с ними и 0, для которого обратного нет. Прибавьте к сумме единиц оставшиеся три слагаемые. Чему она равна?

Подсказка 5

Сумма сравнима с (p+1)/2, откуда m/n сравнимо c (p+1)/2, то есть 2m сравнимо с n(p+1), откуда явно следует требуемое.

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

Первое решение. Введём обозначение $a =i2+ 1 i$ , для $i=0,...,p− 1$ . Тогда рассматриваемое нами выражение равно

m- σp−1(a0,a1,...,ap−1) n = σp(a0,a1,...,ap−1)

где $σi$ — основной симметрический многочлен степени $i$ . Найдём многочлен, корнями которого являются $ai$ , т. е.

p∏−1(x − 1− i2) i=0

Сделав замену $x− 1= t2$ , получим многочлен

p−1 p−1 p− 1 ∏ (t2− i2)= ∏ (t− i)∏ (t+i)≡ (tp− t)(tp − t)= t2p− 2tp+1+ t2. i=0 i=0 i=0

Теперь, сделав обратную замену, для $p= 4k+ 3$ получаем

p−1 ( ) ∏ (x− 1− i2)≡ (x− 1)p− 2(x− 1)p+1∕2+(x− 1)= xp +...+ p+ 2⋅ p+-1 +1 x − 4. i=0 2

По теореме Виета

σp ≡ 4(modp), σp−1 ≡2(modp),

поэтому $. (2σp− 1− σp)..p$ , и, поскольку $σp$ не кратно $p$ , сокращение произойдёт на число, взаимно простое с $p$ , т. е. $. (2m− n)..p$ . _______________________________________________________________________________________

Второе решение. Рассмотрим дроби вида $x12+1-$ , входящие в нашу сумму, как дроби по модулю $p$ (значением дроби $uv$ по модулю $p$ , где $v ⁄≡ 0(modp)$ , считается решение сравнения $vt ≡u(modp)$ ; при сложении обыкновенных дробей со знаменателями, не кратными $p$ , соответствующие им дроби по модулю также складываются).

Как известно, все числа от 2 до $p− 2$ можно разбить на пары $(x,y)$ в которых $xy ≡ 1(modp)$ . Сложим члены, соответствующие числам $x$ и $y$ которые составляют такую пару:

-1---+ -1---= --x2+-y2+-2---≡1(modp) x2+1 y2 +1 x2y2+ x2+ y2 +1

(так как $2 2 x y ≡ 1(modp)$ ). Складывая $p−3 2$ таких сумм и оставшиеся три слагаемых, получаем, что искомая сумма сравнима по модулю $p$ с $p+1 2 ,$ что и требовалось доказать.

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