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


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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.