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

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

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

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

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

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

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

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

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

Задача 21#102515Максимум баллов за задание: 7

Пусть $n >5$ — такое нечётное число, что число $φ(n(n+ 1))$ является степенью двойки. Докажите, что $n+ 1$ — тоже степень двойки.

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

Подсказка 1

Нетрудно заметить, что любой примарный сомножитель в разложении n имеет вид 2^(2^k)+1(почему это так?). То есть задача сводится к рассмотрению чисел такого вида. Что вы можете про них сказать? Что вы можете сказать про эти числа по модулю чисел такого же вида?

Подсказка 2

Рассмотрите наименьшее число вида 2^(2^k)+1, на которое не делится n(n+1). А что делать дальше? Вообще у нас задача по теории чисел, поэтому нужно писать какие-то сравнения и изучать степени вхождения простых, причем задача намекает, что изучать нужно именно вхождения двойки. Пишите много сравнений и неравенств, может что выйдет))

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

Так как функция Эйлера мультипликативна, то если $ps$ — это примарный сомножитель в разложении $n<$ то $ps−1(p− 1)$ является степенью двойки, что возможно только в двух случаях: $p =2$ или $t p= 2 +1.$ Легко видеть, что если $t$ не является степенью двойки, то $p$ не простое. Поэтому любой примарный сомножитель это либо степень двойки, либо одно простое число Ферма, то есть простое вида $2k 2 + 1.$

Положим $2m−1 pm =2 + 1$ (отметим, что не все из них простые). Так как $n$ и $n+ 1$ взаимно просты, то функция Эйлера от каждого из них является степенью двойки. Пусть

n+ 1= 2sq1q2...qx; n= r1r2...ry

где $qi$ и $rj$ — простые числа Ферма. Заметим, что

pn+1 =2+ p1p2...pn

поэтому любое число Ферма больше произведения всех меньших.

Среди различных чисел $q i$ и $r j$ выберем наибольшее, пусть это $p . e$ Если оно в разложении числа $n +1,$ то очевидно, что $n +1$ будет сильно больше числа $n.$ Значит, оно в разложении числа $n.$ Пусть $n$ делится на $p,p ,...,p , 1 2 z$ но не делится на $p z+1$ (возможно, $z =0).$

Рассмотрим числа $n$ и $n+ 1$ по модулю $2z w= 2 +1.$ Все числа Ферма, которые есть в разложении, кроме $p1,p2,...,pz,$ дают остаток $1$ от деления на $w,$ $p1p2...pz$ дает остаток $2z 2 − 1$ от деления на $w.$ Тогда $n+ 1$ с одной стороны дает остаток такой же, как $s 2 ,$ а с другой стороны — $(2z ) 2z 2 − 1 + 1= 2 .$ Значит, $z s =2 .$

Тогда $s n +1 =2 q1q2...qx,$ а число $n$ делится на $2z p1p2...pz = 2 − 1$ и на $pe.$ Если $z = e,$ то $2e n= 2 − 1,$ и, следовательно, число $n +1$ — степень двойки. Покажем, что случай $e> z$ невозможен. В этом случае число $n$ делится на $z 22 − 1$ и на $pe.$ Пусть $z >0.$ Тогда

z z n ≥(22 − 1)pe =(22 − 1)(p1p2...pe−1+ 2)>

>(2s− 1)p1q1...qx =3(2s − 1)q1...qx ≥2sq1...qx = n+ 1

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

Пусть $z =0.$ Тогда $n ≥pe,$ а $n +1= 2q1...qx.$ Если $q1...qx$ — произведение всех чисел Ферма, меньших $pe,$ то $n+ 1= 2(pe− 2),$ а $n =pe,$ откуда $pe +1= 2(pe − 2)$ и $n= pe = 5,$ что запрещено условием. В противном случае

n +1 =2q1...qx < 2(pe− 2)∕p1 = 2(pe− 2)∕3< pe ≤ n

— снова противоречие.

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

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

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

Задача 22#127170Максимум баллов за задание: 7

Докажите, что для натурального числа $a$ найдется такое натуральное число $b> a,$ что $1+ 2b+3b$ делится на $1+ 2a+3a.$

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

Для $a= 1$ подходит $b= 3,$ далее считаем $a ≥2.$ Пусть $M = 1+ 2a+ 3a.$ Будем искать, такое $b= a+ Δ,$ что

a b a b 2 ≡ 2 (mod M ) 3 ≡ 3 (mod M ).

Пусть $M =2xN = 3yK,$ $N$ не делится на $2, K$ не делится на $3.$ Покажем, что $Δ$ кратные $φ(N)$ подходят.

Сделаем оценку на $x,$ рассмотрев $M$ по модулю $8,$ при $a≥ 3.$

a−3 a a M ≡ 1+ 8⋅2 + 3 ≡ 1+ 3 ⁄≡0 (mod 8),

так как $3a$ по модулю $8$ принимает только значения $1,3.$ Отдельно рассмотрим случай $a =2 :$

M = 1+ 4+ 9= 14 =⇒ x= 1.

Получаем, что $x≤ 2≤ a.$ Тогда для любого $Δ$ имеем:

2a+Δ ≡ 2a ≡ 0 (mod 2x)

Из $НО Д(N,2)= 1,$ тогда по теореме Эйлера имеем:

2φ(N) ≡ 1 (mod N) =⇒ 2a+Δ ≡ 2a (mod N),

для всех $Δ$ кратных $φ(N).$ Из данных двух сравнений следует, что:

2a+Δ ≡2a (mod M ).

Сделаем оценку на $y :$

1+ 2a+ 3a < 3a+1 =⇒ y ≤a.

Тогда аналогично получаем, что:

a a+Δ y 3 ≡ 3 ≡ 0 (mod 3 ),

для всех $Δ.$ Аналогично случаю для $N$ по теореме Эйлера:

a+Δ a 3 ≡3 (mod K),

для $Δ$ кратных $φ(K ).$ Тогда подходит $b= a+ φ(N )φ(K).$

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

Задача 23#83139Максимум баллов за задание: 7

Теорема Эйлера. Для любого числа $m$ и взаимно простого с $m$ числа $a$ верно, что $aφ(m) ≡ 1$ (mod $m$ )

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

Давайте возьмем две разные ПрСВ по одному модулю $m$ и перемножим в каждой все числа. Так как наборы остатков одинаковые, то получившиеся произведения будут сравнимы по модулю $m$ .

Тогда рассмотрим две такие ПрСВ: [ $x1$ , $x2$ , ..., $xφ(m )$ ] (это любая ПрСВ по модулю $m$ ) и [ $ax1$ , $ax2$ , ..., $axφ(m)$ ] (То, что написано справа - это $a⋅$ ПрСВ) и перемножим в каждой все числа. Получаем, что:
$x1⋅x2⋅....⋅xφ(m ) ≡ax1⋅ax2⋅....⋅axφ(m)$ (mod $m$ ) или
$φ(m) x1x2...xϕ(m ) ≡x1x2...xφ(m)a$ (mod $m$ ).
Теперь перепишем это сравнение через разность, то есть
$φ(m) φ(m) a x1x2...xφ(m)− x1x2...xφ(m) = (a − 1)x1x2...xφ(m)$ делится на $m$ .
Из-за того, что НОД( $xi$ , $m$ ) = 1, то отсюда следует, что $aφ(m)− 1$ делится на $m$ или $aφ(m) ≡ 1$ (mod $m$ )