Prove Irreducibility of (21n+4)/(14n+3) for n ∈ N

[symplectic_manifold]

Hey, Guys...the following problem from IMO 1959, the very first: Prove that the fraction (21n+4)/(14n+3) is irreducible for every natural number n.
...just can't get what is meant by the given solution: 3(14n+3)-2(21n+4)=1...I mean, what is their "sample" method?!...can't see through...tried to get the same...no chance.
Please, help!

 

[Muzza]

Showing that (21n + 4)/(14n + 3) is irreducible is equivalent to showing that 21n + 4 and 14n + 3 share no common factors, i.e. that gcd(21n + 4, 14n + 3) = 1 (where gcd = greatest common divisor). That, in turn, is equivalent to showing that there exists integers x, y such that x(21n + 4) + y(14n + 3) = 1 (which is what whoever wrote the solution did).

One of the implications of the last theorem: if K divides both 21n + 4 and 14n + 3, then K divides x(21n + 4) + y(14n + 3), which implies that K divides 1. But then K = +/- 1, so gcd(21n + 4, 14n + 3) = 1.

The proof of the other implication can be found http://www.math.swt.edu/~haz/prob_sets/notes/node7.html#SECTION00230000000000000000 .

 

[tacman]

To prove that a fraction is irreducible means to show that the numerator and denominator have no common factors other than 1. In other words, they cannot be reduced further.

To prove this for the fraction (21n+4)/(14n+3), we can use the Euclidean algorithm. This algorithm states that for any two positive integers a and b, there exist unique integers q and r such that a = bq + r, where r is the remainder and 0 ≤ r < b.

In this case, we can rewrite the fraction as (21n+4)/(14n+3) = (21n+4) ÷ (14n+3). Using the Euclidean algorithm, we can find the greatest common divisor (GCD) of the numerator and denominator by repeatedly dividing the larger number by the smaller number until we reach a remainder of 0.

So, let's start with the first division: (21n+4) ÷ (14n+3). Using long division, we get:

(21n+4) ÷ (14n+3) = 1 + (7n+1) ÷ (14n+3)

Next, we divide (14n+3) by (7n+1):

(14n+3) ÷ (7n+1) = 2 + (1) ÷ (7n+1)

Since we have a remainder of 1, we cannot divide any further. Therefore, the GCD of (21n+4) and (14n+3) is 1, which means that they have no common factors other than 1.

Now, let's go back to the original fraction:

(21n+4)/(14n+3) = (21n+4) ÷ (14n+3)

= (1 + (7n+1) ÷ (14n+3)) ÷ (14n+3)

= 1 ÷ (14n+3) + (7n+1) ÷ (14n+3) ÷ (14n+3)

= 0 + (7n+1) ÷ (14n+3) ÷ (14n+3)

= (7n+1) ÷ (14n+3)²

Since the GCD of (21n+4) and (14n+3) is 1