Question

Найти линейное представления НОД(82295,58890)

Answer 1

Найдём НОД. Пусть A = 82295, B = 58890

НОД(A; B) = НОД(A-B; B) = НОД(23405; 58890) = НОД(C; B) (пусть C = A - B)

НОД(C; B) = НОД(C; B-2C) = НОД(23405; 12080) = НОД(C; D) (D = B - 2C)

НОД(C; D) = НОД(C-D; D) = НОД(11325; 12080) = НОД(E; D) (E = C - D)

НОД(E; D) = НОД(E; D-E) = НОД(11325; 755) = 755

755 = D - E = B - 2C - C + D = B - 3C + B - 2C = 2B - 5(A - B) = 2B - 5A + 5B = -5A + 7B = -5 * 82295 + 7 * 82295

Ответ: 755 = -5 * 82295 + 7 * 82295

Answer 2

Для нахождения линейного представления наибольшего общего делителя (НОД) двух чисел, необходимо применить расширенный алгоритм Евклида. Этот алгоритм позволяет найти НОД и коэффициенты $x$ и $y$, такие что:

$НОД(a, b) = ax + by$

где $a$ и $b$ – заданные числа, а $x$ и $y$ – коэффициенты, которые и будут линейным представлением.

Применим алгоритм Евклида для чисел 82295 и 58890:

1. Делим большее число на меньшее и находим остаток: $82295 \div 58890 = 1 \quad \text{с остатком} \quad 23405$

2. Теперь вместо $82295$ берем $58890$, а вместо $58890$ берем полученный остаток $23405$: $58890 \div 23405 = 2 \quad \text{с остатком} \quad 12080$

3. Теперь вместо $58890$ берем $23405$, а вместо $23405$ берем полученный остаток $12080$: $23405 \div 12080 = 1 \quad \text{с остатком} \quad 11245$

4. Теперь вместо $23405$ берем $12080$, а вместо $12080$ берем полученный остаток $11245$: $12080 \div 11245 = 1 \quad \text{с остатком} \quad 835$

5. Теперь вместо $12080$ берем $11245$, а вместо $11245$ берем полученный остаток $835$: $11245 \div 835 = 13 \quad \text{с остатком} \quad 60$

6. Теперь вместо $11245$ берем $835$, а вместо $835$ берем полученный остаток $60$: $835 \div 60 = 13 \quad \text{с остатком} \quad 35$

7. Теперь вместо $835$ берем $60$, а вместо $60$ берем полученный остаток $35$: $60 \div 35 = 1 \quad \text{с остатком} \quad 25$

8. Теперь вместо $60$ берем $35$, а вместо $35$ берем полученный остаток $25$: $35 \div 25 = 1 \quad \text{с остатком} \quad 10$

9. Теперь вместо $35$ берем $25$, а вместо $25$ берем полученный остаток $10$: $25 \div 10 = 2 \quad \text{с остатком} \quad 5$

10. Теперь вместо $25$ берем $10$, а вместо $10$ берем полученный остаток $5$: $10 \div 5 = 2 \quad \text{с остатком} \quad 0$

Таким образом, мы получили остаток равный нулю, что означает, что последний делитель (5) является наибольшим общим делителем (НОД) чисел 82295 и 58890.

Теперь мы можем найти линейное представление НОД(82295, 58890). Для этого воспользуемся обратными ходом алгоритма Евклида:

Из последнего шага алгоритма Евклида у нас есть: $5 = 10 - 2 \cdot 5$ $5 = 10 - 2 \cdot (25 - 10 \cdot 2)$ $5 = 5 \cdot 10 - 2 \cdot 25$ $5 = 5 \cdot (35 - 25) - 2 \cdot 25$ $5 = 5 \cdot 35 - 7 \cdot 25$ $5 = 5 \cdot 35 - 7 \cdot (60 - 35)$ $5 = 12 \cdot 35 - 7 \cdot 60$ $5 = 12 \cdot (835 - 60 \cdot 13) - 7 \cdot 60$ $5 = 12 \cdot 835 - 97 \cdot 60$ $5 = 12 \cdot 835 - 97 \cdot (11245 - 835 \cdot 13)$ $5 = 1261 \cdot 835 - 97 \cdot 11245$ $5 = 1261 \cdot (12080 - 11245) - 97 \cdot 11245$ $5 = 1261 \cdot 12080 - 1358 \cdot 11245$ $5 = 1261 \cdot 12080 - 1358 \cdot (23405 - 12080 \cdot 2)$ $5 = 3977 \cdot 12080 - 1358 \cdot 23405$ $5 = 3977 \cdot (58890 - 23405 \cdot 2) - 1358 \cdot 23405$