Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
2  
Yes, perfect. Go on. –  Berci Nov 17 '12 at 13:32
add comment

3 Answers 3

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

share|improve this answer
    
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?\ \ $ –  Bill Dubuque Nov 17 '12 at 20:15
    
@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). –  Did Nov 18 '12 at 23:13
    
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. –  Bill Dubuque Nov 19 '12 at 0:12
add comment

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

share|improve this answer
    
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. –  Bill Dubuque Nov 17 '12 at 16:13
    
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. –  Adeel Nov 17 '12 at 19:43
    
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? –  Bill Dubuque Nov 17 '12 at 19:58
    
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. –  Adeel Nov 17 '12 at 23:36
    
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). –  Bill Dubuque Nov 17 '12 at 23:48
show 2 more comments

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.

share|improve this answer
    
@Downvoter If something is not clear then please feel welcome to ask questions and I will be happy to elaborate. –  Bill Dubuque Nov 17 '12 at 15:50
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.