Сравнения второй степени с одним неизвестным
Курсовой проект - Математика и статистика
Другие курсовые по предмету Математика и статистика
е класса по модулю р будут все одновременно квадратичными вычетами либо квадратичными невычетами.
Свойство 2. ()=1
Доказательство очевидно, ведь единица является квадратом.
Свойство 3. ()=
Доказательство этого свойства следует из критерия Эйлера при а= -1. Так как - четное, если р имеет вид 4n+1, нечетное, если р имеет вид 4n+3, то число -1 является квадратичным вычетом по модулю р тогда и только тогда, когда р имеет вид 4n+1.
Свойство 4. ( ) = ( )( )
Действительно,
( ) ( )( ) ( mod p).
Свойство 4, очевидно, распространяется на любое конечное число сомножителей в числителе символа Лежандра, взаимно простых с р. Кроме того, из него следует свойство 5.
Свойство 5. () = (), т.е. в числителе символа Лежандра можно отбросить любой квадратный множитель.
Действительно, ( ) ( )( ) ( ) 1 ) ( mod p).
3. Методы решения сравнений высшей степени, n?2, с одним неизвестным
1.С использованием свойств сравнения
Пример. Найти однозначное положительное число, 27-я степень которого оканчивается цифрой 7.
, где (7, 10) = 1.
По одному из свойств сравнения аb (mod m), (b, m) = (a, m), отсюда (x, 10) = 1. Применив теорему Эйлера, получим сравнение
,
так как ? (10) = 4. Возведем обе части сравнения в 6-ю степень, после чего придем к сравнению .
Тогда сравнение можно преобразовать следующим образом:
,
.
Так как ( x, 10), то, проверяя подстановкой в последнее сравнение числа 1, 3, 5, 7, 9, находим единственное решение .
Ответ. .
2.Метод подбора
Пример. Решить сравнение .
Решение.
Используем метод проб, подвергая проверке числа, взаимно простые с модулем, т.е. числа 1, 3, 5, 7, 9, 11, 13, 15. Искомые решения:
.
3.С использованием критерия Эйлера
Показать, что произведение двух квадратичных вычетов по простому модулю есть квадратичный вычет по тому же модулю, а произведение квадратичного вычета на невычет есть квадратичный невычет по тому же простому модулю.
Решение.
Если a и b- квадратичные вычеты по модулю p, то на основании критерия Эйлера:
( mod p),
( mod p).
Перемножая эти сравнения, имеем:
( mod p)
и ab- квадратичный вычет по модулю p. Во втором случае
( mod p)
и ab- квадратичный невычет по модулю p.
4. Двучленные сравнения высшей степени, n?2, с одним неизвестным, по простому и составному модулям
.1 Сравнения по простому модулю
Рассмотрим случай, когда модуль - простое число.
Теорема 1. Если числа m? , m? ,… попарно взаимно просты, то сравнение
f ( x ) 0(mod m? m? … ) равносильно системе сравнений:
При этом, если Т? , Т? , ..., - числа решений отдельных сравнений этой системы по соответствующим модулям, то число решений Т исходного сравнения равно Т? Т ?... .
Доказательство. Первое утверждение теоремы (о равносильности системы и сравнения) очевидно, т.к. если a b (mod m) , то a b (mod d), где d делит m. Если же a b (mod m?) и a b (mod m?), то a b (mod HOK (m? , m? )), где НОК ( m? , m? ) - наименьшее общее кратное m? и m?.
Обратимся ко второму утверждению теоремы (о числе решений сравнения).
Каждое сравнение f (x) 0(mod m ) выполняется тогда и только тогда, когда выполняется одно из T s штук сравнений вида x b s (mod m s ), где b пробегает вычеты решений сравнения f ( x ) 0(mod m ). Всего различных комбинаций таких простейших сравнений
Т? Т? ... штук. Все эти комбинации приводят к различным классам вычетов по mod( m? m? … ).
Лемма 1. Произвольное сравнение f(x) 0(mod p) , где р - простое число, равносильно некоторому сравнению степени не выше p-1 .
Доказательство. Разделим f(x) на многочлен - х (многочлен деления круга) с остатком:
(x) =(- х) Q(x) + R(x),
где степень остатка R(x) не превосходит р-1. Но ведь, по теореме Ферма, - х 0 (mod p). Это означает, что f(x) R(x) (mod p), а исходное сравнение равносильно сравнению R(x) 0 (mod p).
При помощи доказанной леммы можно свести решение высокой степени к решению сравнения меньшей степени.
Лемма 2. . Если сравнение а ++…+ 0 ( mod p )
степени n по простому модулю р имеет более n различных решений, то все коэффициенты а, , …, кратны р.
Доказательство. Пусть сравнение а ++…+ 0 (mod p)
имеет n+1 решение и , , …, , - наименьшие неотрицательные вычеты этих решений. Тогда, очевидно, многочлен f(x) представим в виде:
(x) = a (()…()()() + b (()…()() + c (()…() +… + k (() + l ( + m.
Действительно, коэффициент b нужно взять равным коэффициенту при в разности f(x) - a (()…()()(); коэффициент с - это коэффициент перед в разности
(x) - a (()…()()() - b (()…()(), и т.д. Теперь положим последовательно= , , …, , . Имеем:
)f() = m 0 ( mod p), следовательно р делит m;
)f( ) = m + l ( ) l ( 0 (mod p), следовательно p делит l, ибо p не может делить , так как ;
)f() k ( 0 (mod p), следовательно, р делит k.
И так далее.
Получается, что все коэффициенты a, b, c,…, k, l кратны р. Это означает, что все коэффициенты …, тоже кратны р, ведь они являются суммами чисел, кратных р.
Если модуль - число составное, то сравнение n-й степени может иметь и более n решений, при этом коэффициенты многочлена не обязаны быть кранными р.
Всякое нетривиальное сравнение по mod p равносильно сравнению степени не выше р-1 и имеет не более р-1 решений.
Теорема (Вильсон). Сравнение ( р - 1) + 1 0 (mod p) выполняется тогда и только тогда, когда р - простое число.
Доказательство. Пусть р - простое число. Если р = 2, то, очевидно, 1 + 1 0 (mod 2). Если р > 2, то рассмотрим сравнение
[ ( х - 1) ( х - 1)… (х - (р - 1))] - ( - 1)