Proving that $\frac{n+1}{2n+3}$ and $\frac{3n-5}{4n-7}$ are irreducible for all $n$

Question

I am trying to solve the following problem:

Prove that the following fractions are irreducible for any n (n is a natural number and it cannot be null).

1. $\frac{n}{n+1}$
2. $\frac{n+1}{2n+3}$
3. $\frac{3n-5}{4n-7}$

I don't know if my logic is right!

Now for the first one, i used the property which states that $n$ and $n+1$ are always coprime. For the second one i relied on the following property,

1. if $n|a$ and $n|b$ then $n|(a*k - b*p)$.

So lets suppose $\frac{n+1}{2n+3}$ is reducible, then there is a whole number $d$ which divides both the numerator and denominator. By property 1, $d|[2n+3 - 2(n+1)]$ this means $d|1$ so $d=1\ldots$.

So the fraction is not reducible since every number is divisible by 1.

Is my logic right? how would someone go about solving this problem?

Answer 1

Yes: since $(2n+3)-2\cdot(n+1)=1$, every common divisor of $2n+3$ and $n+1$ is also a divisor of $1$. Thus, $2n+3$ and $n+1$ are co-prime.

Ditto for $3n-5$ and $4n-7$, to conclude it suffices to find some integers $\color{red}{a}$ and $\color{green}{b}$ such that $\color{red}{a}\cdot(3n-5)+\color{green}{b}\cdot(4n-7)=\pm1$.

Both cases are examples of the more general result that $un+v$ and $u'n+v'$ are co-prime as soon as $uv'=u'v\pm1$.

Answer 2

You can use the lemma of Bézout and a linear combination of the numerator and denominator which is equal to one. For example, for (b) note $-2(n+1) + (2n+3) = 1$.

Answer 3

Hint $ $ Compute the gcd of the fraction top & bottom as in the Euclidean algorithm, using $\, (a,b) = (a,\, b\bmod a),\,$ in order to eliminate $\,n\,$ by decreasing its coefficients, i.e.

$$\begin{align} (3n\!-\!5,\,10n\!-\!17) &= (3n\!-\!5,\,\color{#0a0}{n\!-\!2})\ \ {\rm by}\ \ \color{#0a0}{n\!-\!2} = 10n\!-\!17-3(3n\!-\!5)\\[.2em] &= (\color{#c00}1,\,n\!-\!2)\qquad\ \ {\rm by}\ \ \color{#c00}1 = 3n\!-\!5-3(n\!-\!2)\\ &=\, 1 \end{align}\qquad$$

Therefore $ \, \dfrac{3n\!-\!5}{10n\!-\!17}\,$ is is irreducible, since the top and bottom are coprime.

Alternatively $ $ working mod $ \, d = (\color{#C00}{3n\!-\!5},\color{#0A0}{10n\!-\!17})\,$ means we can use well-known equational arithmetic to eliminate $\,n\,$ by cross multiplying the equations to kill the coef of $\,n,\,$ i.e.

$$\bmod d\!:\,\ 3(\color{#0a0}{10n\equiv 17}) - 10(\color{#c00}{3n\equiv 5})\,\Rightarrow\, 0\equiv 1\,\Rightarrow\, d\mid 1\!-\!0\,\Rightarrow\, d = 1\qquad$$

Remark $\ $ Other answers recommend using the Bezout identity for the gcd - presumably computed by the extended Euclidean algorithm. But that extra effort is unneeded here, since we don't actually require the Bezout coefficients -- we only need to prove that the gcd $= 1$. This is a simpler task, which can be done as in the ordinary Euclidean algorithm, i.e. one does not need to keep track of the linear representations (Bezout coefficients) as in the extended Euclidean algorithm.

More generally see algorithms for computing Hermite / Smith normal forms.