Сравнения второй степени с одним неизвестным
Курсовой проект - Математика и статистика
Другие курсовые по предмету Математика и статистика
- во многом предопределило дальнейшее развитие этих дисциплин. Гаусс даёт здесь обстоятельную теорию квадратичных вычетов, первое доказательство квадратичного закона взаимности - одной из центральных теорем теории чисел.
"Квадратичный закон взаимности", открытый эмпирически Эйлером (ок. 1772) и доказанный Гауссом (1801), утверждает, что если p и q - различные нечетные простые числа, то каждое из них или является квадратичным вычетом по модулю другого, или это не верно ни для одного из них за исключением случая, когда и p, и q имеют вид 4k + 3 и когда лишь одно из этих чисел является квадратичным вычетом по модулю другого. Теорема Гаусса, названная им "золотой теоремой", служит мощным инструментом теоретико-числовых исследований и позволяет ответить на вопрос, разрешимо ли данное квадратичное сравнение.
Система n-уравнений с n-неизвестными изучались Гауссом. Полное исследование систем линейных сравнений было представлено в работах Фробениуса и Стейница в конце XIX столетия.
Итак, сравнения высших степеней были положены в основу модульного представления числа, которые широко использовались в современной криптографии, и которые до сих пор актуальны в наше время высоких технологий. Большое внимание этому вопросу уделили такие ученые-исследователи, как Риверс, Адельман и Ширман.
Особая трудность, которую во все времена были отмечены задачи теории чисел, заставляла исследователей искать все новые методы в этой ветви математической науки. И в настоящее время мы имеем в теории чисел такое методологическое многообразие, как, пожалуй, ни в одной другой математической дисциплине. Характерной чертой для всех этих методов является сравнительная ограниченность их приложений; каждый такой метод, как правило, может быть применен к решению лишь более или менее узкого круга родственных между собою задач.
2. Определение сравнения n-й степени, n?2, с одним неизвестным, его решения, свойства решений
Рассмотрим двучленные сравнения:
числовой сравнение степень квадратичный
( a, m ) = 1
Если сравнение (1) имеет решение, то а называется вычетом степени n по модулю m. В противном случае а называется невычетом степени n по модулю m. В частности, при n=2 вычет или невычеты называются квадратичными, при n=3- кубическими, при n=4- биквадратичными.
Рассмотрим простейшее двучленное сравнение второй степени вида:а (mod р), где а и р взаимно просты, а р- нечетное простое число.
Условие взаимной простоты (а,р)=1 исключает из рассмотрения случай а=0.
Нас интересует вопрос, при каких простейшее двучленное сравнение второй степени имеет решение, а при каких не имеет. Сравнение а (mod 2) имеет решение при любых а, так как вместо а достаточно подставлять только 0 или 1, а числа 0 и 1 являются квадратами.
Что касается сравнения 0 (mod p), то оно всегда имеет решение х=0.
Определение. Если сравнение а (mod р) имеет решения, то число а называется квадратичным вычетом по модулю р. В противном случае число а называется квадратичным невычетом по модулю р.
Итак, если а - квадрат некоторого числа по модулю р, то а- квадратичный вычет, если же никакое число в квадрате не сравнимо с а по модулю р, то а- квадратичный невычет.
Если а - квадратичный вычет по модулю р, то сравнение а (mod р) имеет в точности два решения. Действительно, если а - квадратичный вычет по модулю р, то сравнения а (mod р) есть хотя бы одно решение ( mod p). Тогда - тоже решение, ведь =. Эти два решения не сравнимы по модулю р>2, так как из ( mod p) следует 2 ( mod p) , т.е. ( поскольку р2) ( mod p), что невозможно, ибо а0. Поскольку сравнение а (mod р) есть сравнение второй степени по простому модулю, то больше двух решений оно иметь не может.
Приведенная система вычетов
,…, -2, -1, 1, 2, …,
По модулю р состоит из квадратичных вычетов, сравнимых с числами , ,…, , и квадратичных невычетов, т.е. вычетов и невычетов поровну.
Действительно, квадратичные вычеты сравнимы с квадратами чисел
,…, -2, -1, 1, 2, …, ,
т.е. с числами , ,…, , при этом все эти квадраты различны по модулю р, ибо из ( mod p), где 0<k<l, следует, что нетривиальное сравнение ( mod p) имеет аж четыре решения : l, -l, k, -k, что невозможно.
Фраза Число а является квадратичным вычетом ( или невычетом) по модулю р несколько длинновата. Адриен - Мари Лежандр предложил выход, введя в рассмотрение удобный символ ( заменяющий длинную фразу. Этот символ носит теперь фамилию Лежандра и читается: символ Лежандра а по пэ.
Определение. Пусть а не кратно р. Тогда символ Лежандра определяется так:
Теорема ( критерий Эйлера). Пусть а не кратно р. Тогда
) ( mod p)
Доказательство. По теореме Ферма, 1 ( mod p), т.е.
В левой части последнего сравнения в точности один сомножитель делится на р, ведь оба сомножителя на р делится не могут, иначе их разность, равная двум, делилась бы на р>2. Следовательно, имеет место одно и только одно из сравнений:
Но всякий квадратичный вычет а удовлетворяет при некотором х сравнению
а(mod p) и, следовательно, удовлетворяет также получаемому из него почленным возведением в степень сравнению 1 (mod p). При этом квадратичными вычетами и исчерпываются все решения сравнения 1 (mod p), так как, будучи сравнением степени , оно не может иметь более решений. Это означает, что квадратичные невычеты удовлетворяют сравнению 1 (mod p).
Свойство 1. Если аb (mod p), то ( )= ()
Это свойство следует из того, что числа одного и того ж