Разделы 
Дополнительно
Задача по математике - 895
2014-03-08 
Докажите, что если числа #a# и #b# взаимно просты, то #\text{НОД} (11a+2b,18a + 5b)# равен либо 1, либо 19.
Решение:
Применим алгоритм Евклида: #18a + 5b = (11a + 2b) \cdot 1 + (7a + 3b), \\ 11a + 2b = (7a + 3b) \cdot 1 + (4a - b), \\ 7a + 3b = (4a - b) \cdot 1 + (3a+4b), \\ 4a - b = (3a+4b) \cdot 1 + (a-5b), \\ 3a+4b = (a-5b) \cdot 3 + 19b.# Значит, #\text{НОД}(11a+2b,18a+5b) = \text{НОД}(a-5b,19b),# Далее, т.к. числа #a# и #b# взаимно просты, то числа #a-5b# и #b# также взаимно просты (действительно, по алгоритму Евклида #a-5b = b \cdot (-5) + a).# И потому #\text{НОД}(a-5b,19b) = \text{НОД}(a-5b,19)# Теперь ясно, что если #a-5b# делится на 19, то #d = 19,# если нет, то #d = 1.#
Докажите, что если числа #a# и #b# взаимно просты, то #\text{НОД} (11a+2b,18a + 5b)# равен либо 1, либо 19.
Решение:
Применим алгоритм Евклида: #18a + 5b = (11a + 2b) \cdot 1 + (7a + 3b), \\ 11a + 2b = (7a + 3b) \cdot 1 + (4a - b), \\ 7a + 3b = (4a - b) \cdot 1 + (3a+4b), \\ 4a - b = (3a+4b) \cdot 1 + (a-5b), \\ 3a+4b = (a-5b) \cdot 3 + 19b.# Значит, #\text{НОД}(11a+2b,18a+5b) = \text{НОД}(a-5b,19b),# Далее, т.к. числа #a# и #b# взаимно просты, то числа #a-5b# и #b# также взаимно просты (действительно, по алгоритму Евклида #a-5b = b \cdot (-5) + a).# И потому #\text{НОД}(a-5b,19b) = \text{НОД}(a-5b,19)# Теперь ясно, что если #a-5b# делится на 19, то #d = 19,# если нет, то #d = 1.#
