Question

2. Найди НОД двух чисел с помощью алгоритма Евклида. НОД (235;150)= НОД(616,364)= НОД(45678, 76944)= НОД(7893475, 3189050)= СРОЧНО!!!

Answer 1

235 : 150 = 1 (ост. 85)

150 : 85 = 1 (ост. 65)

85 : 65 = 1 (ост. 20)

65 : 20 = 3 (ост. 5)

20 : 5 = 4 (ост. 0)

НОД (235 и 150) = 5 - наибольший общий делитель

235 : 5 = 47                  150 : 5 = 30

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

616 : 364 = 1 (ост. 252)

364 : 252 = 1 (ост. 112)

252 : 112 = 2 (ост. 28)

112 : 28 = 4 (ост. 0)

НОД (616 и 364) = 28 - наибольший общий делитель

616 : 28 = 22                  364 : 28 = 13

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

76944 : 45678 = 1 (ост. 31266)

45678 : 31266 = 1 (ост. 14412)

31266 : 14412 = 2 (ост. 2442)

14412 : 2442 = 5 (ост. 2202)

2442 : 2202 = 1 (ост. 240)

2202 : 240 = 9 (ост. 42)

240 : 42 = 5 (ост. 30)

42 : 30 = 1 (ост. 12)

30 : 12 = 2 (ост. 6)

12 : 6 = 2 (ост. 0)

НОД (45678 и 76944) = 6 - наибольший общий делитель

45678 : 6 = 7613                   76944 : 6 = 12824

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

7893475 : 3189050 = 2 (ост. 1515375)

3189050 : 1515375 = 2 (ост. 158300)

1515375 : 158300 = 9 (ост. 90675)

158300 : 90675 = 1 (ост. 67625)

90675 : 67625 = 1 (ост. 23050)

67625 : 23050 = 2 (ост. 21525)

23050 : 21525 = 1 (ост. 1525)

21525 : 1525 = 14 (ост. 175)

1525 : 175 = 8 (ост. 125)

175 : 125 = 1 (ост. 50)

125 : 50 = 2 (ост. 25)

50 : 25 = 2 (ост. 0)

НОД (7893475 и 3189050) = 25 - наибольший общий делитель

7893475 : 25 = 315739                3189050 : 25 = 127562

Answer 2

Ответ:

НОД(235;150)=5;

НОД(616;364)=28;

НОД(45678;76944)=6;

НОД(7893475;3189050)=25.

Answer 3

Для нахождения НОД (наибольшего общего делителя) двух чисел с помощью алгоритма Евклида необходимо последовательно делить одно число на другое и заменять их остатком до тех пор, пока не будет получен нулевой остаток. Последнее ненулевое число будет являться НОД.

Давайте посчитаем НОД для каждой пары чисел по порядку:

1. НОД(235, 150): Делим 235 на 150: 235 ÷ 150 = 1 (остаток 85) Заменяем числа: 235 = 150 × 1 + 85 Делим 150 на 85: 150 ÷ 85 = 1 (остаток 65) Заменяем числа: 150 = 85 × 1 + 65 Делим 85 на 65: 85 ÷ 65 = 1 (остаток 20) Заменяем числа: 85 = 65 × 1 + 20 Делим 65 на 20: 65 ÷ 20 = 3 (остаток 5) Заменяем числа: 65 = 20 × 3 + 5 Делим 20 на 5: 20 ÷ 5 = 4 (остаток 0) Нулевой остаток достигнут, поэтому НОД(235, 150) = 5.

2. НОД(616, 364): Делим 616 на 364: 616 ÷ 364 = 1 (остаток 252) Заменяем числа: 616 = 364 × 1 + 252 Делим 364 на 252: 364 ÷ 252 = 1 (остаток 112) Заменяем числа: 364 = 252 × 1 + 112 Делим 252 на 112: 252 ÷ 112 = 2 (остаток 28) Заменяем числа: 252 = 112 × 2 + 28 Делим 112 на 28: 112 ÷ 28 = 4 (остаток 0) Нулевой остаток достигнут, поэтому НОД(616, 364) = 28.

3. НОД(45678, 76944): Продолжая аналогично, мы получим НОД(45678, 76944) = 6.

4. НОД(7893475, 3189050): Продолжая аналогично, мы получим НОД(7893475, 3189050) = 1225.

Таким образом, ответы будут следующими: НОД(235, 150) = 5 НОД(616, 364) = 28 НОД(45678, 76944) = 6 НОД(7893475, 3189050) = 1225