Question

Отметьте среди следующих уравнений единственное, которое разрешимо в целых числах: 1) 1001x + 77y = 1 2) 1001x + 707y = 1 3) 1001x + 171y = 1 4) 1001x + 7711y = 1 5) 1001x + 1177y = 1

Answer 1

Ах+bу=с
Диофантово уравнение является неразрешимым в целых числах, если наибольший общий делитель а и b не делит с. Справедливо и обратное: если наибольший общий делитель а и b делит с, то уравнение разрешимо в целых числах.
В данных примерах с=1. Делителем 1 является только 1. Поэтому, коэффициенты а и b должны быть взаимно простыми числами.
1) а=1001 и b=77 делятся на 77, но с=1 не делится на 77. Неразрешимо в целых числах.
2)  а=1001 и b=707 делятся на 7, но с=1 не делится на 7. Неразрешимо в целых числах.
3) а=1001 и b=171 взаимно простые, их общий делитель 1 и с=1 делится на 1. Разрешимо в целых числах.
4) а=1001 и b=7711 имеют наибольший общий делитель 701, но с=1 не делится на 701. Неразрешимо в целых числах.
5) а=1001 и b=1177 имеют наибольший общий делитель 107, но с=1 не делится на 107. Неразрешимо в целых числах.
Ответ: в целых числах разрешимо только уравнение 3.

Answer 2

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

Уравнение вида ax + by = c разрешимо в целых числах, если НОД(a, b) делит c. Если НОД(a, b) не делит c, то уравнение не имеет решений в целых числах.

Применим этот подход к каждому из предложенных уравнений:

1. НОД(1001, 77) = 77 делит 1, поэтому это уравнение разрешимо в целых числах.
2. НОД(1001, 707) = 1 не делит 1, поэтому это уравнение не разрешимо в целых числах.
3. НОД(1001, 171) = 57 делит 1, поэтому это уравнение разрешимо в целых числах.
4. НОД(1001, 7711) = 77 делит 1, поэтому это уравнение разрешимо в целых числах.
5. НОД(1001, 1177) = 77 делит 1, поэтому это уравнение разрешимо в целых числах.

Таким образом, единственное уравнение, разрешимое в целых числах, это 1) 1001x + 77y = 1.