Главная страница
Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
|
Свойства НОД
- Основное свойство: наибольший общий делитель m и n делится на любой общий делитель этих чисел. Пример: для чисел 12 и 18 наибольший общий делитель равен 6; он делится на все общие делители этих чисел: 1, 2, 3, 6.
- Следствие 1: множество общих делителей m, n совпадает с множеством делителей НОД (m, n).
- Следствие 2: множество общих кратных m, n совпадает с множеством кратных НОК (m, n).
- Если m делится на n, то НОД (m, n) = n. В частности, НОД (n, n) = n.
-
— общий множитель можно выносить за знак НОД. - Если D = (m, n), то после деления на D числа становятся взаимно простыми, то есть,
. Это означает, в частности, что для приведения дроби к несократимому виду надо разделить её числитель и знаменатель на их НОД. - Мультипликативность: если a 1, a 2 взаимно просты, то:

- Наибольший общий делитель чисел m и n может быть определён как наименьший положительный элемент множества всех ихлинейных комбинаций:

и поэтому (m, n) представим в виде линейной комбинации чисел m и n:
.
Это соотношение называется соотношением Безу, а коэффициенты u и v — коэффициентами Безу. Коэффициенты Безу эффективно вычисляются расширенным алгоритмом Евклида. Это утверждение обобщается на наборы натуральных чисел — его смысл в том, что подгруппа группы , порождённая набором , — циклическая и порождается одним элементом: НОД .
|