Find ALL solutions to $23x + 13y = 275$ when $x,y \ge 0$ Find ALL solutions to $23x + 13y = 275$ when $x,y \in \Bbb N$.
How can I approach this exercise? do I need to use GCD?
I got to $y = 23k + 16, x = 13t + 4$, when $k,t \in \Bbb Z$
 A: Since $ \gcd(23,13)= 1 =  4\cdot 23 -7\cdot 13$, the general integer solution for  $23x + 13y = 275$ is $x=13t+4\cdot275, y=-23t-7\cdot275$ with $t \in \mathbb Z$.
Now solve $x \ge 0, y \ge 0$ for $t$. You'll find that $t = -84, x = 8, y = 7$ is the only solution.
Indeed:
$x=13t+4\cdot275$ and $x\ge0$ imply $t \ge -1100/13 > -84.7$
$y=-23t-7\cdot275$ and $y\ge0$ imply $t \le -1925/23 < -83.6$
A: Hint :there is a linear combination of 23 and  13 that equals to 1(why?) , can you adjust this combination such that it would yield 275?
A: Hint: Use the Euclidean Algorithm to express $13$ and $23$ as a linear combination of $\gcd(13,23)=1$.
Then proceed with doing Belgi's hint.
A: This is called a linear Diophantine equation, if $x, y \in \mathbb{Z}$. There exists an algorithm on how to systematically solve it. And yes it involves the $\gcd$.
You can determine the solutions in $\mathbb{Z}$ and then restrict them to $\mathbb{N}_0$.
WA gives
$$
x = 8 - 13 k \\
y = 23 k + 7
$$
for $k \in \mathbb{Z}$.
$$
x = 8 - 13 k \ge 0 \iff k \le 8/13 \Rightarrow k \le 0 \\
y = 23 k + 7 \ge 0 \iff k \ge -7/23 \Rightarrow k \ge 0
$$
This leaves only $k=0$ and we get the solution $(x,y) = (8,7)$.
A: In this case, brute-forcing isn't completely insane.
By successive subtractions, the possible values of $275-23m$ are
$$275,252,229,206,183,160,137,114,\color{green}{91},68,45,22.$$
And by successive additions, the multiples of $13$ are
$$0,13,26,39,52,65,78,\color{green}{91},107,130,143,156,169,182,195,208,221,234,247,260,273.$$
A: In some cases it is possible to have an easy brute force search.
Here for instance the divisibility by $5$ brings great thnigs.
$23x+13y\equiv3x+3y\equiv3(x+y)\equiv275\equiv0\pmod5$ and since $3\land5=1$ we get $x+y\equiv0\pmod 5\iff x+y=5k$.
So $23x+13y=65k+10x=275$, obviously $k$ is also odd for $10$ to divide $275-65k$
$
\begin{array}{c|cccc}
k & 65k & 275-65k & x & y\\
\hline
1 & 65 & 210 & 21 & -16\\
3 & 195 & 80 & 8 & 7\\
\end{array}
$
Brute force is reduced to only 2 choices!
