Наибольший общий делитель, его свойства и способы нахождения

Наибольший общий делитель(НОД) двух данных чисел aиb— это наибольшее число, на которое оба числа a и b делятся без остатка.

Кратко наибольший общий делитель чисел a и b записывают так: НОД (a; b). Пример: НОД (12; 36) = 12.Делители чисел в записи решения обозначают большой буквой «Д».Пример. Д (7) = {1, 7} Д (9) = {1, 9} НОД (7; 9) = 1 Числа 7 и 9 имеют только один общий делитель — число 1. Такие числа называют взаимно простыми числами. Основное свойство: наибольший общий делитель 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. (a*m. A*n) =!a! * (m*n)— общий множитель можно выносить за знак НОД.Если, D= (m.n) то после деления на D числа становятся взаимно простыми, то есть, .Это означает, в частности, что для приведения дроби к несократимому виду надо разделить её числитель и знаменатель на их НОД. Мультипликативность: если взаимно просты, то: Наибольший общий делитель чисел m и n может быть определён как наименьший положительный элемент множества всех их линейных комбинаций: и поэтому (m,n) представим в виде линейной комбинации чисел m и n: (m,n)=u*m+v*n. Это соотношение называется соотношением Безу, а коэффициенты u и v — коэффициентами Безу. Коэффициенты Безу эффективно вычисляются расширенным алгоритмом Евклида. Это утверждение обобщается на наборы натуральных чисел — его смысл в том, что подгруппа группы Z, порождённая набором , — циклическая и порождается одним элементом: НОД (a1, a2, …, an). 1. Чтобы найти НОД нескольких чисел, достаточно, разложить их на простые множители и перемножить между собой те из них, которые являются общими для всех данных чисел.