REDACTED

CANBANKAN wrote: The mod d should be mod p. Sorry for the typo. It is fixed now.

REDACTED

This is secretly a geometry problem. This is a solution by codecode. Let $A = \{ (x,y) \in S\times T \mid kx\equiv y(\bmod\; p), 0\le x,y\le p-1\}$ Label the points $A_j = (x_j,y_j)$. The key claim is that all $A_j$ are collinear; if that's the case, observe that the points form an arithmetic sequence. Note $\max x_j - \min x_j \le s-1$, so $x_j-x_{j-1} \le \frac{s-1}{\lambda s} \le \frac{1}{\lambda}$. We can analogously get $y_j-y_{j-1} \le \frac{t}{\lambda s}$. Thus, $a=x_j-x_{j-1}, b=y_j-y_{j-1}$ works. Now let's prove our key claim: let $B$ be the convex hull of points in $A$. Then $B$ consists of at least 3 points. Let $y_j = kx_j + pv_j (v_j \in \mathbb{Z})$. Then $(x_j, y_j) = (x_j, kx_j + pv_j) = x_j (1,k) + v_j (0,p)$ Consider points $(x_j, v_j)$. Since $(x_j,v_j)$ can be obtained from $(x_j, y_j)$ through a linear transformation call $\Phi^{-1} \colon (x_j,y_j) \to (x_j,v_j)$, we can see that the corresponding points form the convex hull of the transformed shape. Note that the Jacobian of $\Phi$ is $\begin{bmatrix} 1 & k \\ 0 & p \end{bmatrix}$ which has determinant $p$. Therefore, the area of the interior of the transformed convex hull $Int(\Phi^{-1}(B))$ is $\frac 1p$ times the area of the interior of the original convex hull $Int(B)$. By Pick's Theorem, the area of $Int(\Phi^{-1}(B))$ is equal to $$ \text{(the number of interior lattice points)} + \text{(number of points on the border)}/2 - 1$$ We know there are $|A| \ge 1+\lambda s$ points in the interior or on the border of $\Phi^{-1}(B)$, so the area of $Int(\Phi^{-1}(B))$ is at least $\frac{1+\lambda s}{2}-1$. The area of $Int(B)$ is at least $p(\frac{1+\lambda s}{2}-1)$ However, we also know that $Int(B)$ is contained in $S\times T$ which has area $st$. We can check that $st < \frac{s\lambda p}{6} < p(\frac{1+\lambda s}{2}-1)$, contradiction!