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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Задача 1#104744

Пусть $P$ — нечётное, большее единицы число и $P =p p ...p 1 2 n$ — его разложение на простые множители (среди $p ,p ,...,p 1 2 n$ могут быть равные). Тогда для произвольного целого числа $a$ символ Якоби определяется равенством:

(a) (a)( a) ( a) P- = p1 p2 ...pn ,

где $( ) api$ — символы Лежандра. По определению считаем $( ) a1 = 1$ для всех $a.$ Докажите, обобщённый квадратичный закон взаимности: если $P,Q$ — взаимно простые нечётные числа, то

( ) ( ) Q- =(−1)(P−1)4(Q−1)⋅ P- P Q

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

Сначала проверим случай, когда одно из чисел $1.$ Пусть $P =1.$ Тогда $( Q)= 1, (-1)= 1, (− 1)0 = 1. 1 Q$ То есть действительно всё сходится.

Теперь пусть $P =p1p2...pn$ и $Q= q1q2 ...qk.$ Из взаимной простоты следует, что $pi ⁄= qj.$ Мультипликативность символа Якоби следует из определения и мультипликативности символа Лежандра: $(a1a2) (a2)(a1) P = P P .$ Тогда

( )( ) ∏n ( ) ∏n ( ) ∏n ∏k( )( ) Q- P- = Q- ⋅ pi = qj pi P Q i=1 pi i=1 Q i=1j=1 pi qj

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

(Q )( P) ∑n ∑k pi−1 qj−1- -P Q- = (− 1) i=1 j=1 2 2

Значениие степени $− 1$ зависит от чётности показателя, то есть нам нужно доказать, что

∑n k∑ pi−-1qj −-1≡ P-− 1Q-−-1 (mod 2) i=1j=1 2 2 2 2

Для нечётных $a, b$ заметим, что $a−21+ b−21≡ ab−21(mod 2)$ (можно явно проверить, рассмотрев остатки по модулю $4:$ при равных остатках с обеих сторон получится $0,$ при различных остатках — $1).$ Тогда заметим, что в сумме можно вынести $pi2−1$ за второй индекс суммирования:

∑n k∑ p − 1q − 1 ∑n p− 1∑k q − 1 ∑n p − 1Q − 1 -i2---j2--= i2--- -j2--≡ -i2----2-- (mod 2) i=1 j=1 i=1 j=1 i=1

из нашего тождества. Теперь общий множитель $Q−1 2$ можно тоже вынести:

∑n pi− 1 Q− 1 Q − 1∑n pi− 1 Q− 1P − 1 --2---2--= --2-- -2---≡ -2----2-- (mod p) i=1 i=1

снова по тождеству. То есть у нас получилось в точности то, что и требовалось доказать:

( ) ( ) Q- P- = (−1)(P−1)(4Q−1) P Q

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

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

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

Задача 2#108630

Пусть $p$ — простое число, а $m > 1,x >1,y > 1$ — натуральные числа. Оказалось, что

xp+yp- (x+-y)m 2 = 2

Докажите, что $m = p.$

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

Пока будем считать, что $p> 2.$ Пусть $q$ — простой общий делитель чисел $x$ и $y.$ Тогда $x = qa ⋅x 1$ и $y = qb⋅x 2$ ( $a≤ b).$ Теперь посмотрим на степень вхождения $q$ в нашем равенстве. Мы получаем, что $am = ap,$ а значит, $m =p.$

Следовательно, достаточно доказать задачу для $α (x,y)= 2 ,$ где $α≥ 0.$ Предположим, что $x +y$ имеет простой множитель $q >2.$ Тогда $x$ и $y$ по отдельности на $q$ не делятся. Тогда по лемме об уточнении показателя получаем

p p vq(x + y )= vq(x+ y)+vq(p)

поэтому $m = 1,$ что неверно. Пусть $(x,y) =2α,$ а значит, $x =2α ⋅x 1$ и $y =2β ⋅y 1$ ( $α ≤ β).$ Мы разобрали случай, когда у $x +y$ есть нечётный простой делитель, поэтому можно считать, что $α= β$ и $k x1+ y1 = 2.$ Следовательно, из нашего равенства мы получаем, что $p p s x1+ y1 = 2,$ где $s$ — какое-то число. Тогда мы знаем, что $p k p s x1+ (2 − x1)= 2 .$ После раскрытия скобок получаем, что степень вхождения двойки справа равна $k,$ а слева равна $s.$ Значит, $s= k.$ Так как $p> 1,$ то $p k p k x1 +(2 − x1) > 2,$ а значит, $x1 = 1,$ и аналогично $y1 = 1,$ то есть $x= y.$ Тогда из условия сразу следует, что $m = p.$

Если же $p =2,$ то мы получаем $2 2 x+ym x +y = ( 2 ).$ Заметим, что $3 2 2 (x +y) > 4(x + y)$ в силу того, что $x> 1$ и $y > 1.$ А значит, левая часть нашего равенства при $m > 2$ точно больше правой. То есть $m$ тоже равно двум.

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

Задача 3#108631

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

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

Предположим, что $c$ нечетное. Тогда правая часть делится на $p +3,$ откуда $p+3 =2k$ или $p+ 3= 2kpl.$

В первом случае получаем, что $p ≡5 (mod 8).$ Тогда $− 1$ является квадратичным вычетом по модулю $p,$ а $2$ — не является, откуда $− 2$ является квадратичным невычетом по модулю $p,$ но

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

откуда получаем противоречие.

Во втором случае получаем, что $p+ 3$ делится на $p,$ откуда $p= 3.$ Тогда имеем уравнение $c a b 5 +1= 2 3.$ Заметим, что $v2(5c+ 1)= 1,$ откуда $a= 1.$ По лемме об уточнении показателя получаем, что

v3(5c+ 1)=v3(6)+ v3(c)= 1+v3(c)

откуда $b−1 c≥ 3 .$ То есть $3b−1 b 5 < 2⋅3,$ что возможно только при $a= b= c= 1$ и $p =3.$

Разберем случай четного $c.$ Пусть $v2(c)=n,$ то есть $n c =2 ⋅m.$ Заметим, что $2n (p+ 2) + 1$ делит $c (p+ 2) + 1,$ откуда

n (p+ 2)2 +1= 2k⋅pl

Заметим, что $2n (p+2) + 1≡ 2 (mod 4)$ при $p> 2,$ откуда $k= 1.$ Тогда $2n b (p+2) − 1=2 ⋅(p − 1).$ Тогда

2n v2((p +2) − 1)= v2(p+ 1)+v2(p+3)+ v2(n)− 1

С другой стороны

v2(2 ⋅(pl− 1))= v2(p− 1)+ v2(p+ 1)+v2(l)

откуда

v2(p+3)+ n− 1= v2(p− 1)+v2(l)

Заметим, что $2n+1 2 ≡1 (mod p),$ а $2n 2 ⁄≡ 1 (mod p),$ откуда следует, что $v2(ordp2)= n,$ то есть $p− 1$ делится на $n+1 2 .$ Тогда $p ≡1 (mod 4).$ Посмотрим на наше равенство по модулю $p+ 1.$ Имеем $l 2≡ 2⋅(−1),$ откуда $l$ — четное. Тогда из только что полученного равенства на степени вхождения следует, что

v2(p+ 3)≥ 2+ v2(b)≥ 3

То есть число $p − 1$ не может делиться на $8.$ Значит, $n+ 1=2,$ откуда $n= 1.$ Тогда имеем уравнение

(p+ 2)2+ 1= 2pl

Заметим, что при $p> 5$

l 2 2 2p≥ 2p > (p+ 2) +1

Если $p= 3,$ то $26=2 ⋅3l$ — нет решений.

Если $p= 5,$ то $50=2 ⋅5l,$ откуда $l= 2.$

Вернемся к исходному уравнению

72m +1 =2a⋅5b

Посмотрев по модулю $4,$ получаем $a= 1.$ Далее $72m + 1= 5t⋅(72+1).$ Но по лемме об уточнении показателя

v5(72m +1)= v5(72+ 1)+v5(m )

откуда $m ⋅(72+ 1)≥72m+1,$ что не может быть правдой. Значит, $c= 2m =2,$ $a= 1,$ $b= 2,$ $p= 5.$

Ответ:

$(1,1,1,3),$ $(1,2,2,5)$

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

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

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

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

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

Задача 6#118946

Докажите, что для любого простого $p> 3$ существует бесконечно много натуральных $n$ таких, что $2n+ 3n +6n − 1$ делится на $p.$

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

По малой теореме Ферма: если $a⁄≡ 0⇒ ap−1 ≡ 1. p p$ Тогда $2n+p−1 ≡ 2n,3n+p−1 ≡ 3n,6n+p−1 ≡ 6n, p p p$ то есть

n n n n+p−1 n+p− 1 n+p−1 2 +3 + 6 − 1≡p 2 + 3 +6 − 1

значит, надо найти одно $n$ такое, что $2n+ 3n +6n − 1≡p 0.$

Рассмотрим $n= −1,$ пусть оно и ненатуральное, последующие будут натуральными:

−1 −1 −1 3+-2+1- 2 + 3 +6 − 1≡p 6 − 1≡p 0

Курсы

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

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

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

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

Задача 8#119614

Для каждого натурального $n$ определим число $φ(n),$ равное количеству целых чисел $m,1 ≤m ≤ n$ взаимно простых с $n.$ Найти $φ(1947).$

Источники: Росатом - 2025, 11.3 (см. olymp.mephi.ru)

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

Пусть $n =pr1⋅pr2 ⋅pr3, 1 2 3$ где $p,p ,p 1 2 3$ — различные простые числа, $r ,r ,r 1 2 3$ — их (натуральные) кратности. Количество чисел, не больших $n,$ делящихся на $p1 :$

r1−1 r2 r3 n1 = p1 ⋅p2 ⋅p3

Количество чисел, не больших $n,$ делящихся на $p : 2$

r1 r2−1 r3 n2 = p1 ⋅p2 ⋅p3

Количество чисел, не больших $n,$ делящихся на $p3 :$

r1 r2 r3−1 n3 = p1 ⋅p2 ⋅p3

Количество чисел, не больших $n,$ делящихся на $p1⋅p2 :$

n = pr1−1⋅pr2−1⋅pr3 4 1 2 3

Количество чисел, не больших $n,$ делящихся на $p1⋅p3 :$

n5 = pr11−1⋅pr22⋅pr33−1

Количество чисел, не больших $n,$ делящихся на $p2⋅p3$

n6 = pr11 ⋅pr22−1⋅pr33−1

И наконец, количество чисел, делящихся на $p1⋅p2⋅p3 :$

n7 = pr11−1 ⋅pr22−1⋅pr33−1

Общее количество чисел, не взаимно простых с $n,$ по формуле включений-исключений равно

n1+ n2+n3 − n4− n5− n6+n7 =pr11−1⋅pr22−1⋅pr33−1(p1⋅p2+ p1⋅p3+p2⋅p3− p1− p2− p3+ 1)

Тогда

φ(n)= n− n1− n2 − n3+ n4+ n5+n6 − n7 =

= pr1−1⋅pr2−1⋅pr3−1(p ⋅p ⋅p − p ⋅p − p ⋅p − p ⋅p +p + p +p − 1)= 1 2 3 1 2 3 1 2 1 3 2 3 1 2 3

= pr1−1⋅pr2−1⋅pr3−1(p1− 1)(p2− 1)(p3− 1) 1 2 3

Таким образом, при $n =1947= 3⋅11 ⋅59$ имеем

φ(1947)= (3− 1)(11− 1)(59− 1)= 1160

Ответ:

1160

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

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

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

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

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

Задача 11#82679

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

Интенсивы

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

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

Задача 12#83138

Малая теорема Ферма. Для любого простого $p$ и взаимно простого с $p$ числа $a$ верно, что $ap−1 ≡ 1$ (mod $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,$ чтд.

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

Задача 13#83156

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

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

Будем воспринимать наши числа $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 .$

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

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

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

Задача 15#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,$ тем самым получено противоречие.

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

Задача 16#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 512s − 1 = s+ 21.$ Значит, показатель в самом деле равен $2n−2.$

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

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

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

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

Задача 17#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$ (очевидно, нечётное), должно быть степенью двойки, то есть равняться единице.

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

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

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

Задача 19#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.$ С другой стороны,