2

Problem 1 : Prove that the fraction $\frac{21n+4}{14n+3}$ is irreducible for every natural number $n$.

I understand that it can be solved using the Euclidean Algorithm, but how would the solution look like? I know the Euclidean Algorithm, but don't understand how it is applied here.

jimpix
  • 211

4 Answers4

6

The euclidean algorithm works just as usual. We have $$ \gcd(21n+4,14n+3)\\ =\gcd(21n+4-(14n+3),14n+3)\\ =\gcd(7n+1,14n+3)\\ =\gcd(7n+1,14n+3-2(7n+1))\\ =\gcd(7n+1,1)=1 $$

Arthur
  • 199,419
  • In step 2, why do you subtract $14n + 3$ instead of dividing? – jimpix Aug 07 '16 at 15:56
  • Because that's what the euclidean algorithm is: it's subtracting the smallest from the largest repeatedly until you get something simple. There is no division in the euclidean algorithm. – Arthur Aug 07 '16 at 15:59
  • Hmm.. is there something wrong with link? – jimpix Aug 07 '16 at 16:00
  • No. They do the division to tell how many times you can subtract one from the other. It's not really part of the formal algorithm, but it lets you do fewer steps. It's how i could tell that I needed to subtract $2$ times $7n+1$. – Arthur Aug 07 '16 at 16:03
  • so I've learn the incomplete algorithm it seems. – jimpix Aug 07 '16 at 16:04
  • No, you've learned the algorithm the way everyone does it in practice, and there is nothing wrong with that. But perhaps they should've done it once the long way first, to show why the division is a good thing to do in practice. – Arthur Aug 07 '16 at 16:08
  • But I don't understand why you subtract. Perhaps I need to recheck the algorithm. – jimpix Aug 07 '16 at 16:09
  • The subtraction is the core part of the algorithm. It's based on the theorem that states $\gcd(a,b)=\gcd(a-b,b)$. – Arthur Aug 07 '16 at 16:10
  • I see. I don't understand when people write it like $gcd(x,y) = gcd(a,b)$ since I'm used to the different format. – jimpix Aug 07 '16 at 16:42
  • You can also solve this by observing that if $ p|21n+4$ and $p|14n+3$ then $p|3(14n+3)-2(21n+4)=1.$ In other words, try to derive an expression $p|X$ where $n$ does not appear in $X$. – DanielWainfleet Aug 07 '16 at 16:44
0

HINT:

If integer $d$ divides $21n+4,14n+3$

$d$ must divide $3(14n+3)-2(21n+4)=1$

The basic idea was to eliminate $n$ and find a constant that must be divisible by $d$

lab bhattacharjee
  • 274,582
0

By the Euclidean algorithm,$$21n+4 = 1(14n + 3) + (7n + 1)$$ Now the $GCD$ of $(21n+4)$ & $(14n + 3)$ is the same as that of $(14n + 3)$ & $(7n + 1)$.
So applying the algorithm to $(14n + 3)$ & $(7n + 1)$, $$(14n + 3) = 2(7n+1) + 1$$ By the same logic, the $GCD$ of $(14n + 3)$ & $(7n + 1)$ is equal to that of $(7n + 1)$ & $1$. Hence we finally have the $GCD$ of $(21n+4)$ & $(14n + 3)$ $=1$.
Since the $GCD$ of the numerator and denominator is 1, therefore, the fraction is irreducible.

Anonymous_original
  • 100
0

$${21n+4\over 14n+3}={14n +3 +7n+1\over 14n+3}=1 +{7n+1\over 14n+3}= 1 +{14n+2\over 2(14n+3)}$$

$$\gcd(14n+2,14n+3) = 1$$ thus irreducible.