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

Остатки и сравнения по модулю → .06 Обратные остатки

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Докажите, что для любого натурального $k$ можно выбрать натуральные числа $a ,a ,...,a 1 2 k+3$ и простое число $p$ так, что $aiai+1ai+2ai+3− i$ делится на $p$ для всех натуральных $i=1,2,...,k.$

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

Подсказка 1

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

Подсказка 2

Предлагается простроить пример в рациональных числах(ведь рациональные числа это остатки). Как его построить? Как из него перейти в натуральные числа?

Подсказка 3

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

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

Выберем различные положительные рациональные числа $r,r ,...,r 1 2 k+3$ так, чтобы

riri+1ri+2ri+3 = i

для $1≤ i≤k.$ Пусть $ri = ui. vi$ Выберем простое число $p$ такое, что $p$ не делит все $ui$ и $vi.$ Рассмотрим

p−1 p−2 ai =rivi =uivi

— целое число.

aa a a ≡ rvp−1r vp−1r vp−1r vp−1 ≡ r r r r ≡ i i i+1 i+2i+3 p i i i+1i+1 i+2 i+2 i+3 i+3 p ii+1i+2i+3 p

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

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

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

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

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

Дано простое число $p ≥5.$ Для каждой перестановки $(x ,x ,...,x) 1 2 p$ чисел $1,2,...,p,$ в которой $x ⁄= i i$ для каждого $i≤p,$ посчитали остаток от деления числа $x1+2x2+ ...+ pxp$ на $p.$ Докажите, что перестановок, у которых этот остаток равен 1, столько же, сколько перестановок, у которых он равен $4.$

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

Подсказка 1

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

Подсказка 2

Рассмотрим перестановку дающую 1. Давайте запишем две строки. Первая - перестановка из условия, а вторая - числа от 1 до p. Тогда в задаче перемножили строки и сложили. Придумайте, как изменить сумму в 4 раза.

Подсказка 3

Давайте домножим все числа на 2. После чего первую строчку упорядочим, а вторую изменим как и первую, тогда сумма увеличится в 4 раза. Подумайте, почему новые числа удовлетворяют условию. Пока мы сделали в одну сторону, а как сделать в другую?

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

Нам будет удобнее думать, что $(x,x ,...,x ) 1 2 p$ — перестановка не чисел, а вычетов по модулю $p.$ Запишем каждую перестановку в виде двух строк, в каждой из которых расставлены все вычеты. При этом $xi$ — это вычет во второй строке, над которым в первой строке стоит $i.$ По условию мы рассматриваем только такие перестановки, в которых ни под одним вычетом $i$ не стоит он сам (для краткости назовём их хорошими). В каждой хорошей перестановке $(x1,x2,...,xp)$ умножим все вычеты в обеих строках на $2.$ При этом снова получится хорошая перестановка (так как при умножении на $2$ всех вычетов снова получаются все вычеты по этому модулю, и если $2i≡ 2j (mod p),$ то $i≡ j (mod p)),$ а выражение $x1+ 2x2+ ...+ pxp$ умножится на $4.$ Таким образом, мы установили соответствие между хорошими перестановками, у которых вычет этого выражения равен $1,$ и теми, у которых он равен $4.$ Поскольку для каждого вычета $i (mod p)$ существует вычет $j,$ для которого $2j ≡ i (mod p),$ наша операция обратима, а соответствие взаимно-однозначно, откуда и следует, что перестановок двух требуемых видов поровну.

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

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

Теорема Вильсона. Пусть $p$ — некоторое простое число. Докажите, что

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

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

Рассмотрим две такие ПрСВ: [1, 2, ..., $p− 1$ ] и [ $a$ , $2a$ , ..., $(p− 1)a$ ]. Заметим такой интересный факт, что во втором ПрСВ есть ровно одно число, которое дает остаток 1 при делении на $p$ , то есть существует ровно один такой остаток $b$ , что $ab ≡1$ (mod $m$ ). Остаток $b$ называют обратным к $a$ .

Давайте подумаем может ли так случиться, что $a= b$ , то есть $2 a ≡1$ (mod $m$ ). Если так произошло, то $2 a − 1= (a− 1)(a+1)$ делится на $p$ . Значит либо $a − 1$ , либо $a+ 1$ делится на $p$ , так как $p$ - простое. Тогда либо $a≡ 1$ , либо $a≡ −1≡ p− 1$ (mod $m$ ). (Тут важно, что $p$ — простое, так как если $p$ было бы равно 8, то $a$ могло бы быть равно 5)