Сравнения первой степени. Линейные диофантовы

Уравнения.

Пусть а, b – целые числа, m – натуральное число. Говорят, что а сравнимо с b по модулю m, если делится на m. В этом случае будем писать

Приведем основные свойства сравнений:

1) ;

2) если , то ;

3) если , , то ;

4) если , то ;

5) если , то ;

6) если , то ;

7) если , , то ;

8) если , то для любого натурального n;

9) если , многочлен с целыми коэффициентами, то ;

10) ,…, тогда и только тогда, когда ;

11) если и m делится на d, то ;

12) если и n делится на k, то

Пусть а, b – целые числа, m – натуральное число. Сравнение называется разрешимым, если существует целое число такое, что В этом случае число называется решением сравнения .

Сравнение разрешимо тогда и только тогда, когда b делится на (a, m). Причем, если - это одно из решений сравнения , то множество всех решений этого сравнения имеет вид , т.е.

Вышеуказанное решение линейного сравнения позволяет найти все решения линейного диофантова уравнения где – целые числа, Диофантово уравнение имеет решение в целых числах x, y тогда и только тогда, когда с делится на (a,b). Причем, если это одно из решений этого уравнения, то множество всех решений задается в виде где t пробегает множество всех целых чисел. Частное решение можно найти с помощью алгоритма Евклида. Индукцией по числу переменных аналогичным образом можно решить линейное диофантово уравнение от n переменных

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

Пример 1. Решите сравнение

Решение. С помощью алгоритма Евклида найдем частное решение исходного сравнения. Имеем 84=15·5+9,15=9·1+6,9=6·1+3,6=3·2+0. Поэтому 3=9–6·1=9–(15–9·1)·1=9·2–15·1=(84–15·5)·2–15·1=84·2+15·(–11), следовательно, 39=3·13=84·26+15·(–143), т.е. 15·(–143)≡39(mod 84), значит, Поэтому множество всех решений исходного сравнения имеет вид т.е.

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

Решение. Зафиксируем переменную и рассмотрим исходное уравнение как диофантово уравнение относительно переменных . Уравнение разрешимо тогда и только тогда, когда , то есть при Поэтому . Найдем частное решение . Используя алгоритм Евклида, находим линейное разложение наибольшего общего делителя чисел 6 и 10:

. Поэтому , . Общее решение исходного уравнения: , где

Ответ: , где

Пример 3. Решите систему сравнений

Решение. Преобразуем исходную систему:

К последней системе применим китайскую теорему об остатках. Найдем частные решения сравнений , , . Имеем . Поэтому решение исходной системы имеет вид: , то есть

Пример 4. Решите систему уравнений в целых числах.

Решение. Решаем систему методом Гаусса:

.

Откуда следует, что , . Следовательно, , т.е. Окончательно получаем ,

2.1. Решите следующие сравнения:

1) , 2) , 3) ,

4) .

2.2. Решите следующие уравнения в целых числах:

1) 2) , 3) ,

4) , 5) .

2.3. Решите следующие уравнения в целых числах:

1) , 2) ,

3) ,4) .

2.4. Пусть - целые числа, не все из которых равны 0.

1) Докажите, что уравнение разрешимо в целых числах тогда и только тогда, когда .

2) Пусть - частное решение неоднородного уравнения , - линейно независимые решения однородного уравнения . Докажите, что общее решение неоднородного уравнения задается формулой , где - произвольные целые числа.

2.5. Используя китайскую теорему об остатках, решите следующие

системы сравнений:

2) 3)

5) 6)

8) 9) .

2.6. Решите следующие системы уравнений в целых числах:

1) 2)

3) 4)

2.7. Найдите все натуральные решения уравнения .

2.8. Докажите, что уравнение не имеет решений в натуральных числах.

2.9. Пусть - целые числа, удовлетворяющие равенству

. Докажите, что

2.10. Докажите, что уравнение не имеет решений в целых числах.

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

2.12. Докажите, что для любых натуральных найдутся целые числа , такие, что уравнение имеет единственное решение , в натуральных числах.

2.13. Найдите все простые числа и натуральные числа , удовлетворяющие уравнению .

Функция Эйлера.

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

По определению полагается

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

Пусть m – натуральное, а а – целые числа и то (теорема Эйлера).

Следствием теоремы Эйлера является теорема Ферма: если p – простое, а а – целые числа, причем то Теорему Ферма можно сформулировать иначе: пусть p – простое число, а – целое число, тогда

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

Пример 1. Используя теорему Ферма, вычислите остаток при делении на 29.

Решение. Имеем .

Пример 2. Используя теорему Эйлера и китайскую теорему об остатках, найдите остаток при делении на 96.

Решение. Пусть , тогда

Используя теорему Эйлера, находим, что

Далее

Используя китайскую теорему об остатках, находим .

3.1. Вычислите: 1) 2) 3) , 4) , 5) .

3.2. Сколько чисел от 1 до 120 не взаимно просты с числом 30?

3.3. Пусть p, q – простые числа, Найдите p, q.

3.4. Пусть а, b – взаимно простые натуральные числа, р – простое число, Докажите, что не делится на р.

3.5. Найдите все простые числа р такие, что

1) числа также являются простыми;

2) числа также являются простыми.

3.6. Пусть n – нечетное натуральное число. Докажите, что делится на n.

3.7. Используя теорему Ферма, вычислите следующие остатки:

1) , 2) , 3) ,

4) .

3.8. Используя теорему Ферма и китайскую теорему об остатках, вычслите следующие остатки:

1) 2) , 3) ,

4) , 5) .

3.9. Используя теорему Эйлера, вычислите следующие остатки:

1) , 2) , 3) ,

4) , 5) .

3.10. Используя теорему Эйлера и китайскую теорему об остатках, вычислите следующие остатки:

1) , 2) , 3) ,

4) .

3.11. Докажите, что для любого простого числа и любого целого числа сравнение разрешимо.

3.12. Найдите все натуральные числа , для которых делится на .

3.13. Докажите, что для простых и натуральных равенство

невозможно.

3.14. Пусть натуральные числа и таковы, что делится на для любого натурального . Докажите, что .

3.15. Найдите все простые числа , такие, что делится на .

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

1) , 2) .

3.17. Докажите, что существует бесконечно много простых чисел вида

.