Най-голям общ делител

Намирането на ГРУ, използвайки множители

Най-естествено число, с което броят на разделен без остатък и б, наречен най-голям общ делител на числата. Означаваме GCD (а, Ь).

Вземем примера на намиране на НОД на две числа 18 и 60:

• 1 Ние увеличи броя на простите числа:
  18 = 2 х 3 х 3
  60 = 2 х 2 х 3 х 5
• 2 удари от първия разширяване на всички фактори, които не са включени в разширяването на второто число, получаване на 2 х 3 х 3.
• 3 умножава прости числа, оставащи след заличаване и да получат най-голям общ делител на цифрите: (. 18 60) GCD = 2 х 3 = 6.
• 4 Имайте предвид, че не е важно от първата или втората от множителите зачеркнете, резултатът е един и същ:
  18 = 2 х 3 х 3
  60 = 2 х 2 х 3 х 5

Пример Виж най-голям общ делител на 111 и 324. 432

Записът е изтрит от първото число, фактори, които не са налични във втория и третия брой, получават:

Намирането на ГРУ, използвайки алгоритъм на Евклид

Вторият метод за намиране на най-голям общ делител, използвайки алгоритъм на Евклид. алгоритъм на Евклид е най-ефективният начин за намиране на НОД. използване е необходимо постоянно да се намери останалата част от разделението на номера и да приложите повторение формула.

Формулата за повтаряне за GCD, GCD (а, Ь) = GCD (Ь, мод б). където мод б - остатък от участък на б.

алгоритъм на Евклид

Пример Намерете най-голям общ делител на 7920 и 594

Ние считаме, НОД (7920. 594), като се използва алгоритъм на Евклид, за да се изчисли остатъка от деление ще бъде с помощта на калкулатора.

GCD В резултат (7920. 594) = 198

Намирането на най-малко общо кратно

Намирането NOC чрез разлагане на множители

Най-малкото общо кратно на естествени числа А и В е-малкото естествено число. е кратно на и и б. Означени LCM (а, Ь).

Вземем примера за намиране LCM две естествени числа 18 и 60:

• 1 Ние увеличи броя на простите числа:
  18 = 2 х 3 х 3
  60 = 2 х 2 х 3 х 5
• 2 Добавяне на липсващите фактори от разлагане на втория номер, да получат 2 × 2 × 3 × 3 × 5.
• 3 умножава основните фактори след добавяне и получаване на най-малко общо кратно на цифрите: (. 18 60) LCM = 2 х 2 х 3 х 3 х 5 = 180.

Пример Намерете най-малко общо кратно на числата 168, 231 и 60

Добавянето на броя на първите разпространители на втория и третия брой, ние получаваме:

2 х 2 х 2 х 3 х 5 х 11 х 7 = 9240.

Намирането на най-малко общо кратно с помощта на най-голям общ делител

Ако е известно GCD на номерата, НОК може да бъде изчислена по формулата

Пример Виж най-малко общо кратно на номера 54 и 72, ако GCD (54, 72) = 18.

Използване формула констатация NOC чрез GCD получи