Задача 71235 [blue]1)[/blue]Используя алгоритм...
Условие
[b]7 650, 25 245[/b]
[blue]2)[/blue]Используя третье свойство НСД, найти НСД трех чисел:
[b]67 283, 122 433, 221 703[/b]
[blue]3)[/blue]Используя признаки делимостичисел, исследовать, делится ли число [b]a[/b] на число [b]m[/b]:
[b]m = 31
a=238173[/b]
[blue]4)[/blue]Рациональное число [b]a / b[/b] заданное цепочкой неполных долей.
Построить соответствующее наименьшее рациональное число
[b]a / b[/b] и найти решение уравнения [b]ax + by = 1[/b]
Цепочка неполных долей [b][1,13,1,2,5,1,1][/b]
Решение
25 245 = 3 * 7 650 + 1 195
7 650 = 6 * 1 195 + 70
1 195 = 17 * 70 + 15
70 = 4 *15 +10
15 =1*10+5
10=2*5+0
Ответ: НОД(7 650;25 245) = 5.
Наибольший общий делитель (НОД) трех чисел можно найти с помощью свойств НОД. Например, для нахождения НОД чисел 67 283, 122 433 и 221 703 можно использовать следующее свойство:
НОД(a,b,c) = НОД(НОД(a,b),c)
Тогда:
НОД(67 283,122 433,221 703) = НОД(НОД(67 283,122 433),221 703)
Выполним алгоритм Евклида для нахождения НОД(67 283,122 433):
122 433 =1*67 283+55 150
67 283=1*55 150+12 133
55 150=4*12 133+2 498
12 133=4*2 498+1 741
2 498=1*1 741+757
1 741=2*757+227
757=3*227+76
227=2*76+75
76=1*75+1
Ответ: НОД(67 283;122 433;221 703) = 1.
Чтобы проверить делится ли число a на число m без остатка, нужно проверить равенство a mod m =0. В данном случае:
238173 mod 31 =0.
Ответ: число 238173 делится на число 31 без остатка.
Цепочка неполных долей [1,13,1,2,5,1,1] соответствует рациональному числу:
a/b=1+1/(13+1/(1+1/(2+1/(5+1/1))))=307/229.
Решим уравнение ax + by = 1. Для этого найдем НОД чисел a и b с помощью алгоритма Евклида:
307=229*1+78
229=78*2+73
78=73*1+5
73=5*14+3
5=3*1+2
3=2*1+1
НОД(307;229)=1.
Выразим НОД через a и b:
ax + by = НОД(a,b).
78-229*2=-380.
73-78*(-3)=307.
Ответ: решение уравнения ax + by = 1 при a/b=307/229 - это x=-3 и y=-2.