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

Posted By on 06.09.2012

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

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

Существует классический способ нахождения наибольшего общего делителя (НОД).

1. Разложить оба числа на простые множители
2. Одинаковые множители каждого разложения записать в виде степени.
3. Отобрать в ответ общие множители из двух разложений. Если степени их различны, следует забрать множитель в меньшей степени.

 

Пример.
Найти наибольший общий делитель

НОД (4704, 5040)

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

 4704 = 2^{5}*7^{2}*3
 5040 = 2^{4}*5*3^{2}*7

HOД  (4704, 5040) = 2^{4}*3*7 = 336

Алгоритм Эвклида для нахождения наибольшего общего делителя двух чисел

1. Из большего числа следует вычесть меньшее.
2. Убираем большее число из двух предыдущих и вместо него берем разность.

3. Если плучены одинаковые числа, то именно они и являются НОД. Если получены разные, то переходим к пункту 1 и повторяем процесс.

Пример.

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

НОД (180, 140)

180-140 = 40, заменяем 180 на 40

140-40 =  100, заменяем 140 на 100

100-40 =  60, заменяем 100 на 60

60-40 =  20, заменяем 60 на 20

40 – 20 = 20, заменяем 40 на 20

20-20=  0 – процесс закончен

НОД (180, 140) = 20

Второй способ достаточно громоздкий, но иногда хорошо выручает.

ПОДПИШИТЕСЬ НА РАССЫЛКУ!
ИМЯ:
АДРЕС E-Mail:

Поделиться в соц. сетях

Опубликовать в Google Plus
Опубликовать в LiveJournal
Опубликовать в Мой Мир
Опубликовать в Яндекс
Опубликовать в Одноклассники
686 views

Наиболее просматриваемые записи

About The Author

Comments

ЗАДАЙТЕ ВОПРОС