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.

Question

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.

Answer 1

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

Answer 2

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.

Answer 3

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