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
    How do you know that such $\rm\:a,b\:$ exist, and how do you propose to find them? Does your method mistakenly prove that $\rm\:n(n\!+\!1)/2\:$ is in lowest terms for all $\rm\,n?\ \ $2012-11-17
  • 0
    @Dubuque This is an odd comment. *How do you know that such a,b exist*... In the second paragraph I state that IF a and b exist THEN the numbers are co-prime. In the third paragraph I suggest that in the specific cases the OP is interested in, the identity uv'=u'v+/-1 might help to find such a and b. *Does your method mistakenly prove that...* Sorry but I stopped reading your comment at this *that* (two words too late, but I react slowly).2012-11-18
  • 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
    In general, how do you propose to *discover* the Bezout identity, other than using the extended Euclidean algorithm? This is more work than needed - see my answer.2012-11-17
  • 0
    Dear Bill, Bézout’s lemma says that the gcd of $m$ and $n$ is the smallest positive integer of the form $am+bn$ for $a,b \in \mathbb{Z}$; hence if one has found $a,b$ such that $am+bn=1$, it follows directly that $m,n$ are coprime. In these cases it is easy to find such $a,b$. Hope that helps.2012-11-17
  • 0
    Yes, of course, but how do you propose to actually *compute* the *specific* Bezout identity required, other than by applying the extended Euclidean algorithm? (or equivalent methods) For example, how does your answer handle the example worked out in my answer? You don't propose to pull the Bezout identity out of a hat, right?2012-11-17
  • 0
    Dear Bill, I am not sure if I understand what you mean but in your example there is an obvious linear combination $10(3i-5) - 3(10i-17) = 1$ and from my argument above we are done.2012-11-17
  • 0
    Of course such ad-hoc techniques don't work generally. For small numbers the Bezout identity might seem "obvious" but this will soon fail for for larger numbers. To handle the general case requires the extended Euclidean algorithm (or an equivalent *algorithm*). My point was that generally one doesn't need the *extended* part of the algorithm (the Bezout identity), only the gcd computation that shows the gcd $= 1$ (though the Bezout identity does serve as a succint way to check the result -- somewhat analogous to Pratt certificates as witnesses to primality).2012-11-17
  • 0
    Yes, you are right but for the original question or even your example it is surely overkill to use Euclid's algorithm, in my opinion, since there is a simple way to arrive at the answer without writing anything down.2012-11-17
  • 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