For which natural numbers $n$ is the fraction $\frac{n^{3}+n}{2 n+1}$ irreducible?
Here we have a small problem, we cannot directly apply the Euclidean algorithm (try it, you will see the problem). So we must find pairs of numbers that are increasingly simpler and have the same gcd as $n^{3}+n$ and $2 n+1$. Let $D=\operatorname{pgcd}\left(n^{3}+n, 2 n+1\right)$.

First, 2 is clearly coprime with $2 n+1$. Therefore,

$$
D=\operatorname{pgcd}\left(2\left(n^{3}+n\right), 2 n+1\right)
$$

Now,

$$
2 n^{3}+2 n=n^{2} \cdot(2 n+1) \quad+\quad\left(-n^{2}+2 n\right)
$$

so $D=\operatorname{pgcd}\left(2 n+1, n^{2}-2 n\right)=\operatorname{pgcd}\left(2 n+1,2 n^{2}-4 n\right)$. Now we can apply the Euclidean algorithm as in the previous exercise.

$$
\begin{aligned}
2 n^{2}-4 n & =n \cdot(2 n+1) \quad-\quad 5 n \\
5 n & =2 \cdot(2 n+1) \quad+\quad n-2 \\
2 n+1 & =2 \cdot(n-2) \quad+\quad 5
\end{aligned}
$$

Finally, $D=\operatorname{pgcd}(n-2,5)$. Since 5 is prime, this gcd is 5 if $5 \mid n-2$, and 1 otherwise.

Therefore, the fraction is irreducible if and only if

$$
n \not \equiv 2 \quad(\bmod 5)
$$