Question

Являются ли взаимно простыми числа:а)28 и 36б)3;5 и 26  

Answer 1

28=2*2*7
36=2*2*3*3
НОД(28,36)=2*2=4 - не являются взаимно простыми 

3
5
26=2*13
НОД(3,5,26)=1 - являются взаимно простыми

Answer 2

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

а) 28 и 36

Для проверки взаимной простоты чисел 28 и 36 применим алгоритм Евклида:

НОД(28, 36) = НОД(36, 28 mod 36) = НОД(36, 28)

НОД(36, 28) = НОД(28, 36 mod 28) = НОД(28, 8)

НОД(28, 8) = НОД(8, 28 mod 8) = НОД(8, 0)

НОД(8, 0) = 8

Так как НОД(28, 36) не равен 1, то числа 28 и 36 не являются взаимно простыми.

б) 3;5 и 26

Для проверки взаимной простоты чисел 3;5 и 26 применим алгоритм Евклида:

НОД(3;5, 26) = НОД(26, 3;5 mod 26) = НОД(26, 3;5)

НОД(26, 3;5) = НОД(3;5, 26 mod 3;5) = НОД(3;5, 0)

НОД(3;5, 0) = 3;5

Так как НОД(3;5, 26) равен 1, то числа 3;5 и 26 являются взаимно простыми.

: [Взаимно простые числа] : [Алгоритм Евклида] : [Остаток от деления]