НОД БЕЗУ

Соотноше́ние Безу́ — представление наибольшего общего делителя целых чисел в виде их линейной комбинации с целыми коэффициентами[1].

Названо в честь французского математика Этьена Безу.

Формулировка[править | править вики-текст]

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

НОД =

которое называется соотношением Безу (для чисел и), а также леммой Безу или тождеством Безу[3]. При этом целые числа  называютсякоэффициентами Безу.

Примеры

• НОД Соотношение Безу имеет вид:

  

  • Возможны и другие варианты разложения НОД, например:

• Следствия

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

  

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

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

  Множество целочисленных линейных комбинаций}} совпадает с множеством кратных для НОД})[6].

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

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

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

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

   где НОД.

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

  y=

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

  Ниже будет показано, что существуют коэффициенты Безу, удовлетворяющие неравенствам и