This can be solved intuitively by using a slight twist on Euclid's idea for generating new primes. Euclid employed $\,1 + p_1\cdots p_n$ is coprime to $\,c = p_1\cdots p_n.\,$ Stieltjes noted the generalization that, furthermore, $\ \color{#c00}{p_1\cdots p_k} +\, \color{#0a0}{p_{k+1}\cdots p_n}\,$ is coprime to $\,c\,$ too, which motivates the following
Key Idea $ $ Coprimes to $\,c\neq 0\,$ arise by partitioning into $\rm\color{#c00}{two}\ \color{#0a0}{summands}$ all prime factors of $\,c,\,$ i.e.
Theorem $\ \ \color{#c00}a+\color{#0a0}b\ $ is coprime to $\ c\neq 0\:$ if every prime factor of $\,c\,$ divides $\,a\,$ or $\,b,\,$ but not both.
Proof $\ $ If not then $\,a+b\,$ and $\,c\,$ have a common prime factor $\,p.\,$ By hypothesis $\,p\mid a\,$ or $\,p\mid b.\,$ Wlog, say $\,p\mid b.\,$ Then $\,p\mid (a+b)-b = a,\,$ so $\,p\,$ divides both $\,a,b,\,$ contra hypothesis. $ $ QED
The OP seeks $\,\color{#c00}{az}+\color{#0a0}b\,$ coprime to $\,c,\,$ so it suffices to choose $\,z\,$ such that each prime factor $\,p\,$ of $\,c\,$ divides exactly one of $\,az\,$ or $\,b.\,$ Note $\,p\,$ can't divide both $\,a,b,\,$ else $\,p\mid a,b,c,\,$ contra hypothesis. Thus it suffices to let $\,z\,$ be the product of primes in $\,c\,$ that do not occur in $\,a\,$ or in $\,b.\ \ $ QED
Remark $\ $ Note how the solution becomes quite obvious after employing Stieltjes idea, amounting to nothing but a trivial calculation of a difference of sets (of primes)
Note: expensive prime factorization is not required, we can efficiently compute solutions using iterated gcds, e.g. see the $\rm gdc$ function here.
$\textbf{Exercise}$ Let $(a,b)=1$ and $c>0$. Prove that there is an integer $x$ such that $(a+bx,c)=1$.
$\textbf{Solution.}$ Let $p_{1},p_{2},\cdots,p_{m}$ be the primes which appear in the prime factorization of $b$. Then since $(a,b)=1$, we have $(a,p_{i})=1$ for all $i$. If the prime factorization of $c$ contains only primes from the set $\{p_{1},p_{2},\ldots,p_{m}\}$, then our required integer $x=0$ since $(a,p_i)=1$ for each $i$ implies $(a,c)=1$. Now suppose that $c$ contains extra primes $q_{1},q_{2},\ldots,q_{n}$. That is $c$ is of the form $$c=\prod p_{i}q_j \quad \text{or} \quad c =\prod_{i=1}^{n} q_{i}$$ then we want to find a integer $x$ such that $(a+bx,p_i)=1$ for all $i$ and $(a+bx,q_j)=1$ for all $j$. It is clear that $(a+bx,p_i)=(a,p_i)=1$. So basically we want to find an integer $x$ such that $(a+bx,q_j)=1$ for all $j$. We know that $(q_{j}+1,q_j)=1$ always so we need $x$ such that $bx+a=q_{j}+1\equiv 1\pmod{q_j}$ for all $j$, that is $bx\equiv 1-a\pmod{q_j}$ for all $j$. Since $(b,q_j)=1$ for all $j$, therefore $b$ has an inverse and so $x=(1-a)b^{-1}\pmod{q_j}$. Now the system of congruences
\begin{align*}
x &\equiv (1-a)b^{-1}\pmod{q_1}\\
x &\equiv (1-a)b^{-1}\pmod{q_2}\\
& \cdot\\
& \cdot\\
x&\equiv (1-a)b^{-1}\pmod{q_j}
\end{align*}
has a solution by Chinese Remainder Theorem and that solution is our required $x$.
$\textbf{Remark.}$ If we assume Dirichlet's Theorem then this problem can be solved as follows: Since $(a,b)=1$, The set $\{a+bx \ : x \in \mathbb{Z}\}$ contains infinitely many primes. Since $c$ is fixed so its finite so has only finitely many prime factors. Let $P$ be the largest prime factor of $c$. Now choose $x$ large enough so that $a+bx$ is a prime which is greater than $P$. Then for that $x$, $(a+bx,c)=1$.
Best Answer
Suppose $am+bn=1$. If $k$ divides both $a$ and $b$ then there exist $p$ and $q$ such that $a=kp$ and $b=kq$.
Substituting that into our first equation gives $kpm+kqn=1\implies k$ divides $1$
Therefore, $k=1$ and $a$ and $b$ are coprime.