Question

Знайдіть НСД чисел (105 і 60)

Answer 1

Заметим, что $105=15\cdot7, 60=15\cdot4$

Видим, что наибольший общий делитель - число 15.

Answer 2

Щоб знайти найбільший спільний дільник (НСД) чисел 105 і 60, можна скористатися алгоритмом Евкліда. Ось як це можна зробити:

1. Поділіть більше число на менше і збережіть залишок. $\text{Залишок} = 105 \mod 60 = 45$

2. Тепер замініть більше число менше число, а отриманий залишок з кроку 1 - на більше число. $\text{Нове більше число} = 60$ $\text{Нове менше число} = 45$

3. Повторіть кроки 1 і 2, поки не досягнете залежності, коли залишок стане рівним 0. $\text{Залишок} = 60 \mod 45 = 15$ $\text{Нове більше число} = 45$ $\text{Нове менше число} = 15$

4. Тепер поділіть число, на яке поділили в попередньому кроці, на отриманий залишок. $\text{Залишок} = 45 \mod 15 = 0$

Коли залишок стає рівним 0, отримане менше число є НСД чисел 105 і 60. У цьому випадку, НСД(105, 60) = 15.