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.

  • $\begingroup$ 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$. $\endgroup$ – robjohn Oct 13 '14 at 2:06

Your assumption is indeed correct.

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.

  • $\begingroup$ 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$ ? $\endgroup$ – llort Oct 12 '14 at 9:23
  • $\begingroup$ It means I messed up, should be $1$. Thanks. $\endgroup$ – Some Math Student Oct 12 '14 at 9:23
  • $\begingroup$ 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. $\endgroup$ – Some Math Student Oct 12 '14 at 9:30
  • $\begingroup$ 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. $\endgroup$ – robjohn Oct 13 '14 at 2:31
  • $\begingroup$ 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? $\endgroup$ – 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 $$

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

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.