information:extraction, information:filtering
One equation

The simplest linear Diophantine equation takes the form a x + b y = c, {\displaystyle ax+by=c,} where a, b and c are given integers. The solutions are described by the following theorem:

Proof: If d is this greatest common divisor, Bézout's identity asserts the existence of integers e and f such that ae + bf = d. If c is a multiple of d, then c = dh for some integer h, and (eh, fh) is a solution. On the other hand, for every pair of integers x and y, the greatest common divisor d of a and b divides ax + by. Thus, if the equation has a solution, then c must be a multiple of d. If a = ud and b = vd, then for every solution (x, y), we have a (x + k v) + b (y − k u) = a x + b y + k (a v − b u) = a x + b y + k (u d v − v d u) = a x + b y, {\displaystyle {\begin{aligned}a(x+kv)+b(y-ku)&=ax+by+k(av-bu)\\&=ax+by+k(udv-vdu)\\&=ax+by,\end{aligned}}} showing that (x + kv, y − ku) is another solution. Finally, given two solutions such that a x 1 + b y 1 = a x 2 + b y 2 = c, {\displaystyle ax_{1}+by_{1}=ax_{2}+by_{2}=c,} one deduces that u (x 2 − x 1) + v (y 2 − y 1) = 0. {\displaystyle u(x_{2}-x_{1})+v(y_{2}-y_{1})=0.} As u and v are coprime, Euclid's lemma shows that v divides x − x, and thus that there exists an integer k such that both x 2 − x 1 = k v, y 2 − y 1 = − k u. {\displaystyle x_{2}-x_{1}=kv,\quad y_{2}-y_{1}=-ku.} Therefore, x 2 = x 1 + k v, y 2 = y 1 − k u, {\displaystyle x_{2}=x_{1}+kv,\quad y_{2}=y_{1}-ku,} which completes the proof.