Остатки и сравнения по модулю —Каталог задач по Олимпиадной математике

Главная
Каталог задач
Каталог заданий по Олимпиады - Математика
Остатки и сравнения по модулю

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

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

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

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

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

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

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

Считаем остатки

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

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

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

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

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

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

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

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

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

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

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

Задача 1#85917

Дано натуральное $n >1.$ Докажите, что существуют $n$ натуральных чисел таких, что произведение любых $n− 1$ из них даёт остаток $1$ при делении на оставшееся число.

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

Положим $a = 2,a = 3,a =a a ...a + 1 1 2 k 1 2 k−1$ при $3 ≤k <n$ и, наконец, $a = aa ...a − 1. n 12 n−1$ Тогда $aa ...a ≡1 (mod a ) 12 n−1 n$ очевидным образом. Рассмотрим члены нашей последовательности по модулю $ak$ при $k< n.$ Если $k< j < n,$ имеем $aj ≡ 1 (mod ak),$ а $an ≡− 1 (mod ak).$ Поэтому

a1a2...ak−1ak+1...an ≡ −a1a2...ak− 1 ≡ −(− 1) ≡1 (mod ak)

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

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

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

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

Задача 2#85436

Даны простое число $p$ и три различных натуральных числа $a,b$ и $c$ таких, что $ab+ 3,bc+ 3,ac+ 3$ и $abc+ 11$ делятся на $p.$ Чему может быть равно $p?$

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

Давайте запишем условия на делимость в виде сравнений:

ab≡ −3 (mod p)

bc≡ −3 (mod p)

ac≡ −3 (mod p)

abc≡ −11 (mod p)

Теперь мы можем перемножить первые три сравнения и получить, что $(abc)2 ≡ −27 (mod p).$ Но из условия $(abc)2 ≡ 121 (mod p).$ Значит, $p$ является делителем числа $121 − (−27)= 148= 22⋅37,$ и может быть равен либо $2,$ либо $37.$ Для $p= 2$ можно взять просто три нечётных числа $a,b,c.$ А для $p =37$ существуют числа $a= 16,b= 16+37,c= 16 +37⋅2.$ Действительно, легко проверить, что все сравнения выполняются, потому что по модулю $37$ они равны $16,$ а $. 163+ 11 ..37.$

Ответ:

$p =2,p= 37$

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

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

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

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

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

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

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

Курсы

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

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

Задача 7#84250

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

1 1 1 1+ 22 + 32 + ...+ (p− 1)2

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

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

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

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

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

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

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

Покажем, что элементы образуют полную систему вычетов по модулю $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$ натуральных чисел имеем

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

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

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

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

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

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

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

Задача 10#83962

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

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

При $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$ равно $2.$

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

Ответ:

$2$ или $3$

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

Задача 11#83961

Пусть $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)$ – натуральное число. Это невозможно, поэтому мы достигли противоречия.

Интенсивы

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

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

Задача 12#83960

Известно, что при всех натуральных $n$ число $4(an+ 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$ (очевидно, нечётное), должно быть степенью двойки, то есть равняться единице.

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

Задача 13#83959

Докажите, что для любого натурального $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(52s− 1)=s+ 21.$ Значит, показатель в самом деле равен $2n−2.$

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

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

Задача 14#83958

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

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

Предположим противное. Пусть искомое число $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,$ тем самым получено противоречие.

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

Задача 15#83957

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

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

При $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$

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

Задача 16#82679

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

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

Из признака делимости на $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$ по китайской теореме об остатках.

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

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

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

Задача 17#78919

Даны взаимно простые числа $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 .$

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

Задача 18#76655

Сумма всех натуральных делителей числа $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-$

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

Задача 19#82097

Найдите все такие натуральные $n,$ что $2n+-1 n2$ целое.

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

Пусть $p$ — наименьший простой делитель числа $n.$ Тогда $p ≥3$ и $2n ≡ −1 (mod p).$ Получаем, что $22n ≡ 1 (mod p).$ Обозначим через $T$ показатель числа 2 по модулю $p.$ Тогда $T |q− 1$ и $T |2n.$ Значит, $T < q$ и потому либо $T = 1,$ либо $T = 2$ (иначе в $T$ найдется простой делитель $n,$ меньший $p$ ). При $T =1$ получаем, что $2≡ 1 (mod p)$ — противоречие. Поэтому $T = 2$ и $2 2 ≡ 1 (mod p).$ Значит, $p =3.$

Теперь применим LTE:

1+v3(n)=v3(2+1)+ v3(n)= v3(2n− (− 1)n)≥ v3(n2)= 2v3(n)

откуда следует, что $v3(n)= 1.$

Пусть $n = 3m.$ Если $m = 1,$ то $n= 3$ — ответ. В противном случае $m > 3$ — нечетно, и пусть $q$ — наименьший простой делитель $m.$ Тогда $q > 3.$ Получаем: $3m 2 ≡− 1 (mod q)$ и $6m 2 ≡ 1 (mod$ ) $q.$ Пусть $t$ — порядок двойки по модулю $q.$ Тогда $t|q− 1$ и $t|6m.$ Ho $t< q,$ поэтому $(t,m )= 1,$ значит, $t|6.$ Если $t =3,$ то $3m 2 ≡1 (mod q)$ — противоречие. При $t= 1$ получаем, что $2 ≡1 (mod q)$ — противоречие. Если $t= 2,$ то $2 2 ≡ 1 (mod q)$ и $q = 3$ — противоречие. Значит, $t= 6.$ Тогда $6 2 ≡ 1 (mod q)$ и $q = 7.$

Получаем, что $n 7|2 + 1.$ Однако, перебрав все остатки $n$ по модулю $6,$ легко убедиться, что это невозможно. Таким образом, мы получаем противоречие.

Ответ:

$n =3$

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

Задача 20#82096

На доске написаны $n$ цифр в ряд. Докажите, что к ним можно приписать несколько цифр слева и не более $n$ цифр справа так, чтобы получилась степень двойки.

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

Рассмотрим остатки степеней двойки по модулю $102n = 22n ⋅52n.$ Покажем,что двойка — первообразный корень по модулю $5s.$ Заметим, что $k ..s 2 − 1 .5 ,$ только если $.. k.4$ (проверка остатков степеней $2$ по модулю $5$ ). Пусть $k= 4a.$ Теперь по LTE $4a a v5(2 − 1)=v5(16 − 1)= v5(16− 1)+ v5(a).$ То есть $v5(a)≥s − 1,$ откуда $s−1 a≥ 5$ и $s− 1 s k≥ 4⋅5 (равно φ(5 )).$ Таким образом, двойка — действительно первообразный корень по этому модулю. Следовательно, по модулю $2n 5$ степени двойки дают $2n φ(5 )$ различных остатков — в точности те, что взаимно просты с $5$ (так как степень двойки не кратна пяти). Значит, существуют степени двойки, сравнимые по модулю $2k 5$ с $1,2,3,4,6....$ То есть существуют степени двойки, сравнимые по модулю $2k 10$ с $2n 2n 2n 2n 2n 1⋅2 ,2 ⋅2 ,3⋅2 ,4⋅2 ,6⋅2 ...$ (домножаем все предыдущие степени и их остатки на $2n 2 ,$ это можно сделать, поскольку $2n 2$ и $2n 5$ взаимно просты). Заметим теперь, что каждый следующий остаток отличается от предыдущего не более чем на $2n n 2⋅2 <10 .$ Значит, на каждом шаге $(n+ 1)$ -ая с конца цифра соответствующей степени двойки увеличивается не более, чем на $1,$ а отсюда следует, что такими шагами мы получим на местах с $n+ 1$ по $2n$ любую комбинацию цифр. Собственно, выберем степень двойки, на которой мы получили данную комбинацию - она и будет искомой, которая получается дописыванием цифр.

Предыдущий раздел

Следующий раздел