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

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

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

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

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

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

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

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

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

Задача 1#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$

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

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

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

Задача 2#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

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

Задача 3#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

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

Задача 4#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)

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

Задача 5#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,$ таким образом, требуемое сравнение разрешимо.

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

Задача 6#84250

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

(a)

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

(b)

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

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

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

(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.$

Курсы

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

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

Задача 7#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)

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

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

Задача 8#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.$

Ответ:

Нельзя

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

Задача 9#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$ решения.

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

Задача 10#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 ,$ что и требовалось доказать.

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

Задача 11#91881

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

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

Если $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.$

Интенсивы

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

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

Задача 12#91882

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

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

По условию

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

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

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

Задача 13#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).$

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

Как обычно, мы будем заниматься только нечётными $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.$

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

Задача 14#91885

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

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

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

Задача 15#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 .$

Ответ:

Не может

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

Задача 16#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,$ но этого быть не может, пришли к противоречию.

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

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

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

Задача 17#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).$ Что и требовалось.

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

Задача 18#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)

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

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

Задача 19#104746

Пусть $a$ и $d$ — взаимно простые положительные целые числа, большие $1.$ Положим $x =1 1$ и, для $k≥ 1,$ $x = xk-, k+1 a$ если $x ..a, k .$ и $xk+ d$ иначе. Найдите наибольшее натуральное $n,$ для которого существует $k$ такое, что $.. n xk . a .$

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

Очевидно, что $x k$ взаимно просто с $d.$ По индукции и тому факту, что в последовательности может быть не более $a− 1$ последовательных возрастающих членов, также следует, что $xk < da,$ если $xk =xk−1+ d,$ и что $xk < d,$ если $xk−1 xk = a$ или $k =1.$ Это дает верхнюю оценку на показатель степени.

Это означает, что последовательность (в конечном итоге) периодическая, и что как возрастающие, так и убывающие шаги происходят бесконечно много раз. Пусть $−k a$ будет обратным остатком к $k a$ по модулю $d.$ Последовательность содержит элементы, сравнимые с $−1 −2 1,a ,a ,...$ по модулю $d.$

Пусть $xk0$ будет первым элементом таким, что $−n xk0 ≡ a (mod d).$ Мы имеем либо $k0 = 1,$ либо $xk0 = xk0−1∕a;$ в обоих случаях $n xk0 < d< a < da$ и, следовательно,

xk0 ∈ {an− d,an− 2d,...,an− (a− 1)d}

В этом множестве ни один из элементов не делится на $a,$ поэтому будет член последовательности равный $n a$ через $a − 1$ шаг.

Ответ:

$n$ такое, что $d< an < ad$

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

Задача 20#91883

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