Will some $m$ and $n$ always exist for $m(coprime_1)-n(coprime_2)=1$? That is, is it guaranteed that, given any $2$ numbers, $p$ and $q$, such that $(p,q)=1$, there will exist $m$ and $n$ so that $mp-nq=1$?
It seems  like there should be, but it would be nice to have a proof without much abstract algebra used.
 A: Yes. 
Called Bezout identity.
It says slightly more generally that for all $a,b\in\Bbb Z\ \exists x,y\in\Bbb Z:\ xa+yb=(a,b)\ $  where $(a,b)$ is the greatest common divisor.
And the proof relies on identifying the element of minimal absolute value among all elements of the form $xa+yb$.
A: Yes, by the Bezout identity for the gcd (special case gcd $=1).$ Below is a simple proof by induction. See here for a more conceptual proof, which lends greater insight into the essence of the matter.
Theorem $\rm\ \ gcd(m,n) = j\,m + k\,n\ $ for some $\rm\,j,k\in\Bbb Z.$
Proof $\ $ By induction on $\rm\, m\!+\!n.\:$ Trivial if $\rm\,m\,$ or $\rm\,n = 0,\:$ or if $\rm\,m = n.\:$ Else, wlog, $\rm\,m > n > 0.\,$
$$\begin{eqnarray}\rm\ \ gcd(m,n) &=&\,\rm gcd(m\!-\!n,n)\quad&&\text{by Lemma below}\\
&=&\,\rm j\, (m\!-\!n) + k\, n\quad&&\text{by induction (applies since}\rm\: (m\!-\!n)\!+\!n < m\!+\!n)\\
&=&\,\rm j\,m + (k\!-\!j)\, n\quad&&{\bf QED}\end{eqnarray}$$
Lemma $\rm\ \ gcd(m\!-\!n,n) = gcd(m,n)$
Proof $\ $ If $\rm\:c\,|\,n\:$ then $\rm\:c\,|\,m\!-\!n\iff c\,|\,m.\:$ Thus $\rm\,m\!-\!n,n\,$ and $\rm\,m,n\,$ have the same set $\rm\,C\,$ of common divisors $\rm\,c,\,$ hence they have the same greatest common divisor (= max $\rm\, C).$
Remark $\ $ By interpreting the inductive step procedurally, one easily derives a very simple extended Euclidean algorithm to compute the Bezout linear representation of the gcd.
