Помогите решить задачу.

[EXBOR]

Помогите решить задачу. Вроде бы я ее уже решил, но уж больно громоздко получается. Существует ли более изящное решение?

Задача:
Правильно ли утверждение, что существуют 2 натуральных числа (x) и (y) таких, что 158x+93y=2003 ?
Я решал так:
1. Одно уравнение с двумя неизвестными. Значит нужно искать второе условие.
Я считаю, что это тот факт, что 2003 – простое число.
2. Число 158- четное. Значит, при умножении числа 158 на любое число произведение всегда будет четным.
3. При умножении числа 93 на любое четное число произведение тоже будет четным числом. Значит (158x+93y) для всего ряда значений (x) и четных значений (y) тоже будет четным.
4. Остается проверить сумму для нечетных значений (y). Сделал это простым перебором значений (y) от 3 до 19.
Итог: Исходное утверждение неверно.

[nnosipov]

EXBOR в сообщении #559935 писал(а):

Существует ли более изящное решение?

Можно решить это уравнение в целых числах (знать соответствующий алгоритм решения полезно) и затем убедиться, что решений в натуральных числах нет. Но это тоже потребует вычислений. Поэтому в данном случае лучше небольшой перебор (по $x$, либо по $y$, как у Вас).

[Maslov]

EXBOR в сообщении #559935 писал(а):

1. Одно уравнение с двумя неизвестными. Значит нужно искать второе условие.
Я считаю, что это тот факт, что 2003 – простое число.

Простота тут не при чем; используется нечетность. Ровно так же можно было бы решать уравнение $158x + 93y = 2005$.

[Praded]

EXBOR
Почитайте в сети про диофантовы уравнения.