# 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.

• There is some condition missing, as is, choose $a = 2, b = 4, c = 6$. – Daniel Fischer Jul 3 '14 at 15:06
• Thanks. I forgot one. Hold on. @DanielFischer (it's not hard to see how it's true, and how to show it; but I fail to see how the fundamental theorem of arithmetic would be a natural (elegant) entry point) – gnometorule Jul 3 '14 at 15:09

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.

• That is elegant. :) My proof isn't all that different, but this is so nice and clear. Tyvm. – gnometorule Jul 3 '14 at 15:21