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

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

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

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

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

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

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

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

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

Задача 1#84248

Пусть $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)

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

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

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

Задача 2#84249

Натуральные числа $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,$ таким образом, требуемое сравнение разрешимо.

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

Задача 3#84250

Пусть $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.$

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

Задача 4#84251

Пусть $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)

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

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

Задача 5#84252

На доске написаны числа $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.$

Ответ:

Нельзя

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

Задача 6#84254

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

2 2 x +y ≡ 1 (mod p)

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

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

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$ решения.

Курсы

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

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

Задача 7#84255

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

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

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

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

Первое решение. Введём обозначение $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 ,$ что и требовалось доказать.

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

Задача 8#91881

Для простых чисел $p⁄= q$ нашлись натуральные числа $a$ и $b$ такие, что $ap− bp$ делится на $q.$ Докажите, что $a− b$ делится на $q$ или $q− 1$ делится на $p.$

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

Подсказка 1

Условие a-b кратно q понятное, а вот q-1 делится на p - нет. Подумайте о том, где такое встречается.

Подсказка 2

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

Подсказка 3

Поделите на b^p. Вы получите, что (a/b)^p сравнимо с 1. Выведите отсюда решение, поймите, где вылазит a-b кратно q.

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

Если $b ≡ 0, q$ то и $a≡ 0, q$ тогда $a− b$ делится на $q.$ Теперь $b$ не делится на $q$ и $a≡ b. q$

p p (a)p a ≡q b ⇐ ⇒ b ≡q 1

значит, $q − 1$ делится на $p.$

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

Задача 9#91882

Пусть $a,b,x,y$ и $n$ — натуральные числа. Известно, что каждое из чисел $ax− 1,by− 1$ и $x+y − 1$ делится на $n.$ Докажите, что число $ab− a− b$ также делится на $n.$

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

Подсказка 1

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

Подсказка 2

Перепишите условие и вопрос на языке сравнений. Как подступиться к ab-a-b?

Подсказка 3

Выразите a и b через x и y, подставьте в вопрос задачи. Как воспользоваться третьим условием?

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

По условию

1 ax ≡n 1 ⇐ ⇒ a≡n x

Аналогично $1 b≡n y.$ Тогда

1 1 1 1 − x− y ab− a − b≡n xy − x − y ≡n-xy- ≡n 0

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

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

Задача 10#91884

Последовательность ${a} n$ определена условиями $a = 1,a = 2 0 1$ и при всех натуральных $n ≥2$ верно $a =a2 + (aa ...a )2. n n−1 0 1 n−2$ Простое число $p$ — делитель $ak.$ Докажите, что $p >4(k− 1).$

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

Подсказка 1

Утверждение задачи можно переформулировать так: если при k≤ [p∕4]+1 число a_k не кратно p, то не кратны p и все последующие члены последовательности. В такой формулировке удобнее работать со сравнениями. Подумайте, что такое [p∕4]+1.

Подсказка 2

[p∕4]+1 это число похоже на то, что мы какие-то числа разбиваем на четверки. Рассмотрим следующее разбиение остатков на группы. В одной группе окажутся остатки x, y, p-x, p-y, где xy-1 кратно p. Групп ровно столько, сколько нужно. Предположим, что нуля среди остатков не оказалось, значит, есть какие-то 2 остатка из одной группы. Поймите, почему это означает, что нулевой остаток не встретится.

Подсказка 3

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

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

Как обычно, мы будем заниматься только нечётными $p.$ Утверждение задачи можно переформулировать так: если при $k≤ [p∕4]+1$ число $ak$ не кратно $p,$ то не кратны $p$ и все последующие члены последовательности. Положим $m = [p∕4]+ 1.$ Пусть ни одно из чисел $a0,a1,...,am$ не делится на $p.$ Тогда для каждого $i$ такого, что $ai$ не кратно $p,$ в частности, для всех $i≤ m$ существует число $xi < p$ такое, что $ai ≡ a0a1 ...ai−1xi (mod p).$ Кроме того, положим $x0 = 1.$

Каждому ненулевому остатку $x$ при делении на $p$ сопоставим обратный остаток $y$ такой, что $xy− 1$ кратно $p$ (легко видеть, что разным $x$ соответствуют разные $y).$ Объединим в одну группу остатки $x,y,p − x$ и $p− y$ (очевидно, для остатков $y,p− x$ и $p− y$ получится та же самая группа). Ясно, что остаток $x$ не может совпадать с $p− x.$ Есть единственная группа, в которой $x$ совпадает с $y$ (так как если $2 x − 1$ кратно $p,$ то на $p$ делится $x− 1$ или $x+ 1)$ и не более одной группы, в которой $x$ совпадает с $p− y$ (так как не более чем для двух $x$ число $2 x + 1$ кратно $p).$ Во всех остальных группах по четыре разных остатка. Таким образом, общее количество групп, на которые мы разбили ненулевые остатки при делении на $p,$ не превосходит $[p∕4]+1 =m.$ Это значит, что среди чисел $x0,x1,...,xm$ есть два, попавших в одну группу.

Докажем, что если два остатка $xk$ и $xl$ попали в одну группу, то $xk+1$ и $xl+1$ тоже в одной группе. Действительно, если $yk$ — остаток, обратный к $xk,$ то $xk+1 ≡ xk+ yk (mod p)$ (поскольку $a0,a1,...,ak$ не кратны $p,$ для проверки этого утверждения можно умножить его на $xk,$ получив $xkxk+1 ≡ x2k+1 (mod p),$ а затем на $(a0a1...ak−1)2,$ получив $ak ≡ a2k+ (a0a1...ak−1)2 (mod p)).$ Понятно, что при замене $xk$ на обратный остаток $xk+1$ не меняется, а при замене на $p− xk$ — меняется на $p− xk+1.$

Таким образом, если среди $x0,x1,...,xm$ нет $0,$ то их нет и среди всех дальнейших $xi$ и, следовательно, никакие $ai$ не кратны $p.$

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

Задача 11#91885

Докажите, что для каждого простого $p$ числа от $1$ до $p− 1$ можно выписать в ряд $a,a ,...,a 1 2 p−1$ так, что все произведения $a1a2...ak$ различны по модулю $p.$

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

Подсказка 1

Строить произвольный пример тяжело. Было бы здорово, если бы он был красивым. Что вам приходит в голову?

Подсказка 2

Решаем на языке сравнений. Сделайте так чтобы произведения последовательно равнялись числам 1, 2, … p-1.

Подсказка 3

Из примера можно посчитать любое a_i. Поймите, что все они различные числа по модулю p.

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

Рассмотрим $a = 1,a = 2,a = 3,...,a = p−1. 1 2 1 3 2 p−1 p−2$ Заметим, что $a a ...a = k, 1 2 k$ значит, все остатки по модулю $p$ встретятся. Осталось понять, что все $ai$ различны. Пусть это не так, тогда

i j i j 1 1 ai ≡p aj ⇐⇒ i− 1-≡p j− 1-⇐ ⇒ i−-1 − 1≡p j−-1 − 1 ⇐ ⇒ i−-1-≡pj−-1 ⇐⇒ i≡p j

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

Интенсивы

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

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

Задача 12#84253

В строку выписаны $200$ натуральных чисел. Среди любых двух соседних чисел строки правое либо в $9$ раз больше левого, либо в $2$ раза меньше левого. Может ли сумма всех этих $200$ чисел равняться $2022 24 ?$

Источники: Всеросс., 2022, ЗЭ, 9.3(см. olympiads.mccme.ru)

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

Пусть строка состоит из чисел $a,a ,...,a 1 2 200$ в этом порядке. Если число $a = 2k i$ чётно, то следующим за ним может быть число $k$ или число $18k;$ эти числа дают одинаковые остатки при делении на $17.$ Если же $ai$ нечётно, то $ai+1 = 9ai.$ В любом случае получаем, что $ai ≡ 2ai+1 (mod17).$

Таким образом, полагая $a =a200,$ получаем, что с точки зрения остатков при делении на $17$ строка устроена так же, как и строка $199 198 2 a,2 a,...,2a,a.$ Сумма всех членов этой новой строки равна $(200 ) 2 − 1a.$ В частности, она делится на $8 2 − 1= 15⋅17,$ то есть делится на $17.$ Поэтому и сумма чисел в исходной строке делится на $17,$ и она не может равняться $2022 24 .$

Ответ:

Не может

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

Задача 13#90980

Докажите, что если $(n − 1)!≡− 1 (mod n),$ то число $n$ — простое.

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

Предположим, что нашлось составное $n,$ для которого справедливо сравнение из условия. Ясно, что его можно представить в виде $n= ab,$ где $1< a≤ b< n.$ Заметим, что множители $a$ и $b$ входят в $(n− 1)!.$ В таком случае если $(n− 1)!+ 1$ кратно $n,$ то тогда $1$ должна делиться на $a$ и $b,$ но этого быть не может, пришли к противоречию.

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

Задача 14#90981

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

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

Ясно, что

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

2 ≡−(p− 2) (mod p)

...

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

С помощью этого проделаем следующую цепочку сравнений:

(( ))2 ( ) ( ) p−-1 ! ≡ p−-1 !⋅(−(p− 1))⋅(−(p− 2))⋅...⋅ − p-+1 ≡ (p− 1)!⋅(−1)p−21 (mod p) 2 2 2

Заметим, что число $p−1 2$ чётно, поскольку $p ≡1 (mod 4).$ Теперь завершим цепочку сравнений: $(p− 1)!⋅(−1)p−21≡ (p− 1)!≡− 1 (mod p).$ Что и требовалось.

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

Задача 15#90982

Пусть числа $p$ и $p+ 2$ являются простыми числами-близнецами. Докажите, что справедливо $4((p − 1)!+ 1)+ p$ делится на $2 p + 2p.$

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

Делимость на $p$ очевидна, поскольку первое слагаемое делится на $p$ по теореме Вильсона, а второе равно $p.$ Докажем делимость на $p+ 2.$ Домножим число на $p(p+ 1)$ (это никак не поможет ему поделиться на $p+ 2$ ) и найдём его остаток при делении на $p+ 2:$

2 2 2 4((p +1)!+ p(p +1))+p (p+1)≡ 4(− 1− p)− p = −(p+2) ≡ 0 (mod p +2)

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

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

Задача 16#91883

Докажите, что для любого натурального $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

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

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

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

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

Задача 17#91886

Дано простое число $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),$ наша операция обратима, а соответствие взаимно-однозначно, откуда и следует, что перестановок двух требуемых видов поровну.

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

Задача 18#83140

Теорема Вильсона. Пусть $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)