Эта статья входит в число добротных статей

Соотношение Безу

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

В теории чисел соотноше́ние Безу́ — соотношение между парой целых чисел и их наибольшим общим делителем (НОД), названное в честь французского математика Этьена Безу:

Пусть a, b — целые числа, хотя бы одно из которых не нуль. Тогда существуют такие целые числа ~x, y, что выполняется соотношение:

НОД(a, b) = x \cdot a + y \cdot b.

Другими словами, наибольший общий делитель чисел ~a, b можно всегда представить как линейную комбинацию a и b с целыми коэффициентами[1].

Соотношение НОД(a, b) = x \cdot a + y \cdot b называется соотношением Безу (для чисел a и b), а целые числа ~x, y — коэффициентами Безу. В зарубежных источниках это утверждение может называться леммой Безу или тождеством Безу[2].

Пример: НОД(12, 30) = 6. Соотношение Безу имеет вид:

6=3 \cdot 12 + (-1) \cdot 30

Возможны и другие варианты разложения НОД, например: 6=(-2) \cdot 12 + 1 \cdot 30.

Следствия[править | править вики-текст]

Если числа a, b взаимно простые, то уравнение:

ax+by=1

имеет целочисленные решения[3]. Этот важный факт облегчает решение диофантовых уравнений первого порядка.

НОД(a, b) является наименьшим натуральным числом, которое может быть представлено в виде линейной комбинации чисел a и b с целыми коэффициентами[4].

Множество целочисленных линейных комбинаций \{ax+by\} совпадает с множеством кратных для НОД(a,b))[5].

Коэффициенты Безу[править | править вики-текст]

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

Неоднозначность[править | править вики-текст]

Нахождение коэффициентов Безу эквивалентно решению диофантового уравнения первого порядка с двумя неизвестными:

a x  + b y = d, где d= НОД(a, b).

Или, что то же самое:

\frac{a}{d}\ x  + \frac{b}{d}\ y = 1

Отсюда следует, что коэффициенты Безу x, y определены неоднозначно — если какие-то их значения x_0. y_0 известны, то всё множество коэффициентов даётся формулой[6]:

 \left\{ \left(x_0+\frac{kb}{d},\ y_0-\frac{ka}{d}\right) \mid k =0, \pm 1, \pm 2, \pm 3 \dots \right\}

Ниже будет показано, что существуют коэффициенты Безу, удовлетворяющие неравенствам |x| < \left |\frac{b}{d}\right | и |y| < \left |\frac{a}{d}\right |.

Вычисление коэффициентов с помощью алгоритма Евклида[править | править вики-текст]

Для нахождения коэффициентов Безу можно использовать алгоритм Евклида нахождения НОД и представить остатки в виде линейных комбинаций a и b[7]. Шаги алгоритма записываются в следующем виде:

r_1 = a - bq_0

r_2 = b - r_1q_1 = b - (a - bq_0)q_1 = b(1 + q_0q_1) - aq_1

r_3 = r_1 - r_2q_2 = (a - bq_0) - (b(1 + q_0q_1) - aq_1)q_2 = a(1 + q_1q_2) - b(q_0 + q_2 + q_0q_1q_2)

r_n = r_{n-2} - r_{n-1}q_{n-1} = ... = ax + by.

Пример

Найдём соотношение Безу для a=991, b=981. Формулы алгоритма Евклида имеют вид:

991 = 1 \cdot 981 + 10
981 = 10 \cdot 98 + 1
10 = 10 \cdot 1

Таким образом, НОД(991, 981) = 1. Из этих формул получаем:

10 = 991 - 1 \cdot 981
1 = 981 - 10 \cdot 98 = 981 - 98 \cdot ( 991 - 981 ) = 99 \cdot 981 - 98 \cdot 991

В итоге соотношение Безу имеет вид:

1 = 99 \cdot 981 - 98 \cdot 991

Вычисление коэффициентов с помощью непрерывных дробей[править | править вики-текст]

Альтернативный (по существу эквивалентный) способ решения уравнения ~a x  + b y = d использует непрерывные дроби. Разделим обе части уравнения на НОД: a_1 x  + b_1 y = 1. Далее разложим ~\frac{|a_1|}{|b_1|} в непрерывную дробь и подсчитаем подходящие дроби ~\frac{p_k}{q_k}. Последняя (n-я) из них будет равна ~\frac{|a_1|}{|b_1|} и связана с предыдущей обычным соотношением:

p_n q_{n-1} - q_n p_{n-1} = (-1)^{n-1}

Подставив в эту формулу p_n =a_1;\ q_n =b_1 и умножив обе части на d, получаем:

a q_{n-1} - b p_{n-1} = \pm d

С точностью до знака, это соотношение Безу. поэтому предпоследняя подходящая дробь ~\frac{p_{n-1}}{q_{n-1}} даёт модули решения: |x| есть знаменатель этой дроби, а |y| — числитель. Осталось, исходя их первоначального уравнения, найти знаки ~x, y; для этого достаточно найти последние цифры в произведениях |ax|, |by|[8].

Минимальные пары коэффициентов[править | править вики-текст]

Приведенный в предыдущем разделе алгоритм через непрерывные дроби, как и эквивалентный ему алгоритм Евклида, даёт в результате пару (x,y), удовлетворяющую неравенствам:

|x| < \left |\frac{b}{d}\right |; \; |y| < \left |\frac{a}{d}\right |

Этот факт следует из того, что дроби ~\frac{|y|}{|x|} и ~\frac{|a_1|}{|b_1|}, как указано выше, образуют последовательные подходящие дроби, а числитель и знаменатель следующей подходящей дроби всегда больше, чем у предыдущей[8] [9]. Для краткости можно назвать такую пару минимальной, таких пар всегда две.

Пример. Пусть a=12, b=42. НОД (12, 42) = 6. Ниже приведены некоторые элементы списка пар коэффициентов Безу, причём минимальные пары выделены красным цветом.


\begin{align}
\dots \\
12 &\times \color{blue}{-10} & + \;\; 42  &\times \color{blue}{3} &= 6 \\
12 &\times \color{red}{-3} & + \;\;42  &\times \color{red}{1} &= 6 \\
12 &\times \color{red}{4}  & + \;\;42  &\times\color{red}{-1} &= 6 \\
12 &\times \color{blue}{11} & + \;\;42  &\times \color{blue}{-3} &= 6 \\
12 &\times \color{blue}{18} & + \;\;42  &\times \color{blue}{-5} &= 6 \\
\dots
\end{align}

Применение[править | править вики-текст]

Соотношение Безу часто используется как лемма в ходе доказательства других теорем (например, основной теоремы арифметики[10]), а также для решения диофантовых уравнений и сравнений по модулю.

Решение диофантовых уравнений первой степени[править | править вики-текст]

Рассмотрим решение в целых числах диофантовых уравнений вида:

ax + by = c

Обозначим d=НОД(a, b). Очевидно, уравнение имеет целочисленные решения только в том случае, когда c делится на d. Будем считать это условие выполненным и одним из приведенных выше алгоритмов найдём коэффициенты Безу x, y:

ax + by = d

Тогда решением исходного уравнения будет пара[8] c_1 x, c_1 y, где c_1=c / d.

Решение сравнений первой степени[править | править вики-текст]

Для решения сравнений первой степени:

ax \equiv b \pmod {m}.

его достаточно преобразовать к виду[5]:

ax + my = b

Практически важным частным случаем является нахождение обратного элемента в кольце вычетов, то есть решение сравнения:

ax \equiv 1 \pmod {m}.

Обобщения[править | править вики-текст]

Соотношение Безу легко обобщается на случай, когда имеется более двух чисел[1]:

Пусть a_1, …, a_n — целые числа, не все равные нулю. Тогда существуют такие целые числа x_1, …, x_n, что выполняется соотношение:

НОД(a_1, …, a_n) = x_1\cdot a_1 + \cdots x_n\cdot a_n


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

Пример: формулировка для кольца многочленов (от одной переменной):

Пусть \left(P_i\right)_{i\in I} — какое-либо семейство многочленов, и не все они равны нулю. Обозначим \Delta их наибольший общий делитель. Тогда существует такое семейство многочленов \left(A_i\right)_{i\in I}, что выполняется соотношение:

\Delta = \sum_{i\in I} A_iP_i


Коэффициенты Безу для двух многочленов от одной переменной могут быть вычислены аналогично изложенному выше для целых чисел (с помощью расширенного алгоритма Евклида)[11]. Общие корни двух многочленов являются корнями также и их наибольшего общего делителя, поэтому из соотношения Безу и основной теоремы алгебры вытекает следующий результат:

Пусть даны многочлены f(x) и g(x) с коэффициентами в некотором поле. Тогда многочлены a(x) и b(x) такие, что ~af + bg = 1, существуют тогда и только тогда, когда f(x) иg(x) не имеют общих корней ни в каком алгебраически замкнутом поле (обычно в качестве последнего берётся поле комплексных чисел).


Обобщением этого результата на любое количество многочленов и неизвестных является Теорема Гильберта о нулях.

История[править | править вики-текст]

Впервые данный факт опубликовал в 1624 году французский математик Клод Гаспар Баше де Мезириак для случая взаимно простых чисел[12]. Этьен Безу в конце XVIII века обобщил теорему, распространив её на кольцо многочленов.

См. также[править | править вики-текст]

Примечания[править | править вики-текст]

  1. 1 2 Хассе Г., 1953, с. 29.
  2. Jones, G. A., Jones, J. M. §1.2. Bezout's Identity // Elementary Number Theory. — Berlin: Springer-Verlag, 1998. — P. 7—11.
  3. Хассе Г., 1953, с. 33.
  4. Фаддеев Д. К. Лекции по алгебре. Учебное пособие для вузов. — Наука, 1984. — С. 9. — 416 с.
  5. 1 2 Bezout's identity. Проверено 25 декабря 2014.
  6. Гельфонд А. О. Решение уравнений в целых числах. — Наука, 1983. — С. 9—10. — 63 с. — (Популярные лекции по математике, выпуск 8).
  7. Егоров Д. Ф. Элементы теории чисел. — Москва—Петроград: Госиздат, 1923. — С. 14. — 202 с.
  8. 1 2 3 Сушкевич А. К. Теория чисел. Элементарный курс. — Харьков: Изд-во Харьковского университета, 1954. — С. 49—51.
  9. Хинчин А. Я. Цепные дроби. — Изд. 3-е. — М.: ГИФМЛ, 1961. — С. 11—12.
  10. См., например: Жиков В.В. Основная теорема арифметики // Соросовский Образовательный Журнал. — 2000. — Т. 6. — № 3. — С. 112–117.
  11. Коблиц Н. Курс теории чисел и криптографии. — М.: Научное изд-во ТВП, 2001. — С. 19. — 259 с. — ISBN 5-94057-103-4.
  12. Claude Gaspard Bachet, sieur de Méziriac. Problèmes plaisants et délectables // Problemes plaisans, qui se font par nombres. — 2nd ed.. — Pierre Rigaud & Associates, 1624. — P. 18-33.

Литература[править | править вики-текст]

Ссылки[править | править вики-текст]