У будь-якого натурального числа є подільники - числа, на які це число ділиться без залишку. навіть у простих чисел такі подільники є - саме це число і одиниця. Якщо взяти два натуральних числа, то у них також є свої подільники, які іноді можуть збігатися з дільниками другого числа. А дільник одиниця присутня завжди, але розглядати його не цікаво. Так ось, найбільший за значенням дільник, який є загальним для обох чисел буде цим горезвісним найбільшим дільником. Знаходять його за алгоритмом Евкліда, який дуже простий і полягає в наступному. З наявної пари чисел складається нова пара, в якому одне число - найменше з початкових, а друге різниця між ними. потім операція повторюється поки ода отриманих числа не співпадуть. Це і є найбільший дільник. За наведеним прикладом для чисел 8 і 12 отримуємо другу пару чисел 8 і 4 (12-8), наступна пара буде 4 і 4 (8-4). Числа збіглися вже в другій ітерації і ми знайшли найбільший дільник - це 4.
система вибрала цю відповідь найкращим
Натуральне число - число, яке виникло в результаті підрахунку реальних речей (яблук, баранів, телевізорів), яке використовують для визначення їх кількості.
Два натуральних числа - це зрозуміло. Ми маємо два числа, не збігаються один з одним.
Загальний дільник двох натуральних чисел - число, на яке може бути розділене кожне з двох натуральних чисел без залишку. Будь-які два натуральних числа мають як мінімум один спільний дільник - одиницю.
Якщо два натуральних числа мають кілька спільних дільників, то можна визначити найбільший з них. Наприклад, 12 і 8 мають загальні дільники: 1, 2, 4. Відповідно, 4 буде найбільшим спільним дільником для 12 і 8.
Щоб знайти НСД, потрібно розкласти кожне з чисел на прості множники. Якщо мова йде про великі числа, НСД яких важко визначити, застосовують алгоритм Евкліда або бінарний алгоритм.
Олександр Пригічев [596]
Для того, щоб знайти НСД, не обов'язково розкладати на множники! Існує прекрасний алгоритм Евкліда - см википедию. - 4 роки тому