How: For how to do it, look for the Extended Euclidean Algorithm. It is not particularly hard to carry out, but a proper description would be quite lengthy. The Extended Euclidean Algorithm is also described in most books on Elementary Number Theory. There are many computer implementations, but for $a$ and $c$ of modst size, the procedure can be easily carried out by hand.
If $d$ is the greatest common divisor of $a$ and $c$, the Extended euclidean algorithm produces integers $x$ and $y$ such that $ax+d=cy$. But from that one can solve your more general problem.
Existence of solution: Certainly there do not always exist such $m$ and $n$. For example, let $a=2$, $b=1$, $c=2$. Then $an+b$ (that is, $2n+1$) is always odd, and $cm$ (that is, 2m$) is always even, so they can never be equal.
In general, if the greatest common divisor of $a$ and $c$ divides $b$, there always is a solution. If the greatest common divisor of $a$ and $c$ does not divide $b$, there is no solution.
Infinitely many solutions: If there is a solution $(n_0,m_0)$, then there are infinitely many solutions. For suppose that $an_0+b=cm_0$. Then for any integer $t$, we have
$$a(n_0 +ct)+b=c(n_0+at).$$
(Just expand. There will be a term $act$ on the left, and a term $cat$ on the right, and they cancel.)
So if $(n_0,m_0)$ is a solution, then so is $(n_0+ct, m_0+at)$ for any positive integer $t$.
Try
$$ 31 \cdot 16^n $$
It begins with the observation that $x^4 \equiv 0, 1 \pmod {16}$ but there is more to be done
For $31 \cdot 16^n$ with $n \geq 1,$ if any of the fourth powers are odd, there are at least sixteen odd fourth powers. On the other hand, if we have all even numbers, then dividing each by $2$ gives a representation of $31 \cdot 16^{n-1},$ so induction says sixteen are required
Best Answer
Lets look for $2^n$ formula that might work:
$(2^k)^5+(2^l)^7=(2^n)^9$
so we know $2^t+2^t=2^{t+1}$
Than we look for $5 k=7l=9n-1$
$k=\frac{9n-1}{5}, l=\frac{9n-1}{7}$
we are looking for int, so you want the fractions to be integers.
It means $7|9n-1$ and $5|9n-1$ which is $35|9n-1$
Just from a look, you can tell $n=4$ will work
So $x=2^7, y=2^5, z=2^4$