# why this Diophantine equation $2ks=(5t+3)(16t+9)$ has always a solution for every $k$?

I would like to solve the following Diophantine equation and show that it has always a solution; i.e. for every positive integer $k$, there exists an integer $t$ such that the fraction is an integer: $$\frac{(5t+3)(16t+9)}{2k}$$ Any hint will be grateful.

P.S.: Without considering cases for $k\equiv 0,1,2,3,4(\mod5)$.

## 1 Answer

Note that $t$ will have to be odd, say $2w+1$, so we want $(5w+4)(32w+25)$ to be divisible by $k$. Let $k=2^a5^b l$ where $l$ is divisible neither by $2$ nor by $5$. We will succeed if we can find a value of $w$ such that $5w+4$ is divisible by $2^a$ and $32w+25$ is divisible by $5^bl$. So we want to solve the system of congruences $$5w\equiv -4\pmod{2^a},\qquad 32w\equiv -25\pmod{5^b l}.$$ By multiplying the first congruence through by the inverse of $5$ modulo $2^a$, and the second congruence by the inverse of $32$ modulo $5^bl$, we obtain a system of congruences of the shape $w\equiv c\pmod{2^a}$, $w\equiv d\pmod{5^bl}$. By the Chinese Remainder Theorem, this system has a solution.

• Thanks. I think $q$ must be replaced by $l$. – asad Oct 29 '15 at 7:17
• Thanks for telling me. Midway through I changed my mind about what letter to use! Fixed. – André Nicolas Oct 29 '15 at 7:26