A fraction is said to be irreducible when its numerator and denominator do not have common factors, that is, when the greatest common divisor between the two numbers is 1. For example, the fraction $\frac{3}{7}$ is irreducible, but the fraction $\frac{10}{14}$ is not, since 2 is a common factor of 10 and 14. For which values of $n$ is the fraction $\frac{5 n+6}{6 n+5}$ irreducible? Let's study this problem in parts:

a) Let $d=\text{gcd}(5 n+6,6 n+5)$ be the greatest common divisor of $5 n+6$ and $6 n+5$. Verify that $d$ is a divisor of $n-1$.

b) Knowing that $d$ is a divisor of $n-1$, conclude that $d$ is also a divisor of 11.

c) Verify that if 11 divides $5 n+6$, then 11 divides $6 n+5$.

d) For how many positive integers $n$, less than 50, is the fraction $\frac{5 n+6}{6 n+5}$ irreducible?
Solution

a) Since $6 n+5$ and $5 n+6$ are multiples of $d$, there exist integers $x$ and $y$ such that $6 n+5=d x$ and $5 n+6=d y$. Therefore,

$$
\begin{aligned}
n-1 & =(6 n+5)-(5 n+6) \\
& =d x-d y \\
& =d(x-y)
\end{aligned}
$$

implying that $d$ is a divisor of $n-1$.

b) Using the fact that $6 n+5$ and $n-1$ are multiples of $d$, we can write

$$
\begin{aligned}
11 & =(6 n+5)-6(n-1) \\
& =d x-6 d(x-y) \\
& =d(x-6(x-y)) \\
& =d(-5 x+6 y)
\end{aligned}
$$

which allows us to conclude that $d$ is a divisor of 11.

c) If 11 is a divisor of $5 n+6$, then we can write $5 n+6=11 k$. Additionally, we can write 11 as

$$
\begin{aligned}
11 & =(6 n+5)-6(n-1) \\
& =(6 n+5)-6((6 n+5)-(5 n+6)) \\
& =-5(6 n+5)+6(5 n+6) \\
& =-5(6 n+5)+66 k
\end{aligned}
$$

Rearranging the terms of the equation, we get

$$
\begin{aligned}
5(6 n+5) & =66 k-11 \\
& =11(6 k-1)
\end{aligned}
$$

Since 11 is a divisor of $5(6 n+5)$, which has no common factor with 5, we can conclude that 11 divides $6 n+5$.

d) It is just a matter of organizing the information obtained in the previous items. We already know that the $gcd$ of the given numbers divides 11, implying only the possibilities 1 or 11. We need to eliminate the cases where 11 divides both numbers. From the previous item, this happens when $5 n+6$ leaves a remainder of 0 when divided by 11. Testing the possibilities, we see that this occurs when $n$ leaves a remainder of 1 when divided by 11. From 1 to 50, there are 5 numbers that leave a remainder of 1 when divided by 11, namely, 1, 12, 23, 34, and 45. Therefore, the fraction $\frac{5 n+6}{6 n+5}$ is irreducible for $50-5=45$ positive integers $n$ less than 50.