Question

Найти НОД: а)75и45б) 81 и 243в) 47225 и 7875

Answer 1

A)НОД(75,45)=5     б)НОД(81,243)=27*3=81   в)НОД(47225,7875)=1 (взаимно простые)

а)75:3=25   45:3=15  б)81:3=27   243:3=81   в)47225:5=9445   7875:3=2625
  25:5=5     15:3=5       27:3=9     81:3=27       9445:5=1889     2625:3=875
  5:5=1       5:5=1         9:3=3      27:3=9          1889:1889=1    875:5=175
                                  3:3=1       9:3=3                                  175:5=35
                                                 3:3=1                                  35:5=7
                                                                                           7:7=1

Answer 2

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

а) НОД(75, 45): 75 = 45 * 1 + 30 45 = 30 * 1 + 15 30 = 15 * 2 + 0

Последний ненулевой остаток равен 15, поэтому НОД(75, 45) = 15.

б) НОД(81, 243): 243 = 81 * 3 + 0

Поскольку остаток равен нулю, НОД(81, 243) = 81.

в) НОД(47225, 7875): 47225 = 7875 * 6 + 1375 7875 = 1375 * 5 + 500 1375 = 500 * 2 + 375 500 = 375 * 1 + 125 375 = 125 * 3 + 0

Последний ненулевой остаток равен 125, поэтому НОД(47225, 7875) = 125.