Let $r = p/q>0$ be a rational number with $gcd(p,q)=1$.
Is it possible to find a square delimited by pairs of lines ($d_1$, $d_2$) and ($d_3$, $d_4$) such that :
- $d_1 \parallel d_2$ (blue lines) and $d_3 \parallel d_4$ (green lines)
- $d_1 \perp d_3$
- $d_1$, $d_2$, $d_3$ and $d_4$ pass through points with integers coordinates.
- The polygon delimited by those lines is a square of area $r$.
We can assume $d_1=(AB)$ where $A(0,0)$ and $B(a,b)$.
The task is possible if we can find a point $C(x,y)$ such that $d(C, (AB)) = \sqrt{r}$ because :
- we can then define $d_2$ as the parallel to $d_1$ passing through $C$.
- we define $d_3$ and $d_4$ as the rotation of $d_1$ and $d_2$ around the point $A$ with an angle of $\pm \frac{\pi}{2}$.
The distance between $d_1$ and $d_2$ is the same as the one between $d_3$ and $d_4$. So the polygon delimited by those lines has an area of $r$. The distance between $d_1$ and $d_2$ is : $$\frac{|-bx+ay|}{\sqrt{a^2+b^2}}=\sqrt{r} \Longrightarrow p(a^2+b^2)=q(ay-bx)^2$$
- For example, if $r=\frac{4}{5}$, there is a solution with $a=2$, $b=-1$, $x=0$ et $y=-1$ because $4 \times(2^2 + (-1)^2) = 5 \times(2 \times(-1) + 1\times 0)^2$ (see picture)
- If $r=\frac{1}{4}$, it is impossible. If it was, we would have four integers $a\not=0$, $b\not=0$, $x$, $y$ such that : $$a^2+b^2=4(ay-bx)^2$$ So $a$ and $b$ are both even and $a'=\frac{a}{2}$ and $b'=\frac{b}{2}$ may define a solution to the same equation leading to $a=b=0$ (by repeating this).
My questions are :
- How do we know programmaticaly if a solution exists? (no brute force)
- In that case, how do we (for arbitrary large values of $p$ and $q$) find a solution ?
I suspect this is related to gaussian integers and modular arithmetic.
By rescaling the point $B$, you may assume that $\text{gcd}(a,b) = 1$. Then by Bezout's theorem, the expression $ay-bx$, as $x$ and $y$ vary over the integers, can be made to equal any integer. So, you are asking when there is a solution to the equation $p(a^2+b^2) = qc^2$ for certain given coprime positive integers $p$ and $q$.
If $p = k^2p'$, then $k \mid c$ and writing $c' = kc$, we reduce to $p'(a^2+b^2) = qc'^2$. Hence, we may assume that $p$ is squarefree. With this assumption, it follows that $p \mid c^2$ implies that $p \mid c$. So write $d = pc$ to obtain $a^2+b^2 = pqd^2$. We are thus asking for a number of the form $pqd^2$ to be the sum of two non-zero squares.
A number is the sum of two squares if and only if all its prime divisors $r \equiv 3 \mod 4$ occur an even number of times. This condition is vacuous for the factor $d^2$, so this is possible if and only if $pq$ is the sum of two non-zero coprime squares, which is guaranteed as soon as the condition about primes $3 \mod 4$ is fulfilled, with the additional requirement that $pq$ not be a perfect square itself.