Решение линейных уравнений в целых числах

В некоторых случаях нужно решить линейное уравнение или систему линейных уравнений в целых числах. Это означает, что решения должны быть целочисленные. Уравнения решения, которых следует искать в целом виде, называются диофантовыми уравнениями. При этом уравнения не обязательно являются линейными.

Пример 1 Решить уравнение с двумя переменными  в целых числах.Полагая , мы получим общее решение . Здесь   - любое действительное число. Если  принимает целые значения, то и решение будет целочисленным. Если же  - не целое, то и решение целочисленным не будет.

Как же находить целочисленные решения? Ну, в предыдущем примере мы их всех и нашли. А как же поступить, если уравнение не такое простое. Приведем пример:

Пример 2 Решить уравнение с двумя переменными  в целых числах.Поскольку правая часть уравнения делится на , то и левая часть должна делиться на . Так как мы будем искать только целочисленные решения, а  делится на  при целом , то  должно делиться на . Поскольку  и  взаимно простые, то  должно делиться на . Обозначим . Подставляя в уравнение и сокращая левую и правую части на  получим новое уравнение уже относительно  и : 

Теперь запишем общее решение исходного уравнения:. Заметим, что это записаны все решения исходного уравнения. Целочисленные решения будут получиться только при целых значениях . Итак ответ:. Здесь и далее через  будут обозначаться целые числа. 

Некоторые задачи могут приводить к решению диофантовых уравнений.

Задача 1 За купленный товар нужно заплатить  рубль. У покупателя только монеты по р., а у продавца только монеты по р. Как следует заплатить?

Пусть покупатель заплатит  монет, а продавец даст сдачу  монет. Следует решить уравнение

в целых неотрицательных числах.

Правая часть уравнения нечетная, следовательно, и левая должна быть нечетной. А это возможно, только если  целое число. Подставляя это выражение в уравнение получим: 

 Мы получили целочисленное решение уравнения:, где   целое число. Неотрицательные решения уравнения начинаются со значения . Поэтому, в качестве оптимального решения можно остановиться на таком: платим  пятирублевых монет, а сдача -  двухрублевые монеты. Отметим, что целочисленные положительные решения получаются и такие: 

 и так далее. 

Задача 2 По кольцевому маршруту длиной  км движутся в одну сторону три велосипедиста со скоростями  и км в час соответственно. В какой - то момент они встречаются. Через какое время после встречи велосипедисты опять встретятся?Обозначим искомое время через . Тогда велосипедисты проедут  и км соответственно. Если они встречаются, то разности между этими расстояниями будут целыми числами кратными . То есть  

 и .

То есть и . Здесь  - натуральные числа, так как . Минимальное значение  при котором удовлетворяются оба уравнени получается при . То есть встреча произойдет через  часа. За это время велосипедисты проедут соответственно  и километров.