Решение диофантовых уравнений для С7(19)

1 Постановка задачи, или что такое диофантово уравнение

В задаче на свойства чисел С7(19) довольно часто возникает необходимость решить диофантово уравнение:

$$Ax+By = C$$

Здесь целые коэффициенты $A$ и $B$ должны быть взаимно простыми числами, то есть, иметь наибольший общий делитель, равный 1. Решение мы ищем в целых числах.

 

2 Рассмотрим частный пример

Например, требуется решить уравнение

$$9x+5y = 1$$

 Приведем один из способов решения. Их несколько, но мы приводим самый простой.

1 Найдем частное решение, то есть, подберем любые целые $x_0$ и $y_0$, удовлетворяющие этому уравнению. Находим, например:

$$x_0=-1$$
$$y_0=2$$
$$9\cdot(-1)+5\cdot(2)=1$$

2 Общее решение теперь дается формулами

$$x=-1+5n$$

$$y=2-9n, n \in Z$$

3 Решение в общем виде

Обобщая,

запишем общее решение

$$x=x_0+Bn$$

$$y=y_0-An, n \in Z$$


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