ГлавнаяМатематический словарь Н
Наибольший общий делитель

Наибольший общий делитель

Наибольшим общим делителем (НОД) двух целых чисел m и n называется их общий делитель d (то  есть d/m  и d/n  ), который делится на любой другой общий делитель m и n.

Наибольший общий делитель существует и однозначно определён (с точностью до знака), если хотя бы одно из чисел m или n не ноль.

Пример: для чисел 12 и 18 наибольший общий делитель равен 6; он делится на все общие делители этих чисел: 1, 2, 3, 6.

Для понимания определения "наибольший общим делителем" можно рассмотреть "общий делитель"

Общим делителем нескольких чисел называется число, которое является делителем каждого из них.

Например, числа 36, 60, 42 имеют общие делители 2, 3 и 6.

Среди всех общих делителей всегда есть наибольший, в данном случае это 6. Это и есть наибольший общий делитель (НОД).

Из двух возможных значений наибольшего общего делителя, отличающихся знаком, выбирается одно, положительное.

Наибольший общий делитель чисел m и n можно обозначать (записывать) так:
(m, n)
НОД(m, n)
GCD(m, n) (от англ. Greatest Common Divisor)

Пример: НОД(12,18)=6

Понятие наибольшего общего делителя естественным образом обобщается на наборы из более чем двух целых чисел.

Так же можно воспользоваться таким определением:  Наибольший общий делитель двух или нескольких натуральных чисел — наибольшее из чисел, на которые делится каждое из данных чисел.

Например. Наибольший общий делитель 45 и 72 есть 9, Наибольший общий делитель 60, 84, 96 и 120 есть 12.

Используются наибольший общий делитель при сокращении дробей: наибольшее число, на которое могут быть сокращены числитель и знаменатель дроби, — их наибольший общий делитель Если известны разложения заданных чисел на простые множители, то для получения наибольшего общего делителя этих чисел нужно составить произведение тех множителей, которые входят одновременно во все разложения, взяв каждый наименьшее число раз, какое он встречается.

Так, 60 = 2×2×3×5, 72 = 2×2×2×3×3 и 252 = 2×2×3×3×7; поэтому Наибольший общий делитель 60, 72 и 252 есть 2×2×З = 12.

Общим приёмом отыскания Наибольший общий делитель двух чисел является способ последовательного деления, указанный ещё в 3 в. до н. э. Евклидом (Евклида алгоритм). Он заключается в том, что большее из двух данных чисел делят на меньшее, затем меньшее — на остаток от первого деления, остаток от первого деления — на остаток от второго деления и т.д., до тех пор, пока не дойдут до остатка, равного нулю. Последний, отличный от нуля, остаток и будет Наибольший общий делитель данных чисел. Например, чтобы найти Наибольший общий делитель 3542 и 2464, выполняют последовательные деления: 3542 = 2464×1 + 1078, 2464 = 1078×2 + 308, 1078 = 308×3 + 154, 308 = 154×2. В остатке при последнем делении — нуль; следовательно, Наибольший общий делитель 3542 и 2464 равен предпоследнему остатку, то есть 154. Если Наибольший общий делитель двух чисел равен единице, то эти числа называют взаимно простыми. Наибольший общий делитель d двух чисел а и b и наименьшее общее кратное m этих чисел связаны соотношением dm = ab.


  • >>> Для лучшего понимания определения "Наибольший общий делитель" , а так же что бы научиться быстро и легко находить его, советуем просмотреть бесплатный видео урок: "Простые и составные числа"

Понравился сайт поделись с друзьями
и добавь в закладки, нажми
Ctrl + d
Rt: 0.00597 sec / Wed, 17 Sep 2014 03:28:12