For how many values of $n\in \mathbb{N}$ less than $250$, $\frac{7n-3}{8n-5}$ can be simplified

Question

For how many values of $n$, where $n$ is a natural number and is less than $250$, $\frac{7n-3}{8n-5}$ can be simplified which means there is a common factor that can be divided out.

Answer 1

We have $gcd(7n-3,8n-5)>1$ if and only if $n=2+11k$, in which case it is $11$. So this happens for $n=2,13,24,35,\ldots,244$ in the interval $[1,250]$. So the fraction can be simplified $23$ times in this range.

Answer 2

Hint: $ 11 = 8(7n-3)-7(8n-5)$.

Answer 3

Say we can reduce $\frac{7n-3}{8n-5}$ with $d$. Then $$d\mid 7n-3\;\;\;{\rm and}\;\;\;d\mid 8n-5$$

so $$d\mid 8(7n-3) = 56-24\;\;\;{\rm and}\;\;\;d\mid 7(8n-5) = 56n-35$$

so $$d\mid (56n-24)-(56n-35) =11$$

so if we can reduce the fraction we can do this only with $11$

Now when is $11\mid 7n-3$ true? In that case we have $$11\mid 22n-11-3(7n-3) = n-2$$ so $$n-2=11k \implies n=11k+2$$

Finally $11k+2\leq 249$ so $11k\leq 247$ so $k\leq 22$. So we can do this for $23$ numbers.

Answer 4

Let's try to simplify $$\frac {7n-3}{8n-5}=\frac {8n-5-n+2}{8n-5}=1-\frac {n-2}{8n-5}$$

Now we need a common factor between $n-2$ and $8n-5$, and since $8n-5$ is odd, this is the same as a common factor between $8(n-2)=8n-16$ and $8n-5$. Any common factor of two numbers is a factor of their difference, and hence a factor of $11$.

So for a factor to exist we must have $11|7n-3$ and this happens when $n\equiv 2 \bmod 11$

To see this solve $7n\equiv 3 \bmod 11$. If you need, note that $7\times 8\equiv 1 \bmod 11$ so $$8\times 7n\equiv n \equiv 8\times 3 \equiv 2\bmod 11$$but observation/trial and error gets you there quickly.

Some of the other methods proposed are systematic versions of this observation, sometimes in different language, but generalised to a wider set of problems.