Alternative proof for elementary number theory lemma Let $a, b \in \mathbb{N}, (a,b) =1$.Then for any $c \in \mathbb{N}, c \ne a, b$, there is an $m \in \mathbb{N}$ s.t. $$(c, a + bm) = 1$$ 
I can solve this using general principles, but found it as an exercise in a chapter of a book on representing integers using unique prime factorization. I would be curious to see an (ideally elegant) proof using only that.  
 A: 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\,$ 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\:$ 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
Suppose $\,(a,b,c)= 1.\,$ We  seek $\,\color{#c00}{a}+\color{#0a0}{bm}\,$ coprime to $\,c,\,$  so it suffices to choose $\,m\,$ such that each prime factor $\,p\,$ of $\,c\,$ divides exactly one of $\,a\,$ or $\,bm.\,$ Note $\,p\,$ can't divide both $\,a,b,\,$ else $\,p\mid a,b,c.\,$ So it suffices to let $\,m\,$  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), i.e. the problem reduce from a problem in number theory to a trivial problem in set theory.
