Сравнения второй степени с одним неизвестным

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Введение

Методы теории сравнений широко применяются в различных областях науки, техники, экономики. Этот раздел алгебры занимает важное место в вузовском образовании математиков, физиков и других специалистов, однако очень часто изучается недостаточно глубоко. Задача данной курсовой работы - изучить теоретический материал и рассмотреть ряд основополагающих задач по одному из основных разделов теории чисел: сравнения высших степеней, двучленные сравнения высшей степени, n?2, с одним неизвестным, по простому и составном модулям и т.д.

Основная часть курсовой работы состоит из четырех глав. Вторая глава состоит из 4 параграфов. В первом параграфе раскрывается краткий исторический обзор возникновения развития числовых сравнений и сравнений высших степеней с одним неизвестным. Во втором параграфе рассматриваются определение сравнения n-й степени, n?2, с одним неизвестным, его решения, свойства решений.

В третьем параграфе рассматриваются методы решения сравнений высшей степени, n?2, с одним неизвестным. Далее рассматриваются двучленные сравнения высшей степени, n?2, с одним неизвестным, по простому и составному модулям.

В практической части приводятся примеры решения текстовых задач, которые решаются с помощью сравнений.

В работе приводится список литературы по теме « Сравнения второй степени с одним неизвестным».

Цель:

Изучить теоретический материал по теме «Сравнения второй степени с одним неизвестным», развить умение применять знания в решении практических заданий, развить интерес к изучению математики.

Задачи:

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

§1. Краткий исторический обзор возникновения и развития числовых сравнений и сравнений высших степеней с одним неизвестным

Важное место в курсе теории чисел имеют сравнения, и, тем более, сравнения высших степеней. Но до того как они начали развиваться, математики разных стран на протяжении ста лет изучали уравнения первой степени.

Уравнения первых степеней начали изучать еще индусские математики приблизительно с V столетия. Некоторые уравнения с двумя и тремя неизвестными появились в связи с проблемами, которые возникли в астрологии. Например, при рассмотрении вопросов, связанных с определением периодического появления небесных явлений.

В другом издании книги французского математика Баше де Мезирьяка “Problemis plaisans et delectables que se font par les nombres”, которая вышла в 1624 году, рассматривается неопределенное уравнение ax+by=c .

Баше де Мезирьяк фактически применяет процесс, который приводит к последующему вычислению неполных частей и рассмотрения дополнительных дробей. Но он не рассматривал непрерывные дроби как таковые.

Известная работа Баше де Мезирьяка оказала сильное влияние на развитие теории чисел, так как способствовала возникновению интереса к этой области математики.

Цепные дроби к решению таких уравнений были применены Лагранжем, который, однако, акцентирует внимание на то, что это фактически тот же способ, который был дан Баше де Мезирьяком и другими математиками, которые разглядели неопределенное уравнение до него.

Неопределенные уравнения первой степени стали записывать и решать в форме сравнений значительно позднее, начиная с Гаусса. Он впервые систематизировал теорию и определил понятие сравнения в своей книге “Disquisitiones arithmeticae” («Достижения в арифметике»). В «Disquisitiones arithmeticae» Гаусс изложил всё существенное, что было известно в теории чисел до него, но часто исходя из более общих и более принципиальных соображений. Кроме того, «Disquisitiones arithmeticae» в четвёртом, пятом и седьмом своих разделах содержат три крупнейших открытия самого Гаусса: доказательство квадратичного закона взаимности, композицию классов и родов квадратичных форм и теорию деления круга. Квадратичный закон взаимности является центральной теоремой теории квадратичных вычетов, доказательство которой долго и безуспешно пытались получить крупнейшие математики того времени. Исследования Гаусса по квадратичному и, позже, по биквадратичному закону взаимности послужили исходным пунктом длинного ряда работ, приведших в конечном итоге к отысканию общего закона взаимности, представляющего собой одну из важных теорем теории алгебраических чисел.

Отношение, называемое сравнением, было введено К.Гауссом (1777-1855). К. Гаусс создаёт теорию сравнений, называемую иначе арифметикой остаточных классов, с помощью которой были доказаны теорема о том, что простое число является суммой двух квадратов тогда и только тогда, когда оно имеет вид 4n + 1, и теорема о представимости каждого натурального числа суммой четырёх квадратов целых чисел. Кроме того, теория сравнений привела к важным понятиям теоретико-числового характера и тригонометрической суммы. Простейшим характером является символ Лежандра.

К. Гаусс изучил свойства квадратичных вычетов и невычетов. Основной теоремой в этом круге вопросов является так называемый квадратичный закон взаимности. Первое крупное сочинение Гаусса по теории чисел и высшей алгебре -- "Арифметические исследования" (1801) -- во многом предопределило дальнейшее развитие этих дисциплин. Гаусс даёт здесь обстоятельную теорию квадратичных вычетов, первое доказательство квадратичного закона взаимности -- одной из центральных теорем теории чисел.

"Квадратичный закон взаимности", открытый эмпирически Эйлером (ок. 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), то ( )= ()

Это свойство следует из того, что числа одного и того же класса по модулю р будут все одновременно квадратичными вычетами либо квадратичными невычетами.

Свойство 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, с одним неизвестным, по простому и составному модулям

4.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) на многочлен - х («многочлен деления круга») с остатком:

f (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) представим в виде:

f(x) = a (()…()()() + b (()…()() + c (()…() +… + k (() + l ( + m.

Действительно, коэффициент b нужно взять равным коэффициенту при в разности f(x) - a (()…()()(); коэффициент с - это коэффициент перед в разности

f(x) - a (()…()()() - b (()…()(), и т.д. Теперь положим последовательно

x = , , …, , . Имеем:

1) f() = m 0 ( mod p), следовательно р делит m;

2) f( ) = m + l ( ) l ( 0 (mod p), следовательно p делит l, ибо p не может делить , так как ;

3) 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) 0 ( mod p).

Ясно, что это сравнение степени не выше р - 2, но оно имеет р - 1 решение : 1, 2, 3,…, р - 1, так как при подстановке любого из этих чисел, слагаемое в квадратных скобках обращается в ноль, а - 1) сравнимо с нулем по теореме Ферма ( х и р взаимно просты, так как х < р). Это означает, по лемме 2, что все коэффициенты выписанного сравнения краны р, в частности, на р делится его свободный член, равный 1*2*3*…*( р - 1) + 1.

Обратно. Если р - не простое, то найдется делитель d числа р, l < d < p. Тогда ( р - 1) делиться на d, поэтому ( р - 1) + 1 не может делиться на d и, значит, не может делиться также и на р. Следовательно, сравнение

( р - 1) + 1 0 (mod p) не выполняется.

4.2 Случай составного модуля.

Сравнение

(1)

где - произвольный многочлен с целыми коэффициентами,

, n > 1 и попарно простые, равносильно системе:

 (2)

Замечание. Число решений сравнения (1) равно произведению числа решений каждого из сравнений системы (2). Если хотя бы одно из сравнений системы (2) не имеет решений, то система несовместна и, следовательно, сравнение (1) не имеет решений.

Сравнение вида

()

где - целые положительные, а - простые числа, также равносильно системе:

()

Решение этой системы сводится к решению сравнений вида

, (3)

решение которой, в свою очередь, начинается с решения сравнений

. (4)

Путем непосредственных испытаний вычетов по модулю p находятся все решения сравнения (4). Пусть

- (5)

одно из решений сравнения (4). Для этого решения составляется сравнение

( - первая производная функции f(x) при ), из которого находится , или ( при , не делящимся на p). После подстановки значения в равенство (5) находим:

. (6)

Далее решается сравнение , из которого находим или , и после подстановки в (6) получим:

. (7)

Вычисление продолжаем до тех пор, пока не получим , или

. (8)

Решение (8) и является решением сравнения (3).

Если окажется, что делится на р, то решения для не будет, следовательно, и решение (5) не будет решением сравнения (3).

Практическая часть

1) Заменить сравнение - 10х + 13 0 (mod 59)

эквивалентным сравнением с коэффициентом при старшем члене, равным 1.

Решение.

Решаем сравнение 27 1 (mod 59) и находим = 35. Данное нам сравнение эквивалентно сравнению

0 (mod 59),

т. е. сравнению 0 (mod 59).

Ответ. 0 (mod 59).

2) Сравнение 0 (mod 7)

заменить эквивалентным сравнением степени, меньшей, чем 7.

Решение.

Заменим на = , на , на х. Таким образом, заданное сравнение эквивалентно сравнению

0 (mod 7),

т. е. сравнению 0 (mod 7).

Ответ. 0 (mod 7).

3) = 31 удовлетворяет сравнению 11 65 (mod 103).

Найти все решения этого сравнения.

Решение.

Очевидно, что вместе с классом этому сравнению удовлетворяет класс . Коэффициент при старшем члене 11 не делится на простой модуль 103, поэтом сравнение не может иметь больше двух решений.

Ответ. .

4) Сравнению удовлетворяют классы . Имеет ли это сравнение еще одно решение?

Решение.

Деля на

1),

так что r(х) = 0, и, следовательно, это сравнение имеет три решения.

Ответ. Сравнение имеет три решения.

4) Сколько решений имеет сравнение: ?

Решение.

Имеем .

Поэтому и 5 - квадратичный вычет по модулю 29 (сравнение имеет 2 решения).

Ответ. Сравнение имеет 2 решения.

6) Сколько решений имеет сравнение:

Решение.

Имеем .

Поэтому и 3 - квадратичный невычет по модулю 29 (сравнение не имеет решений).

Ответ. Сравнение не имеет решений.

7) Решить сравнение: .

Решение.

Испытывая вычеты 1, 2, 3 находим:

.

Ответ. .

8) Решить сравнение, предварительно приведя его к двучленному сравнению.

.

Решение.

Умножив все члены сравнения на 12, получим:

или

,

где y = .

Сравнение имеет решения y

Теперь для решения исходного сравнения надо решить сравнения:

6x+7 2

6x+7 -2

решая которые, получаем

 ( mod 17).

9) Решить сравнение .

Решение.

Умножим обе части сравнения на число 20, где (20,11) = 1. Получим сравнение

,

.

Обозначим = z. Итак, , или .

Решим это сравнение методом проб. Испытывая числа 0,1,2,…,10, видим, что сравнение имеет решения: z=2 и z=9, т.е.

z = 2 + 11t и z = 9 + 11t.

Т.к. , то , т.е.

, ;

при t = 9 имеем и при t = 2 .

Данное решение имеет решения 3 и 10,т.е. ему удовлетворяют целые числа вида:

,

Ответ. ,

.

10) Решить сравнение:

.

Решение.

Используем метод проб, подвергая проверке числа, взаимно простые с модулем, так как (1,16)=1, т.е. числа 1, 3, 5, 7, 9, 11, 13, 15. Искомые решения:

, , , .

Ответ. , , , .

Заключение

В работе изложены основы теории сравнений. Задача данной курсовой работы разработка учебного пособия, которое содержит достаточный теоретический и практический материал.

В данной работе достаточно полно изложены основные моменты теории, они иллюстрируются примерами, которые позволяют глубже понять рассматриваемые вопросы.

Материал курсовой работы может быть использован как при изучении соответствующего курса теории чисел, так и для спецкурсов по алгебре, в частности, для тех специальностей, на которых нет курса теории чисел, уже на младших курсах обучения.

Приведенный список литературы позволяет при необходимости рассмотреть некоторые более сложные моменты теории сравнений и их приложений.

Литература

1. Бухштаб А.А. «Теория чисел»- М.: «Просвещение» 1966

2. Александров П.С., Маркушевич А.И., Хинчин А.Я. «Энциклопедия элементарной математики», Кн.1 . Арифметика - М.: 1965 Ленинград

3. Грибанов В.У., Титов П.И. «Сборник упражнений по теории чисел»

4. Кудреватов Г.А. Сборник задач по теории чисел. М., « Просвещение», 1970.

5. Куликов Л.Я., Москаленко А.И., Фомин А.А. Сборник задач по алгебре и теории чисел - М.: Просвещение, 1993.

6. А.А. Кочева Задачник-практикум по алгебре и теории чисел, часть 3 - М.: « Просвещение» 1984

7. Сизый С.В. « Лекции по теории чисел»

8. Грибанов В.У., Титов П.И. Сборник упражнений по теории чисел, «Просвещение», Москва 1964

Размещено на Allbest.ru