Задача А: Найти НОД двух натуральных чисел с помощью алгоритма Евклида.

1. Что такое НОД

• НОД(a, b) — наибольший общий делитель чисел a и b.
• Для натуральных чисел (положительных) НОД всегда существует и не меньше 1.

2. Как работает алгоритм Евклида

• Пусть у нас есть два числа a и b (a ≥ b).
• Повторяем пока b ≠ 0:
  • Вычисляем остаток r = a mod b.
  • Заменяем пары (a, b) на (b, r).
• Когда b становится 0, значение a и есть НОД(a, b).
• Обоснование: на каждом шаге мы заменяем пару (a, b) на пару (b, a mod b), и любое число, делящее и a, и b, должно делить также и остаток a mod b. Алгоритм сходится к НОД.

3. Пример разбор для чисел 21 и 14

• 21 = 14 * 1 + 7, остаток r = 7
• Следующий шаг: (a, b) = (14, 7)
• 14 = 7 * 2 + 0, остаток r = 0
• b стал 0, значит НОД = a = 7 Итак, НОД(21, 14) = 7.

4. Псевдокод алгоритма

• вход: a, b
• пока b != 0:
  • r = a mod b
  • a = b
  • b = r
• вернуть a (это и есть НОД)

5. Реализация на Python (для класса 8)

• Код читает два числа и выводит НОД в формате НОД(a,b)=g

Пример кода (Python):

def gcd(a, b): while b: a, b = b, a % b return a

считываем два натуральных числа с ввода

a, b = map(int, input("Введите два числа: ").split()) print(f"НОД({a},{b})={gcd(a, b)}")

6. Пример выполнения

• Ввод: 21 14
• Вывод: НОД(21,14)=7

Дополнительно можно привести аналогичный код на другом языке (для справки):

• C++:

#include using namespace std;

int gcd(int a, int b){ while (b != 0){ int t = a % b; a = b; b = t; } return a; }

int main(){ int a, b; if(!(cin >> a >> b)) return 0; cout << "НОД(" << a << "," << b << ")=" << gcd(a,b) << endl; return 0; }

• Java: public static int gcd(int a, int b){ while (b != 0){ int t = a % b; a = b; b = t; } return a; } public static void main(String[] args){ Scanner sc = new Scanner(System.in); int a = sc.nextInt(); int b = sc.nextInt(); System.out.println("НОД(" + a + "," + b + ")=" + gcd(a,b)); }

Если хочешь, могу адаптировать решение под конкретный язык программирования или под задачу в виде файла и привести ещё примеры с другими числами.