Let $a,b,c,d$ are integers such that $(a,b)=(c,d)=1$ and $ad-bc=k>0$. Prove that there are exactly $k$ pairs $(x,y)$ of rational numbers with $0\leq x,y<1$ for which both $ax+by,cx+dy$ are integers.

What I did Let $ax+by=m$ and $cx+dy=n$, solving them we get $y=\frac{na-mc}{k}$ since $0\leq y<1\Rightarrow na-mc<k$ So $na-mc$ can take the values $0,1,2,...,k-1$ and so $y$ assumes $k$ values so does $x$, thus there are exactly $k$ ordered pairs. Well I haven't used the condition of gcd which makes me think its wrong, I am thinking of making the argument right or find a new one. Please help.


Note that I do not need the conditions $\gcd(a,b)=1$ and $\gcd(c,d)=1$ here. Therefore, these conditions are omitted in the proof below.

Let $\textbf{A}:=\begin{bmatrix}a&b\\c&d\end{bmatrix}$. Suppose that $\textbf{x}:=\begin{bmatrix}x\\y\end{bmatrix}\in\mathbb{Q}^2$ satisfies $\mathbf{A}\,\mathbf{x}=\mathbf{b}$, where $\mathbf{b}=\begin{bmatrix}u\\v\end{bmatrix}\in\mathbb{Z}^2$. Then, clearly, $$\mathbf{x}=\mathbf{A}^{-1}\,\mathbf{b}\in\left(\frac{1}{k}\mathbb{Z}\right)^2\,.$$ Now, let $X:=kx$ and $Y:=ky$. Then, we are interested in integers $X,Y$ such that $0\leq X,Y<k$ and $$aX+bY=ku\text{ and }cX+dY=kv$$ with $u,v\in\mathbb{Z}$.

Let $l:=\gcd(b,d)$. Now, for each $i=0,1,2,\ldots,m-1$, where $m:=\frac{k}{l}\in\mathbb{Z}_{>0}$, we shall show that there exist exactly $l$ pairs $(X,Y)$ with $X=li$ and $0\leq Y<k$ that satisfies the condition.

If $X=li$, then $bY=ku-ali=l(mu-ai)$ and $dY=kv-cli=l(mv-ci)$, whence it follows that $dl(mu-ai)=bl(mv-ci)$, or $$m(du-bv)=(ad-bc)i=ki=mli\,.$$ That is, $du-bv=li$. Because $\gcd(b,d)=l$, there exist such $u$ and $v$, say, $(u,v)=\left(u_0,v_0\right)$, and other solutions are $$(u,v)=\left(u_0+\frac{b}{l}t,v_0+\frac{d}{l}t\right)$$ for some $t\in\mathbb{Z}$. Then, we need $$\left(ku_0-ali\right)+k\frac{b}{l}t=ku-ali=bY\in\big\{0,b,2b,\ldots,(k-1)b\big\}\,.$$ Hence, $mt+\frac{l\left(mu_0-ai\right)}{b}\in\{0,1,2\ldots,(k-1)\}$ (noting that $b\mid l\left(mu_0-ai\right)$). There exist exactly $l=\frac{k}{m}$ values of $t$ that satisfies this condition, whence there exist exactly $l$ values of$Y$, provided $X=li$.

Conversely, from $d(ku-aX)=bd Y=b(kv-cX)$, we get $du-bv=X$. This equation shows that, if $(X,Y)$ is a solution, then $l$ must divide $X$. Therefore, there are exactly $lm=k$ pairs $(X,Y)$, whence also $(x,y)$, with the required properties.

Alternative Solution

Let $K:=\big\{\textbf{A}\,\textbf{x}\,|\,\textbf{x}\in[0,1)^2\big\}$. Denote by $I$ the number of interior integral points of $K$, and $B$ the number of integral boundary points of the topological closure $\bar{K}$ of $K$. It is obvious that the number of integral boundary points of $K$ is $\frac{B}{2}-1$. Since $\textbf{A}$ is invertible, the number of rational solutions $\textbf{x}\in[0,1)^2$ to the condition $\textbf{A}\,\textbf{x}\in\mathbb{Z}^2$ is precisely the number of integral points in $K$, which is $I+\frac{B}{2}-1$. Due to Pick's Theorem, the area of $\bar{K}$, which is $k$, must be equal to $I+\frac{B}{2}-1$. Consequently, there are exactly $k$ rational solutions $\mathbf{x}\in[0,1)^2$.

This result holds in $n$ dimension. See Number of Rational Solutions $\mathbf{x}\in[0,1)^n$ to the Matrix Condition $\mathbf{A}\,\mathbf{x}\in\mathbb{Z}^n$.


The gcd comes in when you say that "na−mc can take the values 0,1,2,...,k−1".

If the gcd is not 1, there are fewer distinct values.

  • $\begingroup$ Thanks a lot, I see you mean that as gcd is the least possible positive value of "$ka+lb$". $\endgroup$ – gambler101 Jul 15 '16 at 22:48

Answer currently incomplete

You correctly showed that we must have $x,y \in \{0,1,2,3\ldots,k-1\}$. That doesn't mean there are $k$ values for $x$, it means there are at most $k$ values for $x$.

Moreover, you've shown at most $k$ possibilities for $x$ and at most $k$ possibilities for $y$; it doesn't immediately follow that there are at most $k$ possibilities for $(x,y)$; rather, there are at most $\boldsymbol{k^2}$ possibilities for $(x,y)$.

So we need to reason further. What you have so far gives $x = \frac{i}{k}$, $y = \frac{j}{k}$ for some $i,j$ such that $0 \le i, j < k$. Plugging these into the equations, we must have \begin{align*} ax + by \in \mathbb{Z} &\implies k \mid ai + bj \\ cx + dy \in \mathbb{Z} &\implies k \mid ci + dj \\ \end{align*}

Let's fix $i$ to be between $0$ and $k-1$, arbitrairly. We want to show there is exactly one possible value of $j$.

(Don't have time to finish now. It's a little more involved from here than I expected. Ideas in the comments or ping me if you want me to think about it some more some other day.)

  • $\begingroup$ "We want to show there is exactly one possible value of $k$" isn't $k$ already fixed? $\endgroup$ – gambler101 Jul 16 '16 at 11:33
  • $\begingroup$ @jonathan3951 you are right. That was just a typo $\endgroup$ – 6005 Jul 16 '16 at 12:41

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.