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

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

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

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

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

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

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

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

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

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

(a) Пусть $p$ и $q$ — различные простые нечётные числа. Определим $ν(q)$ как количество элементов в множестве $p−1 S ={q⋅1,q⋅2,...,q⋅ 2 },$ больших $p−1 2 .$ Докажите, что

p−1⌊ ⌋ ν(q) = 2∑ iq-. i=1 p

(b) Квадратичный закон взаимности. Пусть $p,$ $q$ — различные нечетные простые числа. Тогда выполнено равенство:

( ) ( ) p ⋅ q = (−1)p−21⋅q−21 q p

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

(a) Рассмотрим $a∈ S$ — вычет и соответствующее ему число $p−1 qk,k ≤ 2 .$ Заметим, что $p−1 a≤ 2 ,$ если и только если

2mp p− 1 p(2m +1) -2-= mp <qk ≤mp + -2--< ---2---,

а больше если (переход так как у нас $p−1 -2-$ — целое)

p− 1 p(2m +1) p(2m + 2) mp + -2--< qk <(m +1)p⇒ ----2---< qk< ---2---,

тогда логично рассмотреть $⌊ ⌋ 2kpq-,$ если оно четно, то $a ≤ p−21,$ иначе больше. Тогда

p∑−21⌊2iq⌋ p−∑21⌊2i⋅q⌋ ν(q)≡2 -p- = -p-- . i=1 i=1

Заметим, что

⌊ ⌋ ⌊ ⌋ ⌊ ⌋ ⌊ ⌋ i⋅q + (p− i)⋅q = q− 1≡2 0 ⇒ i⋅q ≡2 (p−-i)⋅q- . p p p p

Тогда в получившейся сумме все $2i$ большие $p−1- 2$ заменим на $p− 2i,$ тогда суммирование пройдет по всем $i$ от $0$ до $p−1- 2 ,$ то есть

p−2∑1-⌊2iq⌋ p∑−21⌊iq⌋ ν(q)≡2 p--≡2 p- . i=1 i=1

(b) Докажем сначала лемму.

Лемма. Пусть $p$ и $q$ — различные простые нечетные числа. Рассмотрим прямоугольник на целочисленной решетке с вершинами в точках $(1,1),$ $(1,q−1), 2$ $(p−1,1), 2$ $(p−1,q−1). 2 2$ Посчитав точки внутри и на границе этого прямоугольника, докажите, что

p∑−21[ ] q∑−21[ ] iq + jp = p−-1⋅ q−-1 i=1 p j=1 q 2 2

Доказательство. Рассмотрим прямоугольник как область:

{ p− 1 q− 1} R = (x,y)∈ ℤ2|1≤x ≤ -2-, 1≤ y ≤-2-- .

Всего точек в $R :$ $p−21⋅ q−21.$

Прямая $y = qx p$ делит прямоугольник $R.$ Количество точек под этой прямой для $x = i$ равно $⌊iq⌋ . p$ Сумма $∑ p−12-⌊iq⌋ i=1 p$ даёт общее количество точек под прямой $y = qx. p$

Аналогично, сумма $∑ q−21⌊jp⌋ j=1 -q$ соответствует точкам над прямой $q y = px.$

$PIC$

Так как $p$ и $q$ — различные простые числа, они взаимно просты. Следовательно, прямая $y = qpx$ не проходит через целые точки внутри $R.$ Таким образом количество точек в $R$ равно:

p∑−21⌊iq⌋ q−∑12-⌊jp⌋ p− 1 q− 1 p- + q- = -2--⋅-2--. i=1 j=1

______________________________________________________________________________________________________________________________________________________

Рассмотрим $ν$ из предыдущего пункта, только добавим индекс снизу $νp$ — рассматриваем по модулю $p,$ тогда получим, что

(p) νq(p) (q) νp(q) (p) (q) νp(q)+νq(p) q = (− 1) , p = (−1) ⇒ q ⋅ p =(−1) .

По предыдущему пункту

p−1- q−1 ν (q)+ ν(p)≡ 2∑ ⌊ iq⌋ +∑2 ⌊jp⌋, p q 2 i=1 p j=1 q

а по лемме, это равно $p-− 1 ⋅ q− 1-, 2 2$ тогда и получаем необходимое:

( ) ( ) p ⋅ q = (− 1)p−21⋅q−12 . q p

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

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

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

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

Найдите

(a) $(-3-) 239 ;$ (b) $(1009) 2017 ;$ (c) $( 113) 967 .$

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

Символы Лежандра вычислены следующим образом:

(a)

( 3 ) (3−1)(239−1)( 239) 119(2) 119 32−1- 120 239 =(−1) 4 -3- = (− 1) 3 =(−1) ⋅(−1) 8 =(−1) = 1.

(b)

( 1009) (1009−1)(42017−1)( 2017) ( −-1) 2017 =(−1) 1009 = 1009 = 1.

(c)

( ) ( ) ( ) ( ) ( ) 113- = (− 1)(113−1)(4967−1) 967- = 63- = 9-- -7- = 967 113 113 113 113

(7−1)(113−1)( 113) (1) (−1) 4 -7- = 7 = 1.

Ответ:

Во всех пунктах $1$

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

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

Докажите, что простых чисел вида $3k+ 1$ бесконечно много.

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

Предположим противное, пусть существует конечное число простых чисел вида $3k +1.$ Пусть это $p,p ,...,p . 1 2 n$

Построим число:

2 N =4(p1⋅p2⋅...⋅pn) +3

Заметим, что $N ≡ 1 (mod 3),$ так как $(p )2 ≡1 (mod 3) i$ для всех $p≡ 1 (mod 3), i$ и $4 +3≡ 1 (mod 3).$

Посмотрим на делители $N :$

Если $N$ простое, то оно новое простое вида $3k+1$ —– противоречие. Если $N$ составное, рассмотрим любой его простой делитель $q.$ Тогда: $q ⁄= 2,$ так как $N ≡ 1 (mod 2).$ Заметим, что

2 (2p1⋅p2⋅...⋅pn) ≡ −3 (mod q)

Следовательно, $−3$ — квадратичный вычет по модулю $q,$ т.е.:

(−3) q = 1

Раскроем символ Лежандра:

(−3 ) (− 1) (3) q−1 (q−1)(3−1) (q) -q- = -q- ⋅ q = (− 1) 2 ⋅(−1) 4 ⋅ 3

Упростив, получим:

( ) −3- = 1 =⇒ q ≡ 1 (mod 3) q

Таким образом, все простые делители $q$ числа $N$ имеют вид $3k+ 1,$ противоречие, так как

4(p ⋅p ⋅...⋅p)2+ 3≡ 3⁄≡ 0 (mod p ) 1 2 n i

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

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

Докажите, что число $2n +1$ не имеет простых делителей вида $8k+ 7.$

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

Предположим, что существует простое число $p= 8k +7,$ делящее $2n+ 1.$ Применим критерий Эйлера для квадратичных вычетов. Поскольку $p= 8k+7 ≡− 1 (mod 8),$ символ Лежандра $( 2) p$ равен единице:

p−1 4k+3 1≡ 2 2 ≡ 2 (mod p).

Тогда $d$ — порядок двойки по модулю делит $4k +3 =⇒ d — нечетное.$ Но из $2n ≡ −1 (mod p)$ следует:

2n 2 ≡ 1 (mod p) =⇒ d делит 2n,но не делитn =⇒ d — четное.

Следовательно, исходное предположение неверно. Число $2n +1$ не может иметь простых делителей вида $8k+ 7.$

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

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

Решите уравнение $x3− x+ 9= 5y2$ в целых числах.

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

Заметим, что левая часть всегда делится на $3,$ откуда $y = 3z$ и уравнение преобретает вид $x3− x+ 9= 45z2$ или $2 (x− 1)x(x+ 1) =9(5z − 1).$ Поскольку в левой части стоит три последовательных целых числа, ровно одно из них делится на $3.$ Также заметим, что правая часть дает остаток $1$ при делении на $5,$ откуда $x$ дает остаток $2$ при делении на $5.$

Пусть $2 5z − 1$ делится на некоторое простое $p.$ Тогда $5$ является квадратичным вычетом по модулю $p.$ Откуда, согласно квадратичному закону взаимности, либо $p= 2,$ либо $p$ имеет вид $5k± 1.$ В частности, $2 5z − 1$ не делится на $3.$ Выберем из чисел $x$ и $x +1$ нечетное. Тогда в его разложение на простые множители могут войти только $9$ и простые вида $5k± 1$ в натуральных степенях, т.е. либо $x,$ либо $x +1$ имеет вид $5k±1.$ Это не так, поскольку $x$ имеет вид $5k+ 2.$

Ответ:

Решений нет

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

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

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

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

Пусть $d =ord3. p$ Тогда $d | p− 1,$ а потому $d =2k.$ Покажем, что $n= k.$ Для этого достаточно показать, что $32n−1 ≡ −1. p$ Это равносильно $(p−1)∕2 3 ≡p −1,$ что, по критерию Эйлера, эквивалентно $(3) p = −1.$ По квадратичному закону взаимности

( 3)( p) p 3 = 1

Тогда $( ) ( ) 3p = p3 .$ Покажем, что $p$ не является квадратичным вычетом по модулю $3.$ По условию $p =2n +1.$ Если $n$ нечетно, то $2n+ 1≡3 0,$ откуда $p$ делится на $3$ — противоречие. Пусть $n$ — четно. Тогда $2n+ 1≡3 2,$ но $2$ — квадратичный невычет, что и требовалось.

Курсы

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

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

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

Ненулевые взаимно простые в совокупности числа $a,b,c,d$ удовлетворяют равенству

( 1 1 1 1)2 abcd a + b +c + d = (a +b+ c+ d)2

Докажите, что все нечетные простые делители числа $a2+ b2+ c2+d2$ дают остаток $1$ при делении на $4.$

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

Подсказка 1

В уравнениях с целыми числами дроби выглядят не очень приятно. Избавьтесь от них и предположите противное.

Подсказка 2

Если сумма квадратов a, b, c, d делится на p=4k+3, то по модулю p можно выразить a через остальные переменные. Этот шаг сохраняет все условия, поэтому его следует сделать. Теперь у нас есть какое-то равенство и модуль p. Напишите вместо знака равно сравнение.

Подсказка 3

Тождество получилось 6 степени. Попробуйте разложить его на квадратные множители. Как их найти? В условии есть p=4k+3 и квадраты. Как их связать? На самом деле сумма квадратов не бывает равна нулю по модулю p. Докажите это и поймите из этого разложение на множители.

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

После раскрытия скобок и сокращения, а также избавления от знаменателей получаем равенство

22 2 2 22 22 2 22 2 2 2 2 2 (ab c +a b d +a cd + bc d) =abcd(a + b+ c + d)

Предположим, что $a2+ b2 +c2+ d2$ имеет некоторый простой делитель $p$ вида $4k+ 3.$ Тогда $a2 ≡− b2− c2− d2 (mod p).$ При этом

22 2 2 22 22 2 22 2 2 22 2 2 2 2 2 2 2 2 2 ab c +a b d+ a cd + bc d ≡ bc d − (b +c + d)(bc + cd + bd )≡

≡ −(b2+c2)(c2+ d2)(b2+ d2)≡0 (mod p)

Тогда одна из скобок делится на $p.$ Пусть, не умаляя общности, $b2+ c2$ делится на $p,$ но тогда $b$ и $c$ делятся на $p$ (иначе $− 1≡ (b∕c)2$ было бы квадратичным вычетом по модулю $p =4k+ 3,$ что невозможно). Тогда $a2+ d2$ также делится на $p,$ откуда $a$ и $d$ делятся на $p$ — противоречие с взаимной простотой $a,b,c,d.$

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

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

Докажите, что простое число $p$ является делителем числа вида $x2− x+ 3$ тогда и только тогда, когда оно является делителем числа вида $2 y − y+ 25.$

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

Подсказка 1

Предположим, что p делит число x²-x+3 при некотором x, тогда существует решение сравнения a²-a+3 ≡ 0. Как это можно переформулировать в терминах квадратичных вычетов?

Подсказка 2

Решение существует в том и только в том случае, если дискриминант данного трехчлена является квадратичным вычетом по по данному модулю. А значит, достаточно показать, что дискриминант x²-x+3 является квадратичным вычетом тогда и только тогда, когда дискриминант y²− y +25 является квадратичным вычетом. Вычислите дискриминанты и докажите объявленное утверждение.

Подсказка 3

Дискриминанты равны -11 и -99. Как доказываемое утверждение можно переформулировать в терминах символа Лежандра?

Подсказка 4

Необходимо показать равенство символов Лежандра от -11 и от -99. Почему они равны?

Подсказка 5

Потому что символ Лежандра мультипликативен, а его значение от 9 равно 1.

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

Как известно, решение $.. ax2+bx+ c. p$ существует тогда и только тогда, когда дискриминант $ax2+bx+ c$ является квадратичным вычетом по модулю $p.$ Поэтому, условие задачи равносильно следующему утверждению: дискриминант $x2− x+ 3$ является квадратичным вычетом по модулю $p$ тогда и только тогда, когда дискриминант $y2− y +25$ является квадратичным вычетом по тому же модулю.

Вычислим указанные дискриминанты. Первый равен $1− 12 =− 11,$ а второй $1− 100 =− 99.$ Фактически, требуется проверить, что для любого простого $p$ выполнено $( ) ( ) −1p1 = −9p9 ,$ где $( ) ap$ – символ Лежандра. Отдельно отметим, что случай $p= 2$ очевиден – для него не определено понятие символа Лежандра. Согласно свойству мультипликативности, $( ) ( ) ( ) −9p9 = −1p1 ⋅ 9p .$ При этом, очевидно, $(9) 2 p = 1:3 ≡ 9 (mod p)$ для всех $p.$

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

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

Пусть $p >2$ — простое число. Назовем вычет $a∈ ℤ p$ биквадратичным по модулю $p,$ если существует вычет $b$ такой, что $4 a ≡b (mod p).$ Докажите, что $p= 4k+ 3$ тогда и только тогда, когда его множества квадратичных и биквадратичных вычетов совпадают.

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

Из общей теории известно, что количество квадратичных вычетов по любому простому $p >2$ равно $p−-1. 2$ Отметим, что любой биквадратичный вычет является и квадратичным ( $4 22 a≡ b =(b) (mod p)$ ), поэтому их количество не превосходит $p−1- 2 .$ Тем самым, задача равносильна проверке того, что только для простых вида $p= 4k +3$ количество биквадратичных вычетов равно $p−1 2 .$

Рассмотрим биквадратичные вычеты $( )4 14, 24,..., p−21 .$ Покажем, что никаких других биквадратичных вычетов нет. Рассмотрим произвольную четвертую степень натурального числа $b4.$ Ее основание, $b,$ поделим на $p$ с остатком: $b= kp+ l,l< p.$ Справедливо, что $b4 ≡ l4 ≡(p− l)4 (mod p),$ причем либо $l≤ p−21,$ либо $p− l≤ p−21.$ Поскольку множество биквадратичных вычетов определяется как множество остатков, которые дают четвертые степени натуральных чисел по модулю $p,$ утверждение доказано. Покажем теперь, что среди $( )4 14, 24,..., p−21$ есть одинаковые вычеты по модулю $p$ тогда и только тогда, когда $p= 4k+1$ для некоторого натурального $k.$ Ясно, что это утверждение равносильно нашей задаче.

Проведем рассуждение, являющееся цепочкой равносильных переходов. Среди

( ) 14, 24,..., p−-1 4 2

есть два равных остатка по модулю $p$ тогда и только тогда, когда существуют $p−1 k,l≤-2-,k⁄= l$ и $.. k4 − l4. p.$

k4− l4 =(k2+ l2)(k− l)(k+ l)

Ясно, что ни $k− l$ , ни $k+ l$ не делится на $p,$ поэтому $2 2 k ≡ −l (mod p).$ Следовательно, для $a,$ такого что $a< p$ и $2 k ≡a (mod p),$ справедливо, что и $a,$ и $− a$ являются квадратичными вычетами по модулю $p.$ Из мультипликативности символа Лежандра это означает, что $− 1$ является квадратичным вычетом по модулю $p,$ что верно для простых вида $4k+ 1$ и только для них (следует, например, из критерия Эйлера). Итак, мы доказали, что среди $( )4 14, 24,..., p−21$ есть два равных остатка по модулю $p$ тогда и только тогда, когда $p≡ 1 (mod 4),$ что и требовалось.

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

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

Решите в целых числах уравнение $x2 =y3− 5.$

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

Запишем уравнение в виде $x2+ 4=y3− 1.$ Из такой записи очевидно, что $y > 1.$ Докажем, что $y3 − 1$ всегда делится на некоторое простое $p ≡3 (mod 4).$ Будем пользоваться тем, что любое число, сравнимое с $3$ по модулю $4,$ имеет простой делитель вида $4k +3,$ так как произведение любого набора таких чисел вида $4k+1$ само имеет остаток $1$ по модулю $4.$

(a) $y$ – четное число. В таком случае $y3− 1≡ 3 (mod 4).$ Остается применить утверждение.

(b) $y ≡1 (mod 4).$ В таком случае $2 y +y +1≡ 3 (mod 4).$ Применим утверждение. Так как $3 .. 2 y − 1 . y +y +1,$ оно тоже имеет простой делитель вида $4k+3.$

Итак, $x2+ 4 ... p$ для некоторого $p= 4k +3.$ Значит, $− 4$ является квадратичным вычетом по модулю $p.$ Число $4$ является квадратичным вычетом по любому простому модулю, и из мультипликативности символа Лежандра тогда следует, что $− 1$ является вычетом по модулю $p= 4k+3.$ Однако из общей теории мы знаем, что $− 1$ является вычетом по простому модулю $p$ тогда и только тогда, когда $p= 4k +1.$ Поскольку мы пришли к противоречию, уравнение из условия задачи решений не имеет.

Ответ:

Решений нет

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

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

Докажите, что для любого натурального $n$ любой простой делитель числа $n4− n2+ 1$

(a) сравним с 1 по модулю $4;$

(b) сравним с 1 по модулю $12.$

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

Подсказка 1, пункт а

Как доказывать, что все простые делители числа вида 4k+1? Например, можно сказать, что -1 является квадратичным вычетом. Откуда это взять? Вспомните, в какой формуле сокращенного умножения есть что-то похожее на n^4-n^2+1.

Подсказка 1, пункт б

Как такое можно доказывать? Можно найти показатель числа n по модулю 12. Поймите, что показатель может быть лишь 4 или 12. Но 4 нас не устраивает. Как отсеять этот вариант?

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

(a) Ясно, что $2$ не является делителем $n4− n2+ 1.$ Любой простой нечетный делитель числа $n4− n2+ 1$ является делителем и $n6+ 1,$ так как $n6+1 =(n2+ 1)(n4− n2 +1).$ Итак, если $. n6 +1= (n3)2+ 1.. p,$ то $− 1$ является квадратичным вычетом по модулю $p.$ Как мы уже ни раз отмечали, $− 1$ является квадратичным вычетом по модулю $p$ тогда и только тогда, когда $p =4k+ 1.$

(b) Найдем показатель $T$ числа $n$ по модулю $p.$ Поскольку $6 n ≡− 1 (mod p),$ то $12 n ≡ 1 (mod p),$ значит $.. 12. T.$ Так как $. n6 ≡ −1 (mod p),6 ⁄.. T,$ значит либо $T = 4,$ либо $T = 12.$ Если $T =4,$ то $. n4− 1= (n2+1)(n2 − 1).. p,$ откуда $n2 ≡ ±1 (mod p).$ Тогда $n4− n2+ 1≡ 2± 1⁄≡0 (mod p)$ – противоречие.

Итак, $T = 12.$ Согласно малой теореме Ферма, $p−1 n ≡ 1 (mod p),$ откуда $.. p− 1 . 12$ или $p≡ 1 (mod p)$ – что и требовалось доказать.

Интенсивы

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

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

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

Последовательность натуральных чисел $a,a ,... 1 2$ задана рекуррентно: $a = 3 1$ , $a = a2 i+1 i$ при всех натуральных $i$ . Пусть $2n m = 2 +1.$

(a) Докажите, что $a2n +1$ делится на $m,$ если $m$ — простое;

(b) Докажите, что $a2n + 1$ не делится на $m,$ если $m$ — составное.

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

Подсказка 1, пункт а

В этой задаче можно явно написать формулу a_i. Что делать дальше? Примените критерий Эйлера и воспользуйтесь тем, что 3 не является квадратичным вычетом.

Подсказка 1, пункт б

Вспомните про существование показателя. По какому модулю и какому основанию стоит его рассмотреть?

Подсказка 2, пункт б

Рассмотрите показатель числа 3 по модулю m. Поймите, что он должен быть равен m-1. Почему это плохо? Воспользуйтесь теоремой Эйлера и придите к противоречию.

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

(a) По индукции несложно доказать, что $a= 32i−1 i$ для всех натуральных $i.$ Тогда понятно, что $a n + 1= 322n−1 + 1= 3(m−1)∕2 +1. 2$ Заметим, что $m ⁄≡±1 (mod 12),$ то есть $3$ не является квадратичным вычетом по модулю $m$ . Тогда $(m−1)∕2 3 ≡ −1 (mod m)$ из критерия Эйлера, что и требовалось.

(b) Пусть $m$ — составное число, и выполнена делимость. Отметим, что $3$ и $m$ взаимно просты ( $2n 2 ≡ 1 (mod 3)$ ), поэтому определено понятие показателя $3$ по модулю $m.$ Рассмотрим показатель $d$ числа $3$ по модулю $m.$ Из $22n−1 3 ≡ −1 (mod m)$ получаем $22n 3 ≡ 1 (mod m ),$ откуда $2n 2$ делится на $d,$ то есть $d$ является степенью двойки. С другой стороны из первого сравнения получаем $2n−1 d >2 ,$ откуда $2n d =2 = m − 1.$

Теперь воспользуемся теоремой Эйлера: согласно ей, $. ϕ(m ).. d.$ Поскольку $m$ – составное, то $ϕ(m)< m − 1.$ Получается, что $.. ϕ(m). m − 1,$ но $ϕ(m)< m − 1,$ причем $ϕ(m)$ – натуральное число. Это невозможно, поэтому мы достигли противоречия.

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

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

Решите уравнение в целых числах $x3 − x= 9(5y2− 1).$

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

Перепишем уравнение в виде $(x− 1)x(x+ 1)= 9(5y2− 1).$ Отметим, что правая часть не кратна $27,$ так как $5y2 ≡ 0 (mod 3)$ либо $2 5y ≡ 2 (mod 3).$ Пусть $p$ – простой делитель левой части, не равный $2$ или $3.$ Ясно, что $p⁄= 5,$ так как правая часть уравнения не делится на $5.$ Тогда $2 5y ≡1 (mod p),$ откуда $2 5y ,$ разумеется, является квадратичным вычетом. Из мультипликативности символа Лежандра, $(5y2) (5) (y2) p = p ⋅ p =1.$ Ясно, что $(y2) p = 1,$ поэтому $5$ является квадратичным вычетом по модулю $p.$ Запишем квадратичный закон взаимности:

( 5) 5−1-p−1- (p) p = (−1)2 ⋅ 2 ⋅ 5 = 1

откуда $p$ является квадратичным вычетом по модулю $5.$ Согласно критерию Эйлера, $5−1 p-2-= p2 ≡ 1 (mod 5).$ Таким образом мы получили, что любой простой делитель $(x − 1)x(x+ 1),$ отличный от $2$ и $3,$ сравним с $± 1$ по модулю $5.$

Среди чисел $x − 1, x, x +1$ ровно одно кратно $3,$ поэтому оно же и кратно $9 ≡−1 (mod 5).$ Если какое-то из этих трех чисел является нечетным, то оно сравнимо с $±1$ по модулю $5,$ поскольку оно делится на $3$ в четной степени, а все остальные его простые делители сравнимы с $± 1$ по модулю $5.$ Если $x − 1, x +1$ нечетные, то обязательно $x− 1≡ −1 (mod 5),x +1≡ 1 (mod 5),$ но тогда $.. x . 5,$ хотя правая часть не кратна $5$ – противоречие. Получается, что $x$ – нечетное. По замечанию, $x ≡±1 (mod 5).$ Но тогда либо $x − 1,$ либо $x+ 1$ делится на $5,$ хотя правая часть не кратна $5$ – противоречие.

Выходит, что у $(x− 1)x(x+ 1)$ нет других простых делителей кроме $2$ и $3.$ Так как одно из трех чисел кратно $9,x+ 1≥ 9.$ Два других числа могут быть кратны только двум, поэтому оба должны быть степенью $2$ (причем, из-за неравенства, ненулевой). Ясно, что этими числами обязаны быть $x− 1$ и $x+ 1.$ Две степени двойки отличаются на $2$ только если одна из них равна $2,$ а другая $4.$ В таком случае $x +1= 4,$ что противоречит неравенству выше. Таким образом, у уравнения решений нет.

Ответ:

Нет решений

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

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

Пусть $a ,a,...,a 1 2 p−21$ — все квадратичные вычеты по простому модулю $p> 7.$ Докажите, что $a3+ a3+ ...+ a3 ≡ 0 (mod p). 1 2 p−12-$

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

Подсказка 1

Работая с квадратичными вычетами, полезно написать многочлен x^((p-1)/2)-1. Откуда можно взять тут сумму кубов? Причем тут p>7?

Подсказка 2

Воспользовавшись теоремой Виета, выразите сумму кубов по модулю p. Поймите причем тут p > 7.

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

Рассмотрим многочлен $x(p−1)∕2− 1≡ 0 (mod p)$ над $ℤ . p$ Заметим, что $a$ будет корнем этого многочлена тогда и только тогда, когда $a$ квадратичный вычет по модулю $p.$ Тогда числа $a1,a2,...,ap−21$ и будут корнями этого многочлена.

Простое $p$ больше $7,$ поэтому $p≥ 11,p−21≥ 5.$ Тогда коэффициенты многочлена перед $p−1 p−1- p−1 x( 2 −1),x( 2 −2),x( 2 −3)$ равны нулю.

Из теоремы Виета получим, что:

a1+ a2 +...+ ap−1= 0; ∑ ai⋅aj = 0 2 1≤i<j≤(p−21)

∑ ai⋅aj ⋅ak =0 1≤i<j<k≤(p−21)

Далее выразим сумму кубов

a31+...a3p−1-=(a1+ a2+...+ap−1)3+3(a1+a2+ ...+ an)⋅( ∑ ai⋅aj) 2 2 1≤i<j≤(p−21)

∑ −(3 p−1-ai⋅aj ⋅ak)= 0 1≤i<j<k≤( 2 )

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

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

Найдите все натуральные $m$ и $n,$ удовлетворяющие равенству

n n n n−1 (2 − 1)(2 − 2)...(2 − 2 )= m!

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

Далее в решении, как обычно, $v (N) p$ — показатель наибольшей степени простого числа $p,$ делящей $N.$

Пусть $n n n ( n n− 1) Ln = (2 − 1)(2 − 2)(2 − 4)...2 − 2 .$ Тогда

n n (n n−1) 1+2+⋅⋅⋅+(n−1) n (n−1 ) ( 1 ) Ln =(2 − 1)(2 − 2)⋅⋅⋅2 − 2 = 2 (2 − 1)2 − 1 ⋅⋅⋅ 2 − 1

следовательно,

n(n−-1) v2(Ln)= 1+2 +⋅⋅⋅+ (n− 1) = 2

С другой стороны, по формуле Лежандра, верно неравенство

∞∑ ⌊ ⌋ ∑∞ v2(m!)= mi < mi = m i=1 2 i=12

Приравнивая показатели, имеем

n(n-− 1) 2 = v2(Ln)= v2(m!)< m

Кроме этого заметим, что

Ln = (2n− 1)(2n− 2)⋅⋅⋅(2n − 2n−1)< (2n)n = 2n2

Мы хотим показать, что для всех $n ≥6$ верно

( ) 2n2 < n(n-− 1) 2

что влечет невозможность равенства $Ln = m!$ для указанных $n.$

Для $n =6$ имеем

( ) 262 < 6.9⋅1010 < 1.3 ⋅1012 < 15!< n(n−-1) 2

Пусть $n≥ 7,$ тогда

( n(n − 1)) n(n− 1) n(n−1)−15 --2----!= 15!⋅16⋅17 ⋅⋅⋅--2---->236⋅16 2 = 22n(n− 1)−24 = 2n2 ⋅2n(n−2)−24 >2n2

Таким образом, необходимо проверить выполнение исходного равенства для $n ≤5.$ Имеем

L1 = 1= 1!, L2 = 6= 3!, 5!< L3 = 168 <6!, 7!< L4 = 20160< 8! и 10!< L5 = 9999360< 11!

Наконец, уравнение имеет два решения

(m,n)∈ {(1,1),(3,2)}

Ответ:

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

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

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

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

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

Подсказка 1

Обычно в подобных задачах не нужно сразу применять сильную технику, для начала стоит посмотреть на выражения по каким-нибудь модулям и что-то понять. Изучите n, какие делители у него точно есть?

Подсказка 2

Поймите n по модулю 4. Теперь надо применять что-то сильное, предлагается применить квадратичный закон взаимности. К каким простым числам это можно сделать?

Подсказка 3

Одного квадратичного закона тут не хватает, вспомните про показатели. Где это можно искать? Выделите в числе n наибольшую степень 2, а далее рассмотрите квадратичный закон взаимности для числа 5 и для простого делителя числа 2^n+1, сравнимого по модулю 5 с 2 или 3(почему такой найдется?).

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

Предположим, что $5n− 1$ делится на $2n +1.$ Заметим, что $n$ чётно, ибо иначе $5n− 1$ не делится на $3.$ а $2n+ 1$ делится. Поскольку $2 4m +1$ должно не делиться на $5.$ то $n∕2$ также чётно, т.е. $n$ делится на $4.$ Пусть $m n =2 a,$ где $a$ нечётно, а $n≥ 2.$ Поскольку $n≥ 2,$ то число $m 2 + 1$ сравнимо с $2$ по модулю $5,$ поэтому у него имеется простой делитель $p≡ ±2 (mod 5).$ Поскольку показатель $2$ по модулю $p$ очевидно равен $n 2 + 1,$ мы знаем, что $n p− 1= 2 +1$ для некоторого натурального $k.$

Согласно квадратичному закону взаимности,

( 5) (p) ( ±2) p = 5 = -5- = −1

откуда $52k = 5p−1∕2≡ −1 (mod p)$ и $5m ⁄≡ 1 (mod p).$ С другой стороны, $2m = (22m)a ≡ (−1)a (mod p).$ Таким образом, $2m+ 1$ делится на $p,$ а $5n− 1$ нет, что противоречит предположению.

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

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

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

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

Докажите, что для любого нечетного простого $p$ найдется неприводимый над $ℤ p$ многочлен степени $2.$

Источники: Всеросс., 2006, ЗЭ, 10.2(см. math.ru)

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

Подсказка 1

Пусть дан произвольный многочлен степени 2 в Z_p. В каком случае он имеет корень?

Подсказка 2

Если изначальный вопрос кажется лишком сложным, то рассмотрите частный случай, когда многочлен имеет вид x^2-b.

Подсказка 3

Тогда и только тогда, когда b (или дискриминант исходного уравнения) является квадратичным невычетом по модулю p. Осталось вспомнить почему существует квадратичный невычет по каждому простому модулю

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

Рассмотрим уравнение $x2− b ≡0$ в $ℤ p$ . Его разрешимость эквивалентна тому, что $b$ является квадратичным вычетом. Как известно, существует всего $p− 1 2$ квадратичных вычетов, и столько же невычетов. Тогда в качестве $b$ берем любой невычет и получаем неприводимый многочлен.

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

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

Докажите, что простых чисел вида $4k+ 1$ бесконечно много.

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

Очевидно, что простых чисел бесконечно много. Все простые делятся на 3 группы:
$p =2$ ;
$p =4k+ 1$ ;
$p =4k+ 3$ .
Докажем для начала, что чисел вида $4k +3$ бесконечно много от противного. Пусть $p1$ , ...., $pn$ - все числа вида $4k+ 3$ . Рассмотрим число $4⋅p1⋅...⋅pn− 1$ . У него нет делителей вида $4k+ 3$ и оно нечетно, поэтому все его простые делители вида $4k+ 1$ , но само число сравнимо с -1 по модулю 4. Противоречие.

Вернемся к нашей задаче. Мы знаем, что -1 бывает квадратичным вычетом только по простому числу вида $4k+1$ , поэтому если $. x2+ 1..q$ для нечетного простого $q$ , то $x2 ≡− 1 (mod q)$ , $(−1 ) -q- = 1$ и $q$ — простое число вида $4k+ 1$ . Опять представим, что количество простых чисел вида $4k+ 1$ конечное число и вот они $q1$ , ...., $qm$ . Рассмотрим число $(2q1...qm )2 +1$ , оно не делится на 2, у него нет делителей вида $4k+3$ (так как если $x2+ 1...q$ для нечетного простого $q$ , то $q$ — простое число вида $4k +1$ ) и оно не делится ни на одно простое число $4k+1$ . Противоречие.

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

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

Рождественская теорема Ферма Докажите, что для любого простого числа $p$ вида $4k+ 1$ можно представить, как сумму двух квадратов.

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

Для начала скажем, что для простого числа $p= 4k+ 3$ не существует представления в виде $x2+y2$ . Это так из-за того что квадраты дают только остатки 0 и 1 по модулю 4, а значит $2 2 x +y$ может давать только остатки 0, 1 и 2.

Для начала докажем лемму Туэ.

Лемма Туэ. Пусть $n$ — натуральное число, а $a$ — целое. Тогда найдутся такие целые $x$ и $y$ , что $(x,y)⁄= (0,0)$ , $. ax − y .. n$ , и $√- |x|,|y|≤ n$ .

Доказательство. Рассмотрим такие пары ( $x$ , $y$ ), что $- 0≤x ≤√ n$ , $- 0≤ y ≤ √n$ (исключая (0, 0)). Вариантов для значения $x$ ровно $[√n]+1 >√n-$ (0, 1, ...., [ $√n$ ]) и вариантов для $y$ аналогично > $√n$ , поэтому пар > $n$ или $≥n +1$ , но нам нужно выкинуть (0, 0), поэтому пар $≥ n$ . Для каждой пары можно посчитать значение $ax− y$ и либо у нас найдется такая пара, в которой $ax− y$ делиться на $n$ , либо для всех пар значений $ax − y$ не делится на $n$ . Тогда так как пар хотя бы $n$ , то найдутся 2 пары ( $x1,y1$ ) и ( $x2,y2$ ) такие, что для них $ax1− y1$ и $ax2− y2$ имеет одинаковый остаток по модулю $n$ . Тогда $(ax1− y1)− (ax2− y2)= a(x1− x2)− (y1− y2)$ делиться на $n$ , $√n ≥ x1− x2 ≥ −√n$ и $√n≥ y1− y2 ≥− √n$ , то есть мы нашли подходящие $x= x1− x2$ и $y =y1− y2$ .

Возвращаемся к доказательству теоремы. Так как $p= 4k+1$ , то -1 — кв. вычет по модулю $p$ , поэтому существует такое $a$ , что $a2 ≡ −1 (mod p)$ . Найдем $x$ , $y$ по лемме Туэ для такого $a$ . Имеем $ax ≡ b (mod p)$ , возведем данное сравнение в квадрат и получим $− x2 ≡ (ax)2 ≡ b2 (mod p)$ , возьмем $y = b$ , получаем $x2+ y2 ...p$ и $0 <x2+ y2 < √p2+ √p2 = 2p$ , так как $(x,y)⁄=(0,0)$ и $x⁄= √p$ , потому что $p$ простое и $x$ целое.
$x2+ y2$ от 1 до $2p− 1$ и делится на $p$ , поэтому $x2 +y2 = p$ .