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

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

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

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

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

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

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

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

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

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

Сколько делителей от $1$ до $200$ имеет число $2239− 1?$

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

Подсказка 1

Если совсем нет идей, то для начала стоит понять, что чётные делители можно отбросить.

Подсказка 2

Теперь давайте поймëм, что мы ищем такие n, для которых 2²³⁹ сравнимо с 1 по модулю n. Стоит подумать о показателе двойки по модулю n и о том, как он связан с 239.

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

Ясно, что на чётные делители это число делиться не может. А для любого нечетного числа $a$ если $2239 ≡1 (mod a),ord 2 a$ делит $239.$ Однако число $239$ — простое, то есть либо $orda2= 1,$ либо $239.$ Заметим, что по теореме Эйлера $φ(a) 2 ≡ 1 (mod a).$ Но $orda2≤φ(a)< a≤ 200 <239.$ Следовательно, $orda2= 1,$ откуда $a= 1.$

Ответ:

$1$

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

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

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

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

Докажите, что при натуральном $n >1$ число $2n − 1$ не делится на $n.$

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

Подсказка 1

Тут стоит идти от противного. Ясно, что n нечëтное. Учитывая, что из двойки в степени n вычитается единица и (2, n) равно 1, есть смысл поискать противоречие, связанное с показателем.

Подсказка 2

Рассмотрите наименьший простой делитель n.

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

Предположим противное, пусть существует такое $n.$ Ясно, что оно нечётное. Выберем у $n$ наименьший простой делитель $p.$ На него делится $n 2 − 1,$ то есть $n$ делится и на $ordp2.$ Также на этот показатель делится $φ(p)= p− 1.$ Учитывая, что $ordp2 >1,$ понимаем, что у $ordp2$ есть простой делитель, меньший $p,$ поскольку $ordp2≤ p− 1.$ Следовательно, $n$ также делится на этот делитель, значит $p$ — не наименьший простой делитель, пришли к противоречию.

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

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

Найдите все пары простых чисел $p$ и $q$ таких, что $(5p− 2p)(5q− 2q)..pq. .$

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

Подсказка 1

Для начала стоит откинуть случаи, когда первая сколка делится на p, либо вторая на q. В этом вам поможет МТФ.

Подсказка 2

Стало быть, теперь первая скобка делится на q, а вторая - на p.

Подсказка 3

Пусть p > q. Ясно, что (p, q - 1) = 1. Значит, 1 представляется в виде линейной комбинации p и q - 1. Попробуйте, используя это знания, провести некоторые манипуляции со сравнениями.

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

Предположим, что $5p− 2p$ кратно $p.$ По МТФ $5p− 2p ≡ 5− 2 =3 (mod p).$ Следовательно, $p= 3.$ Таким образом, $5p− 2p =3⋅3⋅13.$ То есть либо $q =3,$ либо $q = 13,$ либо $q$ делит $q q 5 − 2$ (аналогичная ситуация). Значит, в этом случае мы получили пары $(3,3),(3,13),(13,3).$

Пусть теперь $p$ не делит $p p 5 − 2,q$ не делит $q q 5 − 2 .$ Отсюда ясно, что $p p 5 − 2$ кратно $q q q,5 − 2$ кратно $p.$ Пусть $p >q.$ Ясно, что $(p,q − 1)= 1$ и, следовательно, существуют такие положительные $a$ и $b,$ что $ap− b(q − 1)= 1.$ Поскольку $(2,q)= (5,q)= 1,$ по МТФ имеем $q−1 q−1 5 ≡ 2 (mod q).$ По нашему предположению $p p 5 ≡ 2 (mod q),$ отсюда $ap ap 5 ≡ 2 (mod q).$ Последнее сравнение равносильно следующему: $b(q−1)+1 b(q−1)+1 5 ≡ 2 (mod q).$ Но в силу наших рассуждений $b(q−1)+1 b(q−1)+1 5 ≡5 (mod q),2 ≡2 (mod q).$ То есть $5 ≡2 (mod q),$ это возможно лишь при $q = 3,$ но этот случай сейчас не рассматривался.

Ответ:

$(3,3),(3,13),(13,3)$

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

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

Найдите все упорядоченные тройки простых чисел $(p,q,r)$ таких, что

q .. r .. p .. p + 1.r,q + 1.p,r + 1.q

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

Подсказка 1

Для начала поймем могут ли быть равные числа среди p, q, r?

Подсказка 2

Правильно, не могут! Попробуем теперь доказать следующую лемму: если p,q,r — такие различные простые числа, что p делит q^r+1 и p > 2, то либо p − 1 кратно 2r, либо q^2 − 1 кратно p. Заметим, что из условия леммы следует, что q^r сравнимо с -1, но не сравнимо с 1 по модулю p. Что можно сделать с этим сравнением?

Подсказка 3

Верно! Надо возвести его в квадрат и получить, что q^(2r) сравнимо с 1 по модулю p. Что тогда можно сказать про ord(q) по модулю p?

Подсказка 4

Точно! Он делит 2r, но не делит r. Так как p простое, то какой вывод можно сделать?

Подсказка 5

Ага! либо (ord q по модулю p) = 2, либо (ord q по модулю p) = 2r. Если верно второе, то p− 1 кратно 2r, поэтому лемму доказали. Теперь остается ее применить и поразбирать случаи. Предположим, что p, q, r — нечетные. Что следует из того, что p - 1 делится на 2r?

Подсказка 6

Верно! 0 ≡ p^q + 1 ≡ 2, то есть r = 2, а значит, противоречие. Теперь пусть q^2 - 1 делится на p. Какое тогда неравенство можно написать на p и q?

Подсказка 7

Точно! Из того, что q^2 - 1 делится на p следует, что либо (q-1)/2, либо (q+1)/2 делится на p, а значит, q > (q+1)/2 ≥ p. Теперь легко получаем противоречие. Осталось только разобрать случай, когда одно из чисел равно 2 и вычислить два других.

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

Ясно, что $qr+ 1$ не кратно $q,$ а значит $p⁄= q.$ Аналогично $q ⁄= r$ и $r⁄=p,$ то есть $p,q$ и $r$ различные.

_________________________________________________________________________________________________________________________________________________________________________________

Докажем теперь следующую лемму: если $p,q,r$ — такие различные простые числа, что $p$ делит $r q + 1$ и $p >2,$ то либо $p− 1$ кратно $2r,$ либо $2 q − 1$ кратно $p.$

Из условия леммы следует, что $r q$ сравнимо с $− 1$ по модулю $p,$ но не сравнимо с $1,$ поскольку $p> 2.$ Следовательно, $2r 2 q ≡ (− 1) ≡ 1 (mod p).$ Получаем, что $2r$ кратно $ordpq$ и $r$ не кратно $ordpq.$ Поскольку $r$ — простое, это возможно лишь когда $ordpq =2$ или $ordpq =2r.$ Если верно второе, то $p− 1$ кратно $2r.$ В первом же случае получим, что $2 q − 1$ кратно $p.$ Лемма доказана.

_________________________________________________________________________________________________________________________________________________________________________________

Начнём решение со случая, когда $p,q$ и $r$ нечётны. Поскольку $p$ делит $qr+ 1,$ по лемме либо $p− 1$ кратно $2r,$ либо $q2− 1$ кратно $p.$ Но первый случай невозможен, поскольку сравнение $p≡ 1 (mod r)$ влечёт за собой сравнения $0≡ pq+1 ≡2 (mod r),$ то есть $r= 2,$ что противоречит нашему предположению. Следовательно, $p$ делит $q2− 1= (q − 1)(q+ 1).$ Простое число $p$ нечётно, a $q− 1$ и $q+ 1$ чётны. Значит, одно из чисел $q−21$ или $q+21$ кратно $p.$ Отсюда следует, что $p≤ q+21< q.$ Аналогично $q < r$ и $r< p,$ противоречие.

Значит, среди чисел есть хотя бы одна двойка. Поскольку при циклической перестановке ничего не изменится, можно положить, что $p =2.$ Теперь $r$ делит $2q+ 1,$ тогда по лемме либо $2q$ делит $r− 1,$ либо $22− 1 =3$ кратно $r.$ Но первый случай невозможен, поскольку $q$ делит $r2+ 1= (r− 1)(r +1)+ 2$ и $q >2.$ Следовательно, $3$ кратно $r.$ По условию $r2+ 1= 10$ кратно $q.$ Ранее мы заключили, что $q ⁄=p,$ откуда $q ⁄= 2,$ то есть $q =5.$

Ответ:

$p =2,q = 5,r= 3$

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

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

Найдите остаток суммы всех выражений вида $ij,$ где $1 ≤i< j ≤ p− 1$ по простому модулю $p.$

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

У простого числа есть первообразный корень $g.$ Следовательно, каждый остаток в сумме можно заменить на $g$ в соответствующей степени, ведь нас интересует лишь остаток суммы при делении на $p.$ Но тогда сумму можно записать в следующем виде:

g(g2+ g3+...+gp−1)+g2(g3 +g4+ ...+ gp−1)+ ...+ gp−2⋅gp−1 = gp+1−-g3-+ gp+2−-g5+ ...+ g2p−2−-g2p−3-= g− 1 g− 1 g− 1

gp(g+ g2+...+gp−2)− (g3+ g5 +...+ g2p−3) = ----------------g− 1----------------

Мы получили дробь, которая является целой. Покажем, что она делится на $p,$ кроме некоторых случаев.

Предположим, что $g− 1$ не делится на $p.$ В этом случае достаточно доказать, что $p$ делит числитель дроби. Посмотрим на его первое слагаемое: $gp ≡g (mod p),$ а $g+ g2+...+gp−2$ — это сумма всех остатков при делении на $p,$ кроме $0$ и $1,$ то есть она сравнима с $− 1+ 2− 2+3 − 3+ ...= −1$ по модулю $p.$ Тогда всё слагаемое сравнимо с $− g.$ Докажем теперь, что $− g− (g3 +g5+ ...+ g2p−3)= − g2p−21−g g −1$ кратно $p.$

Если знаменатель $g2− 1$ делится на $p,$ то $g+ 1$ кратно $p$ (в этом случае $p$ не делит $g− 1$ ), откуда $g ≡−1 (mod p)$ и $g2 ≡ 1 (mod p).$ То есть либо $p =3,$ либо $p= 2$ (тогда $− 1≡ 1 (mod p)$ ). В первом случае остаток $p − 1,$ во втором — $0,$ потому что в сумме нет слагаемых. Иначе $g2− 1$ не делится на $p,$ а числитель делится, так как $g2p−1 = gp⋅gp−1 ≡ g⋅1≡ g (mod p).$ Следовательно, при $p >3$ остаток $0.$

Если же $g− 1$ делится на $p,$ то $g ≡ 1 (mod p),$ то есть $p =2.$ Этот случай уже рассмотрен.

Ответ:

$0$ при $p⁄= 3$ и $p− 1$ при $p= 3$

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

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

Пусть $p$ и $q$ — простые, $q > 5.$ Известно, что $2p+ 3p$ делится на $q.$ Докажите, что $q > 2p.$

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

Предположим противное, пусть $q ≤2p.$ По условию $q >5,$ то есть $q$ — нечётное, а значит $q ≤2p− 1.$ Делимость $2p+ 3p$ на $q$ равносильна сравнению $p p 2 ≡− 3 (mod q).$ Возведём его в квадрат: $2p 2p 2 ≡ 3 (mod p).$ Далее запишем его следующим образом: $2p− q+1 q−1 2p−q+1 q− 1 2 ⋅2 ≡ 3 ⋅3 (mod q).$ После применения МТФ последнее сравнение превратится в $2p−q+1 2p−q+1 2 ≡3 (mod q).$ Следовательно,

2p− q+1 2p−q+1 p− q−1- p− q−1 p− q−1 p− q−1 3 − 2 = (3 2 − 2 2 )(3 2 + 2 2 )

кратно $q.$ Отсюда вытекают два случая.

Если первая скобка кратна $q,$ то $3p− q−21≡ 2p− q−12-(mod q).$ Также ранее мы выяснили, что $22p ≡32p.$ Таким образом, зная, что если $x x (a,b)= 1,a ≡b (mod m)$ и $y y a ≡ b (mod m),$ то $НОД(x,y) НОД(x,y) a ≡ b (mod m )$ получаем:

(2p,p− q−1) (2p,p− q−1) 2 2 ≡ 3 2 (mod q)

Осталось заметить, что $p− q−1- 2$ не делится на $p,$ потому что $0 < q−1 ≤p− 1 2$ по нашему предположению. Следовательно, этот НОД равен либо $1,$ либо $2.$ То есть либо $1≡ 0 (mod q),$ либо $5≡ 0 (mod q),$ но при $q > 5$ это невозможно.

Если вторая скобка кратна $q,$ то $3p− q−21≡ −2p− q−21(mod q).$ Домножим сравнение на $6q−21$ и получим: $2q−21⋅3p ≡ −3q−21⋅2p (mod q).$ Условие позволяет заменить в последнем сравнении $2p$ на $− 3p$ и получить следующее: $2q−21≡ 3q−21.$ Снова приходим к первой задаче, только в этом случае нужно посмотреть на $q−1 (2p, 2 )$ и аналогичным способом убедиться, что он может быть лишь $1$ или $2,$ что приводит к противоречию.

Курсы

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

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

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

Докажите, что $2$ является первообразным корнем любого простого числа вида $p= 4q +1,$ где $q$ — простое.

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

Пусть $ord2 =d, p$ тогда $d$ делит $p− 1= 4q.$ Поскольку $q$ — простое, задача сводится к рассмотрению случаев.

Если $d= 1,$ то $2≡ 1 (mod p),$ что невозможно.

Если $d= 2,$ то $4≡ 1 (mod p),$ то есть $p= 3,$ но $p> 3,$ противоречие.

Если $d= 4,$ то $16≡1 (mod p),$ откуда $p =3$ или $p= 5,$ но $p> 5,$ противоречие.

Случаи $d= q$ и $p =2q$ влекут за собой сравнение $2q 2 ≡ 1 (mod p).$ Но $2q p−1 2 =2 2 .$ То есть двойка — квадратичный вычет по модулю $p.$ Заметим, что при нечётном $q$ простое число $p$ имеет вид $8k+ 5$ (при $q =2$ число $p$ составное). Однако двойка не может быть квадратичным вычетом по простому модулю вида $8k+ 5,$ противоречие. Следовательно, $d= 4q,$ что и требовалось.

Теперь докажем, что двойка не может быть квадратичным вычетом по простому модулю $p$ вида $8k +5.$ Остатки $p−1 1,2,...,-2-$ при делении на $p$ будем называть положительными, а остальные — отрицательными. Умножим все положительные остатки на $2 :2,4,...,p − 3,p− 1.$ Пусть среди полученных чисел есть $x$ отрицательных остатков. Тогда с одной стороны произведение этих остатков сравнимо с $(−1)x ⋅(p−21)!$ по модулю $p,$ с другой стороны оно сравнимо с $p−1- 2 2 ⋅(p−21)!$ по модулю $p.$ Отсюда получаем, что $p−1 2-2-≡ (−1)x (mod p).$

Осталось заметить, что отрицательными будут лишь те, которые лежат между $p+21-$ и $p− 1$ (границы включены). Количество таких чисел равно верхней целой части от $p−41.$ При $p= 8k+ 5$ оно нечётно, то есть $2p−12-≡ (−1)x ≡ −1 (mod p).$ Следовательно, двойка — квадратичный невычет, доказано.

Ответ:

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

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

Докажите, что $2$ является первообразным корнем по модулю $3n$ при любом натуральном $n.$

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

Докажем индукцией по $n,$ что $ord n2= φ(3n)= 2⋅3n−1. 3$ Нетрудно убедиться, что $2$ — первообразный корень по модулю $3.$

Предположим, что утверждение верно для всех $k≤ n+ 1.$ Пусть $ord3n+12= d,$ тогда $n+1 n+1 n n φ(3 )= 3 − 3 = 2⋅3$ кратно $d.$ Ясно, что $d$ чётное, иначе $d 3$ не будет давать остаток $1$ при делении на $n+1 3 .$ То есть $a d= 2⋅3 .$ Заметим, что

a a−1 a−1 a−1 22⋅3 − 1= (22⋅3 − 1)(24⋅3 + 22⋅3 +1)

По предположению $v(22⋅3a−1 − 1)= a. 3$ Вторая же скобка делится на $3,$ но не делится на $9,$ поскольку $2⋅3a−1$ кратно $φ(9)= 6$ при $a ≥2$ (случаи, когда $a< 2$ можно рассмотреть отдельно). Таким образом, степень вхождения $3$ в $2⋅3a 2 − 1$ равна $a+ 1.$ Значит, для делимости на $n+1 3$ необходимо, чтобы $a$ было не меньше $n.$ Следовательно, $n ord3n+12= 2⋅3,$ что и требовалось.

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

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

Докажите, что если $n= 3k−1,$ то $2n +1..3k. .$

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

Иными словами, нас просят доказать сравнение $23k−1 ≡ −1 (mod 3k).$ Возведём его в квадрат: $22⋅3k−1 ≡ 1 (mod 3k).$ Заметим, что полученное сравнение верно, поскольку $k−1 k 2⋅3 = φ(3).$ Таким образом, $3k−1 3k−1 (2 − 1)(2 + 1)$ кратно $k 3.$ НОД скобочек не превосходит двух, поэтому одна из скобочек делится на $k 3 .$ Предположим, что это первая скобочка, тогда $k−1 k−1 k ord3k2≤ 3 <2⋅3 = φ(3).$ То есть двойка не является первообразным корнем по модулю $k 3 ,$ получили противоречие, так как двойка первообразный корень $k 3,$ то есть делится первая, что и требовалось.

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

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

Натуральное число $n >3$ таково, что $a= 2n−-2 n$ — целое. Докажите, что $a$ — составное.

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

При $n> 3$ число $a> 1.$ Предположим, что при некотором $n> 3$ число $a$ будет простым. Если число $n$ — нечетное, то целое число $2n-− 2 a = n$ заведомо будет четным. Тогда $a= 2,$ откуда $n 2 = 2n +2,$ что выполняется только при $n= 3,$ а при $n> 3$ $n 2 > 2n+ 2$ (легко доказать по индукции).

Если число $n$ — четное, то $n= 2k,$ где $k$ нечетное, иначе $2n− 2 a= --n--$ не будет целым. Тогда $22k− 1− 1 a= ---k---,$ откуда $22k−1− 1 ≡0 (mod k).$ Для $n >3,k> 1.$ Значит, $2k− 1> k> δ,$ где $δ$ — наименьшее число такое, что $2δ− 1 ≡0 (mod k).$ Тогда $(2k− 1)...δ.$

a= 2δx-− 1-= 2δ− 1-⋅(1+ 2δ+...+2δ(x−1)) k k

Если $a$ простое, то $2δ−-1 k = 1.$ Значит, $δ k= 2 − 1.$ Тогда

2δx− 1 a= -2δ− 1

Если $x$ составное, то $x = q1q2$ тогда

2δx − 1= (2δq1 − 1)(1+ 2δq1 + ...+2δ(x−q1))

Где число $2δ− 1|2δq1 − 1$ и при этом $2δ− 1⁄= 2δq1 − 1,$ следовательно $a$ будет составным.

Значит, $x$ — простое. Пользуясь круговыми многочленами, сможем показать, что

2δx−-1 ∏ 2δ − 1 = Φd(2) d|δx,d∤δ

где $Φd$ — круговой многочлен. $Φd(2)= ∏ |2− ξ|>1, ξ$ где $ξ$ примитивные корни степени $d$ из $1.$ И если $δ$ имеет простой делитель $p$ отличный от $x,$ то $δx p$ будет делителем $δx,$ но не $δ.$ И тогда $a$ как минимум будет содержать в произведении $Φx(2)⋅Φδx(2), p$ то есть не будет простым. Тогда $x$ — простое нечетное, а $δ = xj$ для некоторого натурального $j,k =2δ− 1.$ Тогда

j+1 δ+1 xj+1 x =δx =2k− 1= 2 − 3= 2 − 3

Тогда по простому модулю $x$ число $xj+1 ≡2⋅2− 3≡ 1.$ Противоречие. Значит, $a$ — составное.

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

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

Дано нечетное простое число $p$ , а также простые числа $q$ и $r$ . Известно, что $qr+1 ..p .$ . Докажите, что либо $p− 1..2r .$ , либо $2 .. q − 1.p$ .

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

Давайте сразу перепишем все на язык сравнений. Известно, что $qr ≡− 1 (mod p)$ . Возведем это неравенство в квадрат. Получим, что $2r q ≡ 1 (mod p)$ , значит $.. 2r .d =ordpq$ и так как $r$ простое, то у $d$ есть 4 варианта для значения.
1 случай $d= 2r$ Тогда по последнему свойству $.. p− 1 =φ(p).d= 2r$
2 случай $d= 1$ Тогда $.. q− 1.p$ и $2 .. q − 1= (p − 1)(p+ 1).p$ .
3 случай $d= 2$ Тогда $2 .. q− 1.p$
4 случай $d =r$ Если $r= 2$ , то получается 3 случай, поэтому давайте считать, что $r⁄= 2$ . Тогда по последнему свойству $.. p− 1= φ(p).d =r$ и $.. p− 1.2$ , поэтому $.. p − 1.2r$ .

Интенсивы

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

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

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

Дано простое число $p$ . Докажите, что $22p − 4$ делится на $2p− 1$ .

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

Подсказка 1

Четвëрка делимости никак не помогает, значит, на неë исходное число можно поделить. Теперь мы оказались в ситуации, когда можно использовать показатели.

Подсказка 2

А именно, нас интересует одно из из свойств. Если a в степени x сравнимо с a в степени y по модулю m, то как связаны между собой x, y и показатель a по модулю m?

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

$22p − 4= 4⋅(22p−2− 1)$ должно делиться на $2p− 1$ и очевидно, что на самом деле мы хотим, чтобы $22p−2 − 1$ делилось на $p 2 − 1$ . Если мы хотим доказать, что степень двойки минус один делится на какое-то число, то нам на самом деле нужно доказать, что $p .. 2 − 2.ord2p−12$ . Чему же равен $ord2p− 12$ ? Поймем, что $ord2p− 12 =p$ , так как во-первых, $p$ подходит, так как $p p 2 ≡ 1 (mod 2 − 1)$ , для $x <p$ $x p 2 − 1 <2 − 1$ , поэтому $x 2 − 1$ не может делиться на $p 2 − 1$ . Тогда нам нужно доказать, что $p p−1 .. 2 − 2 =2(2 − 1).p$ . Если $p= 2$ , то это очевидно, если $p⁄= 2$ , то это верно по теореме Эйлера.

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

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

Даны натуральные числа $a,n >1$ . Докажите, что для каждого нечетного простого делителя $p$ числа $a2n + 1$ число $p− 1$ делится на $n+1 2$ .

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

$a2n ≡ −1 (mod p)$ , поэтому $a2n+1 ≡1 (mod p)$ , а значит $2n+1..d =ord 2 . p$ . Отсюда следует, что $d= 2x$ , где $x≤ n+ 1$ . Если $x= n+ 1$ , то $..n+1 p − 1= φ(p).2$ и все хорошо. Если же $x ≤n$ , то $2n 2x 2n−x a = (a ) ≡ 1 (mod p)$ . Противоречие.

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

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

Докажите, что для любого натурального $n >1,$ свободного от квадратов, существуют такие простое число $p$ и целое число $m,$ что $n$ делится на $p,$ а $2 p p + pm$ делится на $n.$

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

Пусть $n =p p ...p 1 2 k$ для некоторого упорядоченного набора простых чисел $p < p < ...< p , 1 2 k$ причём $p k$ — нечетное. Пусть $p= p k$ и определим

P =p1p2...pk−1.

Если $k= 1,$ утверждение задачи очевидно, теперь $k ≥2.$ Пусть $b ,b ,...b 1 2 φ(P)$ — все вычеты по модулю $P,$ взаимно простые с $P.$

Во-первых, любое $b i$ при возведении в $p$ -тую степень остаётся по модулю $P$ взаимно простым с $P.$

Во-вторых, пусть существуют $i⁄= j,$ что

i,j ∈ {1,2,...,φ(P )}

и $bp≡ bp. i j$ Если $bi-≡s (mod P) bj$ и $ordP s= l,$ то $sp ≡1 (mod P),$ то есть $p$ делится на $l,$ но тогда или $l= 1,$ что влечёт за собой $i= j$ — противоречие, или $l= p,$ но тогда