Problem 1376

To find an irreducible fraction with a denominator not greater than 2005 that is closest to $\frac{9}{25}$ but is not $\frac{9}{25}$, we can use the following steps:

1. **Express the difference between $\frac{9}{25}$ and another fraction $\frac{p}{q}$:**
$$\left|\frac{9}{25} - \frac{p}{q}\right| = \left|\frac{9q - 25p}{25q}\right|$$
We want to minimize this difference.

2. Consider the case where the absolute difference is 1:
$$|9q - 25p| = 1$$
This can be split into two cases:
- $9q - 25p = 1$
- $9q - 25p = -1$

3. **Solve the Diophantine equation $9q - 25p = 1$:**
- We can find a particular solution to this equation using the Extended Euclidean Algorithm. One particular solution is $(p, q) = (5, 14)$.
- The general solution to the equation $9q - 25p = 1$ is given by:
$$p = 5 + 25k, \quad q = 14 + 9k$$
- We need to find the largest integer $k$ such that $q \leq 2005$:
$$14 + 9k \leq 2005 \implies 9k \leq 1991 \implies k \leq \frac{1991}{9} \implies k \leq 221$$
- The largest integer $k$ is 221. Substituting $k = 221$ into the general solution:
$$p = 5 + 25 \cdot 221 = 5 + 5525 = 5530$$
$$q = 14 + 9 \cdot 221 = 14 + 1989 = 2003$$
- Thus, one possible fraction is:
$$\frac{5530}{2003}$$

4. **Solve the Diophantine equation $9q - 25p = -1$:**
- We can find a particular solution to this equation using the Extended Euclidean Algorithm. One particular solution is $(p, q) = (4, 11)$.
- The general solution to the equation $9q - 25p = -1$ is given by:
$$p = 4 + 25k, \quad q = 11 + 9k$$
- We need to find the largest integer $k$ such that $q \leq 2005$:
$$11 + 9k \leq 2005 \implies 9k \leq 1994 \implies k \leq \frac{1994}{9} \implies k \leq 221$$
- The largest integer $k$ is 221. Substituting $k = 221$ into the general solution:
$$p = 4 + 25 \cdot 221 = 4 + 5525 = 5529$$
$$q = 11 + 9 \cdot 221 = 11 + 1989 = 2000$$
- Thus, another possible fraction is:
$$\frac{5529}{2000}$$

5. **Compare the two fractions to find the closest one to $\frac{9}{25}$:**
- Calculate the difference for each fraction:
$$\left|\frac{9}{25} - \frac{5530}{2003}\right| = \left|\frac{9 \cdot 2003 - 25 \cdot 5530}{25 \cdot 2003}\right| = \left|\frac{18027 - 138250}{50075}\right| = \left|\frac{-120223}{50075}\right| \approx 2.4$$
$$\left|\frac{9}{25} - \frac{5529}{2000}\right| = \left|\frac{9 \cdot 2000 - 25 \cdot 5529}{25 \cdot 2000}\right| = \left|\frac{18000 - 138225}{50000}\right| = \left|\frac{-120225}{50000}\right| \approx 2.4$$

Since both differences are approximately the same, we can choose either fraction. However, the fraction with the smaller denominator is generally preferred.