# Prove sum of numerators is coprime with denominator obtained by lcm

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.

• 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. – alphacapture Jun 27 '17 at 21:39
• 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. – Wapiti Jun 27 '17 at 23:44
• @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. – Bill Dubuque Jun 28 '17 at 0:35

## 1 Answer

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)$

• The linked proof is constructive, i.e. it shows how to compute such an $i.\ \$ – Bill Dubuque Jun 27 '17 at 23:29
• 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. – Wapiti Jun 27 '17 at 23:42
• @Wapiti I simplified it further. – Bill Dubuque Jun 27 '17 at 23:56
• Wow no kidding. – Wapiti Jun 27 '17 at 23:58
• You are quite welcome to ask about any step that is not clear and I will be happy to elaborate. – Bill Dubuque Jun 27 '17 at 23:59