How do I find all integers that satisfy this condition?

Question

Suppose that $72x + 56y = 40$. Find all $x,y$ that satisfy this condition.

Here is what I did:

1. I reduced the equation to give $9x + 7y = 5$
2. But since 5 is relatively prime to 7 and 9, we know $x,y$ is divisible by 5. So we can reduce the equation to $9(5a) + 7(5b) = 5$.
3. Simplifying, we get $9a + 7b= 1$. Would it be easier to continue along this direction, i.e. to find some $a,b$ such that their gcd is one? I cannot continue beyond this as I have no other insights left.

What kind of available theorems/techniques can I use to solve this?

Answer 1

write $$7y\equiv 5\mod 9$$ so $$y\equiv \frac{5}{7}\equiv \frac{14}{7}\equiv 2\mod 9$$ and we find $x$ as $$9x+7(2+9k)=0$$ so $$x=-1-7k$$

Answer 2

$$9x+7y=5$$

First, you find a solution. \begin{array}{rcll} 5-7(1) &= &-2 \\ 5-7(2) &= &-9 \\ 9(-1) + 7(2) &= &5 \end{array}

Because $\gcd(9,7)=1$, the general solution is

$$(x,y) = (-1+7t, 2-9t)$$

for all $t \in \mathbb Z$.

Now take the general case $9x+7y=5$ and subtract $9(-1)+7(2)=5$.

\begin{array}{cccc} 9x &+ &7y &= &5 \\ 9(-1) &+ &7(2) &= &5 \\ \hline 9(x+1) &+ &7(y-2) &= &0 \\ &&9(x+1) &= &7(2-y) \end{array}

Since $9$ and $7$ are relatively prime, then $9$ must divide $2-y$, let's say $ 2-y = 9t$ for some integer, $t$. Hence $y = -9t + 2$ for some integer, $t$. Substituting that back into $9(x+1) = 7(2-y)$, we get $9(x+1)=63t$. We can simplify that to $x = 7t - 1$.

So the most general solution is

$$9(7t-1) + 7(-9t+2) = 5$$