The greatest common divisor and least common multiple

Definition: the Greatest common divisor of two or more natural numbers is called the greatest natural number that divides each of the given numbers.

For example

NOD

Coprime numbers

Definition: Two natural numbers are called relatively Primeif their GCD is equal to one.

Finding GCD using the decomposition into Prime factors

To find the GCD of two or more numbers, you must:

1. To put these numbers into Prime factors.
2. To make the product of the common Prime factors taken with the smallest exponent.
3. To find the value of the work.

The Euclidean Algorithm

1. Share  on  with Stacey:
   
2. Divide the divisor  into :
   
3. Divide the divisor  into the new balance :
   

The last nonzero remainder is the GCD.

Least common multiple (LCM)

The least common multiple of two or more natural numbers is called the smallest natural number that is divisible by each of the given numbers.

Finding knock two natural numbers

To find the NOC two or more numbers, you must:

HCK

For example

NSK

The connection between the NODE and the NOC of the two numbers

NOD

Найбільший спільний дільник та найменше спільне кратне

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

Наприклад

НСД

Взаємно прості числа

Означення: Два натуральних числа називаються взаємно простими, якщо їхній НСД дорівнює одиниці.

Знаходження НСД за допомогою розкладання на прості множники

Щоб знайти НСД двох або кількох чисел, необхідно:

1. Розкласти дані числа на прості множники.
2. Скласти добуток зі спільних простих множників, взятих із найменшим показником степеня.
3. Знайти значення добутку.

Алгоритм Евкліда

1. Поділити  на  з остачею:
   
2. Поділити дільник  на :
   
3. Поділити дільник  на нову остачу :
   

Остання відмінна від нуля остача і є НСД.

Найменше спільне кратне (НСК)

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

Знаходження НСК двох натуральних чисел

Щоб знайти НСК двох або кількох чисел, необхідно:

HCK

Наприклад

НСК

Звязок між НСД і НСК двох чисел

HCД