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

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

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

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

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

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

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

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

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

Задача 1#108630

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

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

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

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

Подсказка 1

Для начала попробуйте разобрать случай, когда у чисел x и y есть общий простой нечетный делитель.

Подсказка 2

Если у x и y есть общий простой нечётный делительно, то достаточно посмотреть на его степень вхождения в обоих частях нашего равенства. Теперь пусть у x + y есть нечетный простой делитель q. Что тогда можно сказать про степени вхождения q в нашем равенстве (давайте пока считать, что p > 2)?

Подсказка 3

Для этого достаточно выяснить, как вычислить степень вхождения q в x^p + y^p. Что же может нам помочь в этом?

Подсказка 4

Правильно, лемма об уточнении показателя! Применив ее, легко получить, что m может быть только 1. Теперь можно считать, что x + y вообще не имеет нечётных простых делителей. То есть x + y является степенью двойки. Из нашего равенства также будет следовать, что x^p + y^p тоже степень двойки. Попробуйте осознать, что это бывает довольно редко.

Подсказка 5

Не забудьте рассмотреть случай p = 2. Чтоб разобрать этот случай достаточно на самом деле понять, что при m > 2 правая часть точно больше левой.

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

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

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

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

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

Задача 2#108631

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

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

Подсказка 1

В случае нечетного c правая часть делится на p+3, а тогда оно является степенью двойки или произведением степени двойки и числа p. Предположим, что это степень двойки. Какие числа тогда заведомо являются вычетами или невычетами по модулю p?

Подсказка 2

Верно! -1 является вычетом, а 2 — невычетом. Тогда -2 — невычет. Возможно ли такое?

Подсказка 3

Конечно же, нет! Пусть теперь p+3 - это произведение степени двойки и p. Легко видеть, что p = 3. Можно ли найти теперь степень вхождения 3 в правую часть?

Подсказка 4

Верно! По лемме об уточнении показателя степень вхождения 3 в правую часть равна степени вхождения 3 в c, увеличенной на 1. Следовательно, с не меньше, чем (b-1)-я степень числа 3. При каких a, b, c это возможно?

Подсказка 5

Остается случай четного c. Обозначим степень вхождения 2 в c через n. Заметим, что если в правой части заменить c на n-ю степень 2, то получится делитель правой части. Тогда мы знаем разложение этой правой части с заменой c на n-ю степень 2 на простые множители. Какие выводы напрашиваются?

Подсказка 6

Верно! Мы видим, что при p > 2 можно применять LTE-лемму по модулю 2! Тогда можно получить уравнение на степени вхождения 2, а что из него следует?

Подсказка 7

Точно! Из этого уравнения легко получается, что степень вхождения 2 в показатель 2 по модулю p равна n+1. Тогда p-1 делится на (n+1)-ю степень 2. Кроме того, можно заметить, что степень вхождения p в левую часть с заменой c на n-ю степень двойки четна. Как тогда можно оценить степень вхождения 2 в b из имеющихся условий?

Подсказка 8

Конечно! Степень вхождения 2 в b, увеличенная на 2, не меньше 3 и не больше степени вхождения 2 в p+3. Отсюда получаем, что p-1 не делится на 8. Какое тогда получается уравнение из исходного?

Подсказка 9

Верно! Мы получаем n = 2 и после подстановки легко видеть, что при p > 5 решений нет (одна из частей уравнения точно больше другой). Остается разобраться со случаями p = 3 и p = 5!

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

Предположим, что $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)$

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

Задача 3#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$ по китайской теореме об остатках.

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

Задача 4#83957

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

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

Подсказка 1

Предположим, что p нечетно. Так как 3 + 4 = 7, удобно использовать LTE-лемму для модуля 7. Какой вывод из нее можно сделать?

Подсказка 2

Точно! Если p отлично от 7, то левая часть делится на 7, но не делится на 49, откуда n = 1. А что получается при p = 7?

Подсказка 3

Верно! Для p = 7 получаем, что левая часть делится на 49, но не делится на 343. Можно ли теперь оценить n сверху?

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

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

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

Задача 5#83958

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

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

Подсказка 1

Предположим, что такое a существует. Тогда, как легко видеть, разница квадрата числа a и 1 делится на 12. А как связаны степени вхождения 2 и 3 в разность квадрата a и 1 и в разность 2022-ой степени a и 1?

Подсказка 2

Верно! Они совпадают. Попробуем теперь изучить именно a²-1. На какую минимальную степень 2 и 3 оно должно делиться?

Подсказка 3

Конечно! Произведение 50 последовательных чисел делится на 50!, а по теореме Лежандра степень вхождения 2 в это число больше 40. Аналогично, степень вхождения 3 больше 20. Как теперь получить противоречие?

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

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

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

Задача 6#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$ тоже пробегают.

Курсы

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

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

Задача 7#83960

Известно, что при всех натуральных $n$ число $4(an+ 1)$ является точным кубом. Докажите, что $a =1.$

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

Подсказка 1

Попробуем выбрать n нечетным и простое p > 2. Что можно сказать о степени вхождения p в наш куб?

Подсказка 2

Конечно! По LTE-лемме она равна сумме степеней вхождения p в a+1 и в n. Как показать, что тогда число кубом не является?

Подсказка 3

Верно! При n = p или n = p² степень вхождения p в наше число на 3 не делится, и кубом оно не является. Тогда легко видеть, что a+1 и a³+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$ (очевидно, нечётное), должно быть степенью двойки, то есть равняться единице.

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

Задача 8#83962

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

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

Подсказка 1

Очевидно, что p нечетно. Из формулы суммы геометрической прогрессии легко видеть, что a четно. А на какую степень двойки может делиться p-1?

Подсказка 2

Верно! Исходя из LTE-леммы, p-1 делится на 2, но не делится на 4. Тогда p имеет остаток 3 при делении на 4, а его квадрат остаток 1. Тогда по LTE-лемме числитель нашей дроби делится на 4. Какова степень вхождения 2 в левую часть данного уравнения?

Подсказка 3

Верно! Она равна разности суммы степеней вхождений 2 в p+1, a и 1. Степени вхождения из нашего выражения не превосходят логарифма от соответствующих чисел! Тогда наша дробь не превосходит (p+1)a/2. Как теперь получить противоречия?

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

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

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

Ответ:

$3$ или $4$

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

Задача 9#82093

Найдите степень вхождения $1991$ в

19911992 19911990 1990 +1992

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

Запишем выражение в виде $(199019911992 + 1)+(199219911990 − 1).$ Пусть $p$ — некоторый простой делитель $1991,$ тогда по $LTE$ имеем:

19911992 19911992 1992 vp(1990 + 1)=vp(1990 − (−1))=vp(1991)+ vp(1991 )= 1993⋅vp(1991)

19911990 1990 vp(1992 − 1)= vp(1991)+ vp(1991 )= 1991⋅vp(1991)

Следовательно, степень вхождения $p$ во всё выражение равна $1991⋅vp(1991)$ для каждого простого делителя $p.$ Получается, что степень вхождения $1991$ равна $1991.$

Ответ:

$1991$

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

Задача 10#82094

Решите в натуральных числах уравнение

2009 2009 z x + y = 7

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

Предположим, что $x+ y$ не делится на $7.$ В таком случае $x+y =1,$ потому что $7z = x2009+ y2009$ кратно $x+ y.$ Но $x+ y > 1,$ потому что $x$ и $y$ натуральные. Следовательно, $x +y$ кратно $7.$ Предположим, что $v7(x)= k,$ то $2009 v7(x )=2009k.$ Ясно, что $z >2009k,$ иначе левая часть больше правой. Если $v7(y)> k,$ то $2009 v7(y )> 2009k.$ Таким образом, степень вхождения $7$ в левую часть равна $2009k,$ то есть меньше, чем степень вхождения $7$ в правую часть, противоречие. То есть $v7(y)=k.$ Сократим равенство на $2009k 7 ,$ получим уравнение $2009 2009 z1 x1 + y1 = 7 .$

Итак, теперь $x1$ и $y1$ не делятся на $7,$ а $x1 +y1$ — делится (доказывается так же, как мы это делали в начале). Тогда по $LT E$ имеем:

v7(x21009+ y12009) =v7(x21009 − (−y1)2009)= v7(x1+ y1)+ v7(2009)=v7(x1 +y1)+2

С другой стороны, она равна $z1.$ Отсюда получаем $v7(x1+ y1)=z1− 2.$ Учитывая, что $x1+ y1$ ни на что кроме $7$ не делится, $z1−2 x1+ y1 = 7 .$

Таким образом, $x21009+y21009- x1+y1 = 49,$ то есть $2009 2009 x1 + y1 = 49(x1+ y1).$ Пусть, не умаляя общности, $x1 ≥ y1,$ тогда $2009 2009 2009 49(x1 +y1)≤98x1 < x1 < x1 + y1$ при $x1 ≥ 2.$ Значит, $x =y =1,$ но этот случай не подходит.

Ответ:

Нет решений

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

Задача 11#82095

Решите в натуральных числах уравнение $3x =2xy+ 1.$

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

Подсказка 1

Легко видеть, что при нечетном x решение возможно только для x = 1. Пусть x четно. Что получится, если применить LTE-лемму по модулю 2?

Подсказка 2

Пусть x = 2k. Тогда мы, перенеся 1 влево, получим, что степень вхождения 2 в разность k-ой степени 9 и 1 в точности равна степени вхождения 2 в k, увеличенной на 3. Какое условие тогда нужно наложить, чтобы решение вообще могло существовать?

Подсказка 3

Верно! Необходимо, чтобы выполнялось неравенство 2k < k + 3 (из соображений степеней вхождения 2). Как теперь завершить решение?

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

Преобразуем к виду $3x− 1 =2xy.$ Пусть $x$ нечётен. Тогда $3x− 1$ не делится на $4,$ откуда $x =1$ и $y = 1.$ Теперь рассмотрим случай, когда $x= 2k.$ Заметим, что $x k 3 − 1= 9 − 1.$ Применим здесь LTE по модулю $2.$

k v2(9 − 1)= v2(9 − 1)+ v2(k)

Сделаем грубую оценку: $v2(k)< k,$ откуда $v2(9k− 1)< k+ 3.$ Таким образом, решения имеются только тогда, когда $2k< k+ 3$ — иначе двойка входит в левую часть в меньшей степени, чем в правую, и равенство недостижимо. Значит, $k <3,$ откуда $x= 2$ или $x =4.$ Простой подстановкой получаем, что в первом случае $y = 2,$ во втором случае $y =5.$

Ответ:

$(2;2),(4;5),(1;1)$

Интенсивы

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

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

Задача 12#82096

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

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

Рассмотрим остатки степеней двойки по модулю $102n = 22n ⋅52n.$ Покажем,что двойка — первообразный корень по модулю $s 5 .$ Заметим, что $k 2 − 1$ делится на $s 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$ с

1⋅22n,2⋅22n,3⋅22n,4 ⋅22n,6⋅22n...

(домножаем все предыдущие степени и их остатки на $2n 2 ,$ это можно сделать, поскольку $2n 2$ и $2n 5$ взаимно просты).

Заметим теперь, что каждый следующий остаток отличается от предыдущего не более чем на $2n n 2 ⋅2 < 10 .$ Значит, на каждом шаге $(n+ 1)$ -ая с конца цифра соответствующей степени двойки увеличивается не более, чем на $1,$ а отсюда следует, что такими шагами мы получим на местах с $n+ 1$ по $2n$ любую комбинацию цифр. Собственно, выберем степень двойки, на которой мы получили данную комбинацию — она и будет искомой, которая получается дописыванием цифр.

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

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

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

Задача 14#83177

На какую максимальную степень пятерки делится выражение $310000− 210000$ ?

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

Первое решение.

10000 10000 5000 5000 v5(3 − 2 )=v5(9 − 4 )= vp(9− 4)+vp(5000)= 5

Второе решение.

10000 10000 10000 10000 v5(3 − 2 )= v5(3 − (−2) )= vp(3− (−2))+ vp(10000)= 5

Замечание.

$v5(310000 − 210000)=(по LTE)= v5(3 − 2)+ v5(10000)= 4$ — неверное рассуждение

Ответ: 5

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

Задача 15#83176

Лемма об уточнении показателя, ЛоУП, lifting the exponent lemma, LTE.

Пусть $a$ и $b$ — различные целые числа, $k$ — натуральное число, а $p$ — нечетное простое число, НЕ ДЕЛЯЩЕЕ $a$ и $b$ .

ЕСЛИ $a− b$ делится на $p$ , то

k k vp(a − b )= vp(a− b)+ vp(k)

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

Будем вести индукцию по $v (k) p$ .

(a) Докажите базу для $vp(k)=0$ .

Решение. Заметим, что $k k k−1 k−2 k−1 a − b = (a− b)(a +a b+ ...+ b )$ . Поскольку
$a ≡b( mod p)$ , правая скобка по модулю $p$ сравнима с $k−1 ka$ , что, очевидно, не кратно $p$ .

(b) Докажите, пожалуйста, базу и для $vp(k) =1$ . Это пригодится в дальнейшем.

Решение. Докажем для $k =p$ . Аналогично предыдущему пункту, заметим, что

ap− bp = (a − b)(ap−1+ ap−2b+ ...+ bp−1)

Поскольку $a≡ b( mod p)$ , правая скобка по модулю $p$ сравнима с $p−1 pa$ , то есть делится на $p$ . Теперь остаётся доказать, что она не делится на $2 p$ . Будем действовать так: заметим, что если $a ≡b( mod p)$ , то $b= a+ np$ . Подставим это выражение вместо $b$ в скобку, получим следующее выражение: $p−1 p−2 p−1 (a + a (a+ np)...+ (a+ np) )$ . Если записывать его как многочлен от $p$ , оно примет вид

pap−1+ ap−2⋅np⋅1+ ap−2⋅np⋅2+...ap−2⋅np⋅(p− 1)+ p2⋅...

раскрываем каждую скобочку по биному Ньютона и смотрим на свободные члены и члены первой степени - очевидно, остальные делятся на $2 p$ , и влиять на наше утверждение не будут

p−1 p−2 p(p−-1) ≡pa + a np 2

складываем все члены с $p$ и замечаем, что $p$ нечётно, а значит, эта сумма делится на $2 p$

p−1 2 ≡ pa ( mod p )

Решение. Пусть $k= pα⋅t$ $(t не кратно p)$ . Тогда заметим, что

v (ak− bk)=v ((apα−1t)p− (bpα−1t)p) p p

Т.к. основания степеней сравнимы по модулю $p$ , можно применить здесь доказанную в предыдущем пункте базу для $p= k$ . Получим

vp((apα−1t)p− (bpα−1t)p)= vp((apα−1t)− (bpα−1t))+ 1

Выполнив аналогичное действие $α$ раз, получим, что

vp(ak− bk) =α +vp(at− bt)

Но это, согласно первому пункту, равно

α+ vp(a− b)

Замечание. Заметим ещё, что вышеприведённое решение не работает при $p= 2$ , т.к. $p(p−2-1)$ в этом случае не кратен $p$ . Недостающую для этой делимости двойку можно получить из $n$ , если оно чётно, а это равносильно тому, что $a− b$ кратно $4$ . Таким образом, если $a− b$ кратно $4$ , то LTE для $p= 2$ выполняется.