Читайте также

Главная  Лучшие    Популярные   Список   Добавить
Статьи » Математика » Алгебра

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

Алгебра Пусть a,b-целые числа, n - натуральное. Рассмотрим сравнение:
ax?b (mod n)
и поставим задачу отыскания всех целочисленных решений этого сравнения. Допустим, что xo-это решение.
ax0=b+nu для некоторого целого u.
Пусть d=(a,n)
Видно, что условие d делит b является необходимым для того, чтобы сравнение имело решения.
Как мы увидим позже, это условие является так же достаточным.

Рассмотрим сначала случай, когда d=1 , т.е (a,n)=1. Пусть [b]n - остаток от деления числа b на n.
Тогда [b]n?Zn.
Множество {[ax]n l x?Zn} совпадает с множеством Zn, поскольку является полной системой вычетов.
Поэтому найдется такое xo?Zn, что [axo]n=[b]n. Отсюда,
axo?b(mod n)
Стало быть, сравнение ax?b (mod n) имеет решение xo.
Покажем, что формула x=xo+nt ,t?Z,
позволяет получить любое решение сравнения ax?b (mod n).
В самом деле, если x - решение сравнения, то вычитая из ax?b (mod n) сравнение axo?b (mod n) получим:
a(x-xo)?0 (mod n), тоесть nla(x-xo). Поскольку (n,a)=1, то nl(x-xo) => x=xo+nt . #.

Теперь рассмотрим случай, когда d=(n,a)>1. Пусть a=a1d, b=b1d, n=n1d, причем (a1,n1)=1.
Рассмотрим сравнение a1x?b1 (mod n1). Понятно, что это сравнение равносильно с исходным ax?b (mod n).
Однако, сравнение a1x?b1 (mod n1) мы уже решать умеем. Его множество решений описывается формулой x=xo+n1t, где
xo- решение сравнения a1x?b1 (mod n1), лежащее между 0 и n1-1, а t-произвольное число.

Приведем пример решения сравнений:
17x?55 (mod 37)

Пользуясь алгоритмом Евклида найдем все такие целые числа u и v, что 17u+37v=1. Имеем:
37=17*2+3
17=5*3+2
3=2*1+1

Отсюда:

1=3-1*2=3-1*(17-5*3)=6*3-17=6(37-2)=6-13*7.
Таким образом, 17(-13)?1 (mod 37)

Умножая последнее сравнение на 55 и учитывая, что -13(55)=-715?-12?25 (mod 37), получаем, что 25-xo. => x=25+37t, t принадлежит Z.

Дополнительно по данной категории

11.03.2010 - История квадратных уравнений манэ
11.03.2010 - Квадратные уравнения
10.03.2010 - Упрощение уравнений и сведение к линейному
10.03.2010 - Упрощение уравнений и сведение к линейному
10.03.2010 - Линейные уравнения
Нет комментариев. Почему бы Вам не оставить свой?
Ваше сообщение будет опубликовано только после проверки и разрешения администратора.
Ваше имя:
Комментарий:
Смайл - 01 Смайл - 02 Смайл - 03 Смайл - 04 Смайл - 05 Смайл - 06 Смайл - 07 Смайл - 08 Смайл - 09 Смайл - 10 Смайл - 11 Смайл - 12 Смайл - 13 Смайл - 14 Смайл - 15 Смайл - 16 Смайл - 17 Смайл - 18
Секретный код:
Секретный код
Повторить:

Поиск по сайту

Поиск

Авторизация


Добро пожаловать,
Аноним

Регистрация или входРегистрация или вход
Потеряли пароль?Потеряли пароль?

Ник:
Пароль:


Содержание:1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
Правообладателям
Образование