Як знайти нод і нок чисел


 

Цілі числа — безліч математичних чисел, що мають велике застосування в повсякденному житті. Невід’ємні цілі числа використовуються при зазначенні кількості будь-яких об’єктів, негативні числа — в повідомленнях про прогноз погоди та ін НОД і НОК — це натуральні характеристики цілих чисел, пов’язані з операціями поділу.



Інструкція

  1. Найбільший загальний дільник (НСД) двох цілих чисел — це найбільше ціле число, на яке діляться обидва вихідних числа без залишку. При цьому хоча б одне з них повинно бути відмінним від нуля, як і НОД.
        
  2. НОД легко обчислити за алгоритмом Евкліда або бінарним методу. За алгоритмом Евкліда визначення НОД чисел a і b, одне з яких не дорівнює нулю, існує така послідовність чисел r_1> r_2> r_3> …> r_n, в якій елемент r_1 дорівнює залишку від ділення першого числа на друге. А інші члени послідовності рівні залишків від ділення предпредидущего члена на попередній, а передостанній елемент ділиться на останній без залишку.
        
  3. Математично послідовність можна представити у вигляді:
    a = b * k_0 + r_1
    b = r_1 * k_1 + r_2
    r_1 = r_2 * k_2 + r_3

    r_ (n — 1) = r_n * k_n,
    де k_i — цілочисельний множник.
    НОД (a, b) = r_n.
        
  4. Алгоритм Евкліда називають взаємним вирахуванням, оскільки НОД виходить при послідовному відніманні меншого з більшого. Неважко припустити, що НСД (a, b) = НСД (b, r).
        
  5. Приклад.
    Знайдіть НОД (36, 120). За алгоритмом Евкліда відніміть від 120 число, кратне 36, в даному випадку це 120 — 36 * 3 = 12. Тепер відніміть від 120 число, кратне 12, вийде 120 — 12 * 10 = 0. Отже, НСД (36, 120) = 12.
        
  6. Бінарний алгоритм знаходження НОД заснований на теорії зсуву. Відповідно до цього методу НОД двох чисел має такі властивості:
    НОД (a, b) = 2 * НОД (a / 2, b / 2) для парних a і b
    НОД (a, b) = НСД (a / 2, b) для парного a і непарного b (навпаки вірно НОД (a, b) = НСД (a, b / 2))
    НОД (a, b) = НСД ((a — b) / 2, b) для непарних a> b
    НОД (a, b) = НСД ((b — a) / 2, a) для непарних b> a
    Таким чином, НОД (36, 120) = 2 * НОД (18, 60) = 4 * НОД (9, 30) = 4 * НОД (9, 15) = 4 * НОД ((15 — 9) / 2 = 3 , 9) = 4 * 3 = 12.
        
  7. Найменше спільне кратне (НОК) двох цілих чисел — це найменше ціле число, яке ділиться на обидва вихідних числа без залишку.
    НОК можна обчислити через НОД: НОК (a, b) = | a * b | / НСД (a, b).
        
  8. Другий спосіб обчислення НОК — канонічне розкладання чисел на прості множники:
    a = r_1 ^ k_1 * … * r_n ^ k_n
    b = r_1 ^ m_1 * … * r_n ^ m_n,
    де r_i — прості числа, а k_i і m_i — цілі числа ≥ 0.
    НОК представляється у вигляді тих же простих множників, де в якості ступенів беруться максимальні з двох чисел.
        
  9. Приклад.
    Знайдіть НОК (16, 20):
    16 = 2 ^ 4 * 3 ^ 0 * 5 ^ 0
    20 = 2 ^ 2 * 3 ^ 0 * 5 ^ 1
    НОК (16, 20) = 2 ^ 4 * 3 ^ 0 * 5 ^ 1 = 16 * 5 = 80.

Зверніть увагу

Існує поняття взаємно-простих чисел, у якого немає спільних дільників, крім 1. Для таких чисел НОД (a, b) = 1.