Problem 5. Let $a, b, c$ and $d$ be positive integers such that there are exactly 2004 ordered pairs $(x, y), x, y \in(0,1)$, for which $a x+b y$ and $c x+d y$ are integers. If $(a, c)=6$, find $(b, d)$.

Oleg Mushkarov, Nikolai Nikolov
5. The answer is 1,7 or 49 .

Suppose first that $a d \neq b c$. The set of points $(a x+b y, c x+d y), x, y \in$ $(0,1)$, coincides with the interior of the parallelogram with vertices $A=(0,0)$, $B=(a, c), C=(b, d)$ and $D=(a+b, c+d)$. Its area $S$ equals $|a d-b c|$. The Pick formula implies that $S=n+\frac{m}{2}-1$, where $n$ (respectively $m$ ) denotes the number of lattice points (i.e., with integer coordinates) in the interior (respectively on the boundary) of the parallelogram. Set $e=(a, c), f=(b, d)$, $a=e a_{1}, c=e c_{1}, b=f b_{1}$ and $d=f d_{1}$. The interior points of the side $A B$ have coordinates $(a x, c x), x \in(0,1)$. Thus the number of such lattice points is $e-1$. Analogously, the number of the interior lattice points on $B D, C D$ and $A C$ equals $f-1, e-1$ and $f-1$, respectively. Consequently $\frac{m}{2}=e+f$ and the first condition of the problem can be written as

$$
e f\left|a_{1} d_{1}-b_{1} c_{1}\right|=2003+e+f
$$

Since $e=(a, c)=6$, it follows that $f$ divides $2009=7^{2} .41$ and $6 f$ divides $2009+f$. This is possible only for $f=1,7,49$. For each of these values of $f$ the numbers $e=6, a_{1}=1+\frac{2009+f}{6 f}, b_{1}=c_{1}=d_{1}=1$ satisfy (1) and hence $(b, d)=1,7$ or 49 .

Suppose now that $a d=b c$. It is easy to see that $a_{1}=b_{1}$ and $c_{1}=d_{1}$. For $x \in\left(0, \frac{1}{e}\right)$ set $y=\frac{1-x e}{f}<\frac{1}{f}$. Then $a x+b y=a_{1}$ and $c x+d y=c_{1}$ are integers, and $e x+f y=1$. It follows that in this case there are infinitely many pairs $(x, y)$ satisfying (1), a contradiction.