2
$\begingroup$

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?

  • 2
    Yes, perfect. Go on.2012-11-17

3 Answers 3

5

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 concude 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$.

  • 0
    The example I gave shows that such $a,b$ need not exist, hence my questions about points that seem to be implicit in your answer.2012-11-19
0

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$.

  • 0
    But it's not overkill; rather it's trivial: $\rm\,(3n\!-\!5,4n\!-\!7) = (3n\!-\!5,n\!-\!2) = (1,n\!-\!2) = 1.\:$ I'd bet that on a random sample of "small" pairs of coprime integers, on average, one can compute the gcd much faster *algorithmically* using Euclid's algorithm vs. *ad-hoc* attempts at guessing the Bezout identity for the gcd.2012-11-18
0

Hint $\ $ Compute the gcds as in the Euclidean algorithm, using $\rm\: (a,b) = (a, b\ mod\ a),\:$ e.g.

$\rm (3i\!-\!5,10i\!-\!17) = (3i\!-\!5,3(3i\!-\!5)\!+\!i\!-\!2) = (3i\!-\!5,i\!-\!2) = (3(i\!-\!2)\!+\!1,i\!-\!2) = (1,i\!-\!2) = 1$

Thus $\rm\ \dfrac{3i-5}{10i-17}\:$ is in lowest terms (reduced), since the top and bottom are coprime.

Alternatively $ $ Computing mod $\rm\: d = (\color{#C00}{3i\!-\!5},\color{#0A0}{10i\!-\!17})\:$ yields a purely equational computation

$\rm mod\ d\!:\ \color{#C00}{5\equiv 3i}\:\Rightarrow\:15\equiv 9i\:\Rightarrow\: 15\!+\!i\equiv \color{#0A0}{10i\equiv 17}\:\Rightarrow\:i\equiv 2\:\Rightarrow\: \color{#C00}{5 \equiv 3i}\equiv 6\:\Rightarrow\:0\equiv 1$

Hence $\rm\:mod\ d\!:\ 0\equiv 1\:$ i.e. $\rm\:d\mid 1\:$ so the gcd $\rm\:d\:$ is $1.$

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.

  • 0
    @Downvoter If something is not clear then please feel welcome to ask questions and I will be happy to elaborate.2012-11-17