Okay so the full question is:

Let $a,b,c,d$ be integers such that $GCD(a,b)=GCD(c,d)=1$ and $ad-bc=k>0$. Prove that there are exactly $k$ pairs $(x_{1},x_{2})$ of rational numbers with $0\leq x_{1},x_{2}<1$ for which both $ax_{1}+bx_{2},cx_{1}+dx_{2}$ are integers.

My question is essentially should it be $GCD(a,c) = GCD(b,d) = 1$ rather than $GCD(a,b)=GCD(c,d)=1$ in order to satisfy the conditions that there are exactly $k$ pairs $(x_{1},x_{2})$ of rational numbers with $0\leq x_{1},x_{2}<1$ for which both $ax_{1}+bx_{2},cx_{1}+dx_{2}$ are integers?

I think a counter example to this is $a=2, b=3, c=4,$ and $d=9$. However, this is not a counter example if the new conditions are used rather than the old conditions of the problem.

I will outline my attempted proof of the problem briefly.

Consider the complex numbers $a + ic, b + id$, and the parallelogram formed by these complex numbers and their sum. Any point inside this parallelogram can be expressed as $(a+ic)x_1 + (b+id)x_2 = (ax_1 + bx_2) + i(cx_1 + dx_2)$.Thus, any values of $x_1, x_2$ such that $ax_{1}+bx_{2},cx_{1}+dx_{2}$ are integers will be Gaussian integers within the parallelogram.

Now, by Pick's Theorem, $A = i + \frac{b}{2} -1$. It can be shown by cross products that the area of the parallelogram is $A = ad - bc = k$. Thus, $i = k + 1 - \frac{b}{2}$.

To prove that there are exactly $k$ ordered pairs requires showing that there $b = 4$ as then $i = k-1$, and the pairs $(x_1, x_2)$ consist of all these $i$ and the point $(0,0)$.

But from here, I don't think I can make any progress if $GCD(a,b)=GCD(c,d)=1$ as that allows contradictive examples such as the aforementioned $a=2, b=3, c=4,$ and $d=9$. But if the condition is $GCD(a,c) = GCD(b,d) = 1$ then $b=4$ necessarily, and so the theorem holds.

Sorry if this was a bit excessive or obvious, I'm still new to this kind of competition math.

  • $\begingroup$ Can you tell me why you think your counter example works? In other words, since $k=6$ in that example, can you tell me why there are more or less than 6 pairs $(x_1,x_2)$, satisfying the conditions? I found exactly six. I also think the original conditions are correct and not your conditions. $\endgroup$ – Mohan Aug 18 '17 at 20:57
  • $\begingroup$ Oh I just realised where I went wrong in that counterexample, I wasn't considering the points where $x_1 = 0$ or $x_2 = 0$ except for $(0,0)$. So that was three pairs which I didn't consider. Could you give me an idea as to why my proof is false? Or at least the fallacy in the final paragraph? $\endgroup$ – Cameron Eggins Aug 19 '17 at 4:34
  • $\begingroup$ Ah wait, I think I might have it. So now considering those boundary points where $x_1 = 0$ or $x_2 = 0$, we have the total number of points which corresponds to certain ordered pairs is $i + b/2 -1 = k$, as required. So that should be the proof completed, but then I didn't use the conditions of $GCD(a,b) = GCD(c,d) = 1$. $\endgroup$ – Cameron Eggins Aug 19 '17 at 4:40

Your Answer

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

Browse other questions tagged or ask your own question.