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.

  • 2
    $\begingroup$ There is some condition missing, as is, choose $a = 2, b = 4, c = 6$. $\endgroup$ – Daniel Fischer Jul 3 '14 at 15:06
  • $\begingroup$ 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) $\endgroup$ – 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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.