Нод і нок (тамаркова)

НСД - це найбільший спільний дільник.

НОК - це найменше спільне кратне.

  1. Найбільшим спільним дільником чисел a і b називається найбільше число, на яке a і b діляться без залишку.
  2. Найменше спільне кратне (НОК) двох цілих чисел m і n є найменше натуральне число. яке ділиться на m і n без залишку

Способи знаходження НСД двох чисел:

1 спосіб (випливає з визначення): Метод повного перебору для знаходження найбільшого загального дільника (НСД) натуральних чисел.

  1. Виписуємо всі подільники числа а;
  2. Виписуємо всі подільники числа b;
  3. Вибираємо серед них загальні дільники;
  4. Серед загальних дільників вибираємо найбільше число - це і є НСД (a, b).

2 спосіб: Метод перебору дільників меншого числа для знаходження найбільшого загального дільника (НСД) натуральних чисел.

  1. Знайти подільники меншого з даних чисел.
  2. Знайти, починаючи з більшого, той з виписаних подільників, який є також дільником іншого числа.
  3. Записати знайдене число - НОД.

3 спосіб; Метод знаходження найбільшого спільного дільника (НСД) натуральних чисел за допомогою розкладання на множники.

  1. Знаходимо розкладання чисел на прості множники.
  2. Підкреслюємо загальні числа.
  3. Знаходимо твір підкреслених чисел у одного числа.
  4. Записуємо відповідь.

4 спосіб: Алгоритм Евкліда знаходження найбільшого спільного дільника (НСД) двох натуральних чисел відніманням.

  1. З більшого числа віднімається менша.
  2. Якщо виходить 0, то числа дорівнюють один одному і є найбільшим спільним дільником.
  3. Якщо результат віднімання НЕ дорівнює 0, то більше число замінюється на результат віднімання.
  4. Перехід до пункту 1.

Способи знаходження НСК двох чисел:

1 спосіб: Метод перебору
1. Виписуємо в рядок кратні для кожного з чисел, поки не знайдеться кратне, однакове для обох чисел.

2 спосіб; Метод знаходження найбільшого спільного дільника (НСД) натуральних чисел за допомогою розкладання на множники

  1. Розкласти дані числа на прості множники.
  2. Виписати в рядок множники, що входять до розкладання найбільшого з чисел, а під ним - розкладання інших чисел.
  3. Підкреслити в розкладанні меншого числа множники, які не ввійшли в розкладання бóльшего числа і додати ці множники в розкладання більшої кількості.
  4. Отримане твір записати у відповідь.
Властивості найбільшого загального дільника:
  1. НСД (a, b) = НСД (b, a)
  2. НСД (a, b) = НСД (-a, b)
  3. НСД (a, b) = НСД (| a |, | b |)
  4. НСД (a, 0) = | a |
  5. НСД (a, до • a) = | a |, при будь-якому до ∈ Z
  6. НСД (a, НОД (b, c)) = НСД (НСД (a, b), c)

Властивості найменшого спільного кратного: