# When do positive integers $0<q_1<k_1$ and $0<q_2<k_2$ exist such that $q_1k_1+q_2k_2=k_1k_2$?

Let $k_1$ and $k_2$ be positive integers. When do positive integers $0<q_1<k_1$ and $0<q_2<k_2$ exist such that $q_1k_1+q_2k_2=k_1k_2$?
I believe that these exist precisely when gcd$(k_1,k_2) \neq 1$. Is this correct? Does somebody have a proof? Examples: for $k_1=3, k_2=6$, one has $4 \cdot 3 + 1 \cdot 6 = 18$ and $2 \cdot 3 + 2 \cdot 6 = 18$. However, for $k_1=2$, $k_2=3$, this never seems to happen.

• Are you sure you don't want the same conditions except $q_2k_1+q_1k_2=k_1k_2$? Otherwise, $k_1=2$ $k_2=6$ has no solution satisfying the given conditions. Note that your solution $4\cdot3+1\cdot6=18$ does not meet the criteria given since $4\ge3$. – robjohn Oct 13 '14 at 2:06

First, we show that it is a necessary condition:

Assume $GCD(k_1,k_2)=1$. If you take a look at your equation, we gain $k_2|q_1, k_1|q_2$ (why?).

Since $q$ cannot be $0$, this leaves us with $q_1k_1+q_2k_2\geq k_1k_2+k_2k_1=2k_1k_2>k_1k_2$.

Now, to prove that our condition is sufficient, we say $k_1=l_1d, k_2=l_2d$, where $GCD(l_1,l_2)=1$.

Now the equation writes $d(q_1l_1+q_2l_2)=d^2l_1l_2 \Leftrightarrow q_1l_1+q_2l_2=dl_1l_2$.

If we say $q_1=l_2r_1, q_2=l_1r_2$, putting that in leaves us with $r_1+r_2=d$, which can be fulfilled due to $d>0$ and leaves us with a solution.

• In the first part: what does $gcd(k_1,k_2)=0$ mean? In the second part: "k_1=l_1d,k_2=l_2d..." doesn't this mean that $1=gcd(k_1,k_2) \geq d$ ? – llort Oct 12 '14 at 9:23
• It means I messed up, should be $1$. Thanks. – Some Math Student Oct 12 '14 at 9:23
• For the second one, it means that $gcd(k_1,k_2)=d$, since we later state that $l_1,l_2$ are coprime. Also, if you simply edit your comment to add another question, I am probably not going to notice - you can always write a new one and delete it later on, no worries there. – Some Math Student Oct 12 '14 at 9:30
• Something must be off in the proof of sufficiency, since $(2,6)=2$ yet the only non-negative solutions are $$0\cdot2+2\cdot6=2\cdot6\\ 3\cdot2+1\cdot6=2\cdot6\\ 6\cdot2+0\cdot6=2\cdot6$$ and none of these meet the conditions as given. – robjohn Oct 13 '14 at 2:31
• I don't think there is - according to the proof, we have $d=2,l_1=1,l_2=3$, and then we choose $r_1,r_2$ such that $r_1+r_2=d$, in this case $r_1=r_2=1$ and say $q_1=l_2r_1=3\cdot 1=3, q_2=l_1r_2=1\cdot 1=1$, giving us our (only) solution. Did I miss something here? – Some Math Student Oct 13 '14 at 14:19

I am assuming that the conditions were $0\lt q_1\lt k_1$ and $0\lt q_2\lt k_2$ and $q_2k_1+q_1k_2=k_1k_2$. Otherwise, there is a counterexample.

If $(k_1,k_2)=d$ and $d\gt1$, then for each $0\lt j\lt d$, we have the solutions $$k_1k_2=\frac{jk_2}{d}k_1+\frac{(d-j)k_1}{d}k_2\tag{1}$$ where $0\lt\frac{jk_2}{d}\lt k_2$ and $0\lt\frac{(d-j)k_1}{d}\lt k_1$.

Suppose that $a_1k_1+a_2k_2=1$ and that we have a solution $$k_1k_2=q_2k_1+q_1k_2\tag{2}$$ where $0\lt q_1\lt k_1$ and $0\lt q_2\lt k_2$. Then \begin{align} (k_2-q_2)k_1&=q_1k_2\\ a_2(k_2-q_2)k_1&=q_1(1-a_1k_1)\\ \left[a_2(k_2-q_2)+a_1q_1\right]k_1&=q_1\tag{3} \end{align} Thus, $k_1\mid q_1$ which is not possible if $0\lt q_1\lt k_1$.

$$(k_1-q_2)(k_2-q_1) = k_1k_2-k_1q_1-k_2q_2 +q_1q_2=q_1q_2$$

• ? So what ? This does not answer the question I'm afraid – Ewan Delanoy Oct 12 '14 at 9:16
• thx. yes Ewan's comment persuaded me the remark was not helpful, however i was unsure of the etiquette of simply deleting it – David Holden Oct 14 '14 at 0:32