The smallest positive integer that can be written in the form $72x+40y$ What is the smallest positive integer that can be written in the form $72x+40y$ where $x,y\in\mathbb{Z}$.I think it might be the greatest common divisor of it, but I am not sure if it is right.
 A: Since $$72x+40y=8(9x+5y)\ \ \ \text{and}\ \ \ 9\times (-1)+5\times 2=1,$$
the answer is $8$.
A: In general, given $a$ and $b$ not both zero, the smallest positive integer $d$ such that $ax+by=d$ has solutions in integers $x$, $y$ is the greatest common divisor of $a$ and $b$, as you surmised. This is Bezout's Theorem.
The most elementary proof of this uses the Euclidean algorithm, continuing to divide until a remainder of zero is reached; the last nonzero remainder is the greatest common divisor, and reorganizing each of the equations eventually provides an explicit formula for $d$ as a linear combination of $a$ and $b$. The Wikipedia page here gives a more detailed outline of this method.
Alternatively, if you know some group theory, let $H = \{ax+by\,\mid\,x,y\in\mathbb{Z}\}$; then clearly $H$ is a subgroup of the integers, so it is cyclic; let $d$ be the positive generator of that subgroup. Since $a, b\in H$, clearly $d$ divides both $a$ and $b$, so $d$ is a common divisor. Further, any integer dividing both $a$ and $b$ must divide any linear combination of $a$ and $b$, so it must divide $d$; thus $d$ is the greatest positive integer dividing both $a$ and $b$; i.e., their gcd.
A: Surely, you can generate only multiples of 8, since $72x+40x=8(9x+5y)$.
As you guessed, you can obtain 8, that is, exist $x$ and $y$ such that $9x+5y=1$ thanks to bezout theorem.
In this case, $x=-1$, $y=2$.
