Глава 1. Основные типы уравнений в целых числах.

Введение.

Уравнения в целых числах – это алгебраические уравнения с двумя или более неизвестными переменными и целыми коэффициентами. Решениями такого уравнения являются все целочисленные (иногда натуральные или рациональные) наборы значений неизвестных переменных, удовлетворяющих этому уравнению. Такие уравнения ещё называют диофантовыми, в честь древнегреческого математика Диофанта Александрийского, который исследовал некоторые типы таких уравнений ещё до нашей эры.

Актуальность темы - с целыми числами мы знакомимся с 1 класса, и на протяжении всей жизни так или иначе сталкиваемся с ними. Решение уравнений в целых числах является важной задачей для современной математики, так как эти уравнения тесно связаны со многими проблемами теории чисел.

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

Задачи:

- исследовать основные типы уравнений в целых числах;

- разработать комплекс упражнений и задач.

Объект - задачи в целых числах.

Предмет – способы решения задач и упражнений в целых числах, разбиение по уровням сложности.

Работа содержит в себе две главы. В первой главе представлены определения и теоремы по данной теме, способы решения основных типов уравнений в общем виде.

Вторая глава разбита на 10 параграфом по виду уравнений и способу решений задач в целых числах. Параграфы разбиты на три уровня - от более простого к более сложному. Представлены разобранные задачи и упражнения и в конце каждого параграфа примеры для самостоятельного решения.

Работа была апробирована на различных конференциях: Международная научно-методическая конференция кафедры высшей математики ВГПУ 2015 и 2016 годов, Международная научно-практическая конференция «Молодежный форум: технические и математические науки» 2015 года.

По результатам исследований опубликовано три статьи: ВГПУ -кафедры высшей математики, ВГПУ- сборник победителей студенческой научной конференции, ВГЛТА – актуальные направления научных исследований XXI века: теория и практика. Все сборники включены в Российский индекс научного цитирования.

Глава 1. Основные типы уравнений в целых числах.

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

Некоторые сведения и теории целых чисел.

Пусть - рациональное число, . Пусть . Используя алгоритм Евклида, последовательно получаем:

,

,

,

…

,

.

Соединяя вместе полученные формулы, получаем:

(1.1)

Определение 2.1. Выражение, стоящее в правой части равенства (1.1), называется конечной цепной дробью.

Обозначим .

Замечание. Числа называется коэффициентами цепной дроби (1.1). Из построения ясно, что коэффициент -целое число, а остальные – натуральные числа.

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

Более конкретно, подходящие дроби соответствующего порядка – это дроби вида

, , и т.д.

Ясно, что последняя подходящая дробь есть число .

Применяя метод математической индукции можно доказать следующее утверждение.

Теорема 1.1. Для подходящей дроби k-го порядка имеет место следующая рекуррентная формула:

= (1.2)

Для вычисления подходящих дробей удобно принимать алгоритм, основанный на следующем правиле (см. [9]). Пусть - первые коэффициенты цепной дроби (1.1). Образуем матрицы второго порядка

, , …, .

Справедливо соотношение:

· · …· = (1.3)

Т.е. перемножив указанные матрицы, мы получаем «в перевернутом виде» подходящие дроби и .

Пример.

Найдем все подходящие дроби числа . С помощью алгоритма Евклида раскладываем в цепную дробь:

= [2; 1; 3; 4; 2]

, , , ,

Находим подходящие дроби по формуле (1.3):

· = , , .

Далее,

· = , т.е. ,

· = , т.е. ,

= , т.е. .

Рассмотрим теперь основные свойства подходящих дробей.

1°. Знаменатели подходящих дробей – натуральные числа и образуют неубывающую последовательность, которая со второго члена становится строго возрастающей.

Доказательство.

Действительно,

, где .

Значит,

2°. Числители и знаменатели двух соседних подходящих дробей связаны соотношением:

. (1.4)

Доказательство .

Все матриц, находящиеся в левой части равенства (1.4) имеют определитель, равный . Поскольку определитель произведения матриц равен произведению их определителей, получаем

,

откуда и следует формула (1.4).

3°. Все подходящие дроби несократимы.

Доказательство.

Действительно, если , то согласно (1.4): . Следовательно, .

4°. Подходящие дроби четного порядка образуют возрастающую, а нечетного - убывающую последовательности.

Пользуясь формулами (1.2) и (1.4), получаем:

= .

Таким образом, если четное, получаем , если нечетное, получаем

5°. Каждая подходящая дробь четного порядка меньше соседних подходящих дробей и .

Доказательство.

Рассмотрим разность

то есть . Заменяя на , получаем

, то есть .

Следствие. Каждая подходящая дробь нечетного порядка больше соседних подходящих дробей.

6°. Любая подходящая дробь четного порядка меньше любой подходящей дроби нечетного порядка.

Доказательство.

Рассмотрим подходящие дроби и Пусть сначала . Тогда, на основании свойств 4° и 5°, имеем

.

Пусть теперь . Тогда применяем свойство 4° и следствие, имеем

> > .

Итак, при любом соотношении между и имеем .

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

7°. Если - положительная дробь, то при ее разложении в цепную дробь четные подходящие дроби образуют возрастающие приближения по недостатку, а нечетные - убывающие приближения по избытку.

Доказательство.

Если последняя подходящая дробь, совпадающая с числом , четного порядка, то она (по свойству 4°) больше остальных подходящих дробей четного порядка, которые, таким образом, образуют возрастающие приближения по недостатку. В то же время, по свойству 6°, число меньше любой подходящей дроби нечетного порядка, которые образуют убывающую последовательность приближения по избытку.

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

Рассмотрим теперь вопрос о том, насколько хорошо подходящие дроби приближают число .

8°. Если - положительная дробь и - подходящая дробь порядка, то .

Доказательство.

На основании свойства 7° число заключено между любыми своими соседними подходящими дробями. Поэтому

= .

На основании свойства 1° получаем , более того, заметим, что при это неравенство является строгим.

 

Неопределенные уравнения.

Применяя теперь изученные цепные дроби к решению уравнений вида

a b , (1.5)

где a, b, c- целые числа, , . В качестве равнения (1.5) мы будем рассматривать целые числа x, y. Уравнение типа (1.5) называется неопределенными (или диофантовыми). Такое название связано с тем, что как мы видим, в случае разрешимости уравнения (1.5) имеет бесконечно много решений.

Рассмотрим вопрос о разрешимости уравнения (1.5).

Теорема 1.2. Для существования решения уравнения (1.5) необходимо и достаточно, чтобы c d=(a, b).

Доказательство.

Необходимость. Если ( ) – некоторое решение (1.5), то

, но тогда и c d.

Достаточность. Пусть c d, тогда, сократив коэффициенты a, b, c на d, мы можем считать, что (a, b)=1.

Без ограничения общности полагаем, что . Рассмотрим сначала случай . Разложим в цепную дробь и пусть -соответствующие подходящие дроби. Так как дробь несократима, получаем , . В силу (1.4) имеем , откуда , или . Умножая обе части последнего равенства на , получаем

т.е. числа , , дают решение уравнения (1.5).

Если , то найдем решение ( ) уравнения ax+b’y=c,

где b’=- b. Тогда ( ) будет решением исходного уравнения.

Следствие. Если (a, b)=1, то уравнение (1.5) разрешимо.

Рассмотрим вопрос о нахождении общего решения уравнения (1.5).

Теорема 1.3. Пусть (a, b)=1 и ( ) – некоторое решение уравнение (2.5). Тогда общее решение уравнения (1.5) может быть записано в виде

, , (1.6)

Доказательство.

Необходимость. Покажем, что любая пара чисел (x, y), удовлетворяющих (1.6), дает решение (1.5). Действительно,

a( )+b = a +b .

Достаточность. С другой стороны, пусть(x, y) - произвольное решение уравнения (1.5).

Тогда имеем соотношения

a b ,

a +b .

Вычитая из первого равенства второе, получим

a( +b( )=0, или

a( =-b( ). (1.7)

Поскольку (a, b)=1, левая часть делится на a, то делится на a, т.е. , или , .

Подставляя значение в (1.7), получаем:

a( )=-b , и поэтому

=- , x= - ,

Таким образом, произвольное решение (x, y) уравнения (1.5) имеет вид (1.6). Полученный результат полностью решает вопрос о нахождении всех целочисленных решений уравнения первой степени с двумя неизвестными.

Пример.

Решите в целых числах уравнение

Рассмотрим сначала уравнение

С помощью алгоритма Евклида находим НОД

⇒ по следствию из теоремы 1.2 уравнение разрешимо.

,

, n=4

· = , ;

· = ,

· = , = ;

· =9,

· .

Тогда частное решение исходного уравнения:

Общее решение: ,

Доказательство.

Необходимость.

⇒ ⇒ .

Достаточность. Пусть , , то , или + . Получаем равные остатки.

Свойства сравнений.

1 . Отношение является отношением эквивалентности на множестве , т.е. оно обладает свойством рефлексивности, симметричности и транзитивности.

2 . Сравнения по одному и тому же модулю можно почленно складывать, т.е. если и , то

.

Доказательство.

По критерию имеем и . Тогда по свойствуотношения делимости , что и означает, что

.

Следствие1. К обеим частям сравнения можно прибавить одно и тоже число.

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

3 . Сравнения по одному и тому же модулю можно почленно перемножить, т.е. если и , то

.

Доказательство.

Рассмотрим

Т.к. и , то по свойству отношения делимости , т.е. .

Следствие 1. Обе части сравнения можно умножить на одно и тоже целое число.

Следствие 2. Обе части сравнения можно возводить в одну и ту же натуральную степень.

4 . Обе части сравнения можно разделить на одно и то же число, взаимно простое с модулем, т.е. если и , то

.

Доказательство.

По критерию имеем: , Т.к. , то по свойству взаимно простых чисел т. е. .

5 Обе части сравнения и модуль можно разделить на одно и то же число, т.е. если , то .

Доказательство.

По критерию имеем: , . Следовательно, , или .

6 . Если два числа сравнимы по некоторому составному модулю, то они сравнимы по любому его делителю, т.е. если и , то .

Доказательство.

По критерию имеем: и . Следовательно, по свойству отношения делимости .

7 . Обе части сравнения и модуль можно умножить на одно и тоже натуральное число: если и , то .

Доказательство.

Необходимость непосредственно следует из определения.

Достаточность: Из 2) следует, что каждое из чисел принадлежит некоторому классу вычетов по модулю m и любые два числа принадлежат разным классам вычетов. Кроме того, всего в совокупности m чисел, т.е. столько и должно быть в полной системе вычетов.

Определение 1.5. Если из полной системы вычетов выбрать числа, взаимно простые с модулем m, то получим систему, которая называется приведенной системой вычетов.

Пример. и т.д.

По аналогии с леммой 1.1 легко проверить следующее утверждение.

Лемма 1.2. Совокупность чисел образует приведенную систему вычетов по модулю m тогда и только тогда, когда:

1) числа попарно не сравнимы по модулю m;

2) взаимно простые с модулем m;

3) количество чисел равно , где - функция Эйлера.

Определение 1.6. Количество натуральных чисел, не превосходящих и взаимно простых с называется функцией Эйлера и обозначается .

Пример. =10. Взаимно простые с 10 числа 1, 3, 7, 9. Значит =4.

Замечание. Поскольку (1, 1)=1, полагают =1.

Рассмотрим задачу о вычислении значений функции Эйлера.

Теорема 1.5. Если - простое число, - натуральное число, то .

Доказательство.

Рассмотрим сначала случай . Ясно, что числа 1, 2, …, все взаимно простые с . Следовательно, = .

Пусть В ряду чисел 1, 2, …, , , …, не взаимно простыми с являются лишь числа, простые с , т.е. каждое Всего таких чисел будет = . Таким образом, .

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

Теорема 1.6. Формула Эйлера мультипликативна, т.е. если , то .

Теперь мы можем сформулировать общую теорему о вычислении значений Эйлера.

Теорема 1.7. Пусть - каноническое разложение числа . Тогда .

Доказательство.

Применяя теорему 1.5 и 1.6, получаем: .

Пример. 288= . Это значит, что .

Свойства полной и приведенной системы вычетов.

1 . Пусть . Если и принимает все значения полной системы вычетов по модулю , , …, , то и принимает все значения полной системы вычетов по модулю , , …, .

Доказательство.

Воспользуемся леммой 1.1:

1) Покажем, что при .

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

2) Т.к. принимает значений, то тоже принимает значений.

По аналогии с предыдущим свойством для полной систему вычетов можно получить следующее утверждение.

2 . Пусть . Если и принимает все значения приведенной системы вычетов по модулю , , …, , то и принимает все значения полной системы вычетов по модулю , , …, .

Теорема 1.8 Эйлера. Если , то .

Доказательство.

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

По свойству 3 сравнений имеем , , …, , , …, . Т.к. , то по свойству взаимно простых чисел , , …, . Следовательно, по свойству 4 уравнений, тогда имеем .

Следствие (Теорема Ферма): Если p- просто число и , то или .

Решение сравнений.

Пусть дан многочлен , где .

Определение 1.7. Выражение вида (1.8) называется сравнение с одним неизвестным.

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

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

Теорема 1.9. Если в сравнении (1.8) коэффициенты , заменить числами, сравнимыми с ними по , то полученное сравнение будет равносильно исходному.

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

Данные свойства могут быть использованы для упрощения сравнений.

Пример. Сравнение равносильно сравнению .

Сравнения первой степени.

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

(*), где .

Исследуем вопрос о разрешимости сравнения (1.8) и нахождении его корней. Справедливо следующее утверждение.

Теорема 1.10. Если , то сравнение (1.8) имеет единственное решение.

Доказательство.

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

, с которым оно находится в одном классе вычетов. Ясно, что соответствующие и порождает единственное решение сравнения (1.8).

Теорема 1.11. Если и , то сравнение (1.8) решений не имеет.

Доказательство.

В самом деле, сравнение (1.8) может быть переписано в виде

, , или , откуда, видно, что должно делиться на любой общий делитель и .

Теорема 1.12. Если и , то уравнение (1.8) имеет решений, которые могут быть найдены по формуле:

где и - единственное решение сравнения

, (**)

где , .

Доказательство.

Из свойств 5 и 8 сравнений следует, что сравнения (*) и (**) равносильны.

В сравнении (**) имеем и поэтому, в силу теоремы 1.10, сравнение (**) имеет единственное решение - некоторый класс вычетов по модулю . Это означает, что числа вида

, ,