найдите НОД ( a, b), если а) а=2×2×3×3×5×7×19 b) b=2×3×11×13

Решение по шагам

Задача: найти НОД(a, b), где a = 2 × 2 × 3 × 3 × 5 × 7 × 19 b = 2 × 3 × 11 × 13

1. Разложим в простые множители

• a = 2^2 · 3^2 · 5 · 7 · 19
• b = 2 · 3 · 11 · 13

2. Найдём общие простые множители и их минимальные степени

• Общие простые: 2 и 3.
• В a: 2^2 и 3^2; в b: 2^1 и 3^1.
• Берём минимальные степени: 2^min(2,1) = 2^1, и 3^min(2,1) = 3^1.

3. НОД = произведение общих множителей с минимальными степенями НОД(a, b) = 2^1 · 3^1 = 6

Проверка числом

• a = 2 × 2 × 3 × 3 × 5 × 7 × 19 = 23940
• b = 2 × 3 × 11 × 13 = 858
• gcd(23940, 858) через алгоритм Евклида: 23940 mod 858 = 774; 858 mod 774 = 84; 774 mod 84 = 18; 84 mod 18 = 12; 18 mod 12 = 6; 12 mod 6 = 0. Значит gcd = 6.

Ответ: НОД(a, b) = 6.