Let $k$ be a common factor, greater than zero, of both the numerator and the denominator. Let \[ 21n+4=Ak \] and \[ 13n+3=Bk \] Then \[ k(3B-2A)=3Bk-2Ak=(42n+9)-(42n+8)=1 \] The first expression is divisible by $k$, so $k$ must be a divisor of 1. Thus the greatest common factor of the numerator and the denominator is one, and the fraction is not reducible.

Using Euclid's algorithm for determining the greatest common divisor of the two numbers we obtain \[ 21n+4=1 \cdot (14n+3)+(7n+1) \] \[ 14n+3=2 \cdot (7n+1)+1 \] \[ 7n+1=1 \cdot (2n+1)+0 \] The greatest common divisor of the numerator and denominator is one. Therefore the given fraction is irreducible.

Easiest IMO prob. ever. We have 2(21n+4)-3(14n+3)=-1, o we are done... Bomb

bomb wrote: Easiest IMO prob. ever. Well it was the first imo problem .... ever

It was I never realised.. Bomb

Of course it seems easy to you since everyone knows how to use Euclid's algorithm, but 49 years ago it was a new method, probably.

Probably, it was new 2300 years ago

I mean that an ordinary kid didn't learn this method at school. I'm not ignorant - I know that Euclid lived in Ancient Greece.

apiarist1 wrote: I mean that an ordinary kid didn't learn this method at school. I'm not ignorant - I know that Euclid lived in Ancient Greece. 1) Ordinary kids don't go to IMO's. 2) 49 years ago people DID learn the Euclidean algorithm at school; it's rather nowadays that they don't. You will be amazed at what people learnt at school 49 years ago; the textbooks contained things that are meanwhile forgotten enough that you can pose them as IMO problems... dg

darij grinberg wrote: 49 years ago people DID learn the Euclidean algorithm at school; it's rather nowadays that they don't. You will be amazed at what people learnt at school 49 years ago; the textbooks contained things that are meanwhile forgotten enough that you can pose them as IMO problems... Could you provide some examples for such IMO problems?

Hi, this is my first ever post here so please forgive me for being a little stupid (perhaps), but all I did was: $ \dfrac{21n + 4}{14n + 3} = \dfrac{14n + 3 + 7n + 1}{14n + 3} = 1 + \dfrac{7n + 1}{14n + 3} = 1 + \dfrac{7n + 1}{2(7n + 1) + 1}$ and so we see that the part by which the fraction exceeds 1 can never be reduced because the numerator does not divide the denominator. EDIT: Sorry, what I mean is that nothing divides both the numerator and the denominator because of the extra "1" hanging around.

I'm not really sure if this is a solution. I'm not too smart so I might be wrong. What I did was assume that the fraction is reducible. Thus (21n+4)/(14n+3)=k for some positive integer k. Thus 21n+4=14nk+3k 7n(3-2k)=3k-4 7n =(3k-4)/(3-2k) Since n is a natural number (3k-4)/(3-2k) must be a positive integer for some k. Unfortunately, (3k-4)/(3-2k)>0 only in the interval (4/3,3/2). We see that for (3k-4)/(3-2k) to be an integer k must be between 3/2 and 4/3. But then, k isn't an integer and we reach a contradiction. Thus (21n+4)/(14n+3) is irreducible. I apologize for the lack of LaTeX in advance. I still have to learn.

darij grinberg wrote: apiarist1 wrote: I mean that an ordinary kid didn't learn this method at school. I'm not ignorant - I know that Euclid lived in Ancient Greece. 1) Ordinary kids don't go to IMO's. 2) 49 years ago people DID learn the Euclidean algorithm at school; it's rather nowadays that they don't. You will be amazed at what people learnt at school 49 years ago; the textbooks contained things that are meanwhile forgotten enough that you can pose them as IMO problems... dg People do realize this was in the soviet Union, america didn't enter till 1970's, with Paul Zeitz being first IMO member for the US (author of "Arts and Crafts of Problem Solving").

[moderator says: do not quote the entire post before yours] ... and your point is?__________________________

$(21n+4,14n+3)$ $=(7n+1,14n+3)$ $=(7n+1,1)$ $=1$ hence the fraction is irreducible.

I quoted for clarity, as someone asked, why this problem was so simple and they said that 50 years ago they knew this, but they were thinking about American education. I am just making a point that this was in USSR and not US.

I just kept on subtracting like: $ 21n+4-(14n+3)=7n+1 $ $ 14n+3-(7n+1)=7n+2 $ $ 7n+2-(7n+1)=1 $ and I am done, because the GCF of n and 1 is always 1.

Could you tell me the way!

trivial by euclidean algorithm

Let's use the Euclidean algorithm. 21n+4 = 1 x (14n +3 ) + 7n+1. 14n+3 = 2 x (7n +1) + 1. Therefore, gcd (21n+4, 14n+3)=gcd (14n+3, 7n+1)=gcd (7n+1,1)=1. -> 21n+4 and 14n+3 are coprime. ∴ 21n+4/14n+3 is in its simplest form.

Hardest problem I've ever solved Lemma 1: A fraction $\frac{x}{y}$ is irreducible for every natural number $n$ if only if $$\gcd(x,y)=1$$for all $n$. Proof: This is true by definition. Lemma 2: For any positive integer $x$, we have $$\gcd(x,1)=1.$$ Proof: Assume otherwise, i.e. that $$\gcd(x,1)=a>1.$$But then we have $a$ divides $1$, a contradiction to $a>1$. Now, we can finish the problem using Euclidean Algorithm. 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).$$We aim to show that this always equals one (then Lemma 1 finishes the problem), but that is true by Lemma 2 when we apply $x=7n+1$.

DPopov wrote: Prove that the fraction $ \dfrac{21n + 4}{14n + 3}$ is irreducible for every natural number $ n$. Euclidean algorithm kills the problem within seconds. One of the easiest imo problems ever!

EaZ_Shadow wrote: DPopov wrote: Prove that the fraction $ \dfrac{21n + 4}{14n + 3}$ is irreducible for every natural number $ n$. Euclidean algorithm kills the problem within seconds. One of the easiest imo problems ever! Are you sure this problem is so easy? It's the hardest one I've ever solved!

megahertz13 wrote: EaZ_Shadow wrote: DPopov wrote: Prove that the fraction $ \dfrac{21n + 4}{14n + 3}$ is irreducible for every natural number $ n$. Euclidean algorithm kills the problem within seconds. One of the easiest imo problems ever! Are you sure this problem is so easy? It's the hardest one I've ever solved! Yeah how could you not see the obvious Euclidean algorithm since gcd of 2 numbers is 1 implies that the 2 numbers a and b written as a fraction is irreducible

Problem just more easy than 2019 imo problem 1

EaZ_Shadow wrote: Problem just more easy than 2019 imo problem 1 yeah ofc it is, maybe because its 60 years earlier

EaZ_Shadow wrote: Problem just more easy than 2019 imo problem 1 im 75% sure ur sol is wrong on the wiki please correct because the final step claims that all linear functions work which is incorrect

InftyByond wrote: EaZ_Shadow wrote: Problem just more easy than 2019 imo problem 1 im 75% sure ur sol is wrong on the wiki please correct because the final step claims that all linear functions work which is incorrect I’m pretty sure it is right because that the common difference won’t stay the same if the leading degree of the polynomial is at least 2

Assume otherwise. Then there is some prime $p$ such that $p|21n+4$ and $p|14n+3$. Clearly $14n+3$ is never a multiple of $2$ or a multiple of $7$, and clearly $21n+4$ is never a multiple of $3$, so $p$ does not equal $2$, $3$, or $7$. Now observe that $21n+4 \equiv 0 \pmod{p}$ implies that $n\equiv -\frac{4}{21} \pmod{p}$, and $14n+3 \equiv 0 \pmod{p}$ implies that $n\equiv -\frac{3}{14}\pmod{p}$, so we have $-\frac{4}{21}=-\frac{3}{14}\pmod{p}$, cross-multiplying we get $56\equiv 63 \pmod{p}$, dividing by $7$ gives $8\equiv 9 \pmod{p}$, so $p|(9-8)=1$, contradiction. Thus no prime exists and the fraction is irreducible.

EaZ_Shadow wrote: InftyByond wrote: EaZ_Shadow wrote: Problem just more easy than 2019 imo problem 1 im 75% sure ur sol is wrong on the wiki please correct because the final step claims that all linear functions work which is incorrect I’m pretty sure it is right because that the common difference won’t stay the same if the leading degree of the polynomial is at least 2 The function is not always a polynomial.

can you show it then?

EaZ_Shadow wrote: can you show it then? buh they're functions. not polys which means that maybe something like $5x^\frac{1}{2}$ works. or something pathological like weirstrass. anyways please find a different proof (maybe has to do with Cauchy? idk)

If $\dfrac{21n + 4}{14n + 3}$ is irreducible, we know that $\gcd(21n + 4, 14n + 3) = 1$. By the Euclidean Algorithm, \[ \gcd(21n + 4, 14n + 3) = \gcd(7n + 1, 14n + 3) = \gcd(7n + 1, 1) = 1. \] Since $\gcd(21n, 14n + 3) = 1$, we know that $\dfrac{21n + 4}{14n + 3}$ is irreducible for all integers $n$. $\blacksquare$