Mock AIME 4 2006-2007 Problems/Problem 9

Problem

Compute the smallest positive integer $k$ such that the fraction

$\frac{7k+100}{5k-3}$

is reducible.

Solution

Suppose $p>1$ is a common divisor of $7k+100$ and $5k-3$. Then $p$ also divides $a\cdot (7k+100) + b\cdot (5k-3)$ for integers $a,b$. Putting $a=5$ and $b=-7$ gives $p|521$. Since $521$ is prime and $p>1$, we have $p=521$. Thus $521$ divides $5k-3$, or $5k-3\equiv0\pmod {521}$ or $k\equiv 209\pmod {521}$. Since we are looking for the smallest positive solution, our answer is $209$.