19.06 НОК, НОД и взаимная простота чисел

а) Алгоритм Евклида заключается в последовательном делении с остатком

1.

Делим 1598 на 987 с остатком:

Получили, что неполное частное равно 1, а остаток равен 611.

2.

Делим 987 на 611 с остатком:

Получили, что неполное частное равно 1, а остаток равен 376.

3.

Делим 611 на 376 с остатком:

Получили, что неполное частное равно 1, а остаток равен 235.

4.

Делим 376 на 235 с остатком:

Получили, что неполное частное равно 1, а остаток равен 141.

5.

Делим 235 на 141 с остатком:

Получили, что неполное частное равно 1, а остаток равен 94.

6.

Делим 141 на 94 с остатком:

Получили, что неполное частное равно 1, а остаток равен 47.

7.

Делим 94 на 47 с остатком:

Получили, что частное равно 2, а остаток равен 0.

Так как остаток равен 0, то НОД — это последний ненулевой остаток, то есть 47.

б) Найдем все целые решения уравнения Заметим, что если и — целые, то левая часть уравнения будет целой. Значит, имеем равенство двух целых чисел.

Согласно указанию, если два целых числа равны, то они делятся на одни и те же числа. Левая часть уравнения делится на 47, так как по пункту а) но правая часть уравнения на 47 не делится.

Значит, два целых числа и 1 не равны ни при каких целых и то есть уравнение не имеет решений.