Say I have two rational numbers $a/b$ and $c/d$ where $a,b,c,d$ are integers and $a<b$ and $c<d$, and $a$ coprime with $b$, and $c$ coprime with $d$. Assume $b,d$ are free and not necessarily coprime, and also that $d>b$ with $d$ not a power of $b$. Let $\ell = \mathrm{lcm}(b,d)$, and set $a' = a\ell/b$, $c'=c\ell/d$. Clearly $a', c'$ are not coprime with $\ell$. I want to show that there exists integers $i,j$ such that $ia' + jc'$ is coprime with $\ell$.

Example: $a,c=1$, $b=40, d=60$. So $\ell = 120$ and $a'=3,c'=2$. Then $\mathrm{gcd}(a'+c'=5,120=\ell)\neq 1$, but $(a'+2c'=7,120)=1$.

I tested it on a computer and it seems true for $a,b,c,d$ less than 100. I think I can prove it, but before I spend more time on it I thought to ask if the answer already exists, or this is an instance of a well-known number theoretic result.

  • $\begingroup$ Why do you restrict "$d$ is not a power of $b$"? I think your claim is true even if $d$ is a power of $b$; however if $d$ is a multiple of $b$ then the claim "$a', c'$ are not coprime with $l$" is false, but this does not affect that the claim is still true in that case. $\endgroup$ – alphacapture Jun 27 '17 at 21:39
  • $\begingroup$ Right, and very astute of you. That restriction is not really necessary, but the reason I put it in there is that this is part of a larger problem and if $d$ is a power of $b$ then my result follows trivially. $\endgroup$ – Wapiti Jun 27 '17 at 23:44
  • $\begingroup$ @alphacapture Correct, we need only $\,(a',c',\ell) = 1,\,$ true by $\,(a,b)=1=(c,d)\,$ and $\,\ell = {\rm lcm}(b,d),\,$ see my answer. $\endgroup$ – Bill Dubuque Jun 28 '17 at 0:35

Note $\ \,\overbrace{(a\ell/b,\,c\ell/d,\,\ell)}^{\Large\ \ (a',\,\ c',\,\ \ell)} = (a\ell/b,\, b\ell/b,\,c\ell/d,\,d\ell/d)=(\overbrace{(a,b)}^{1}\ell/b,\,\overbrace{(c,d)}^{1}\ell/d)=1\,$ by here.

Hence $\,(ia'+c',\,\ell) = 1\ $ for some $\,i\,$ by this Stieltjes / Euclid variant.

Remark $ $ Or, more simply, we can use the $\rm\color{#c00}{Bezout\ gcd\ identity}$ instead of Stieltjes

$$\ 1 = (a',c',\ell) = (\color{#c00}{(a',c')},\,\ell) = (\color{#c00}{ia'+jc'},\,\ell)$$

e.g. in your given example $\, 1 = (3,2,120)\! = ((3,2),120) = (3\!-\!2,120)$

  • $\begingroup$ The linked proof is constructive, i.e. it shows how to compute such an $i.\ \ $ $\endgroup$ – Bill Dubuque Jun 27 '17 at 23:29
  • $\begingroup$ Thanks. My lack of number theory is exactly what led me to ask here, and it seems to have been a good idea. The link seems to draw on a preexisting technique in the art. I'll check this when I have more time. $\endgroup$ – Wapiti Jun 27 '17 at 23:42
  • $\begingroup$ @Wapiti I simplified it further. $\endgroup$ – Bill Dubuque Jun 27 '17 at 23:56
  • $\begingroup$ Wow no kidding. $\endgroup$ – Wapiti Jun 27 '17 at 23:58
  • $\begingroup$ You are quite welcome to ask about any step that is not clear and I will be happy to elaborate. $\endgroup$ – Bill Dubuque Jun 27 '17 at 23:59

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.