INTRODUCING 5 - days-a-week problem solving session for Math Olympiad and ISI Entrance. Learn More 

December 7, 2015

West Bengal RMO 2015 Problem 3 Solution - Triples of Positive Integers


The second stage examination of INMO, the Regional Mathematical Olympiad (RMO) is a three hour examination with six problems. The problems under each topic involve high level of difficulty and sophistication. The book, Challenge and Thrill of Pre-College Mathematics is very useful for preparation of RMO. West Bengal RMO 2015 Problem 3 Solution has been written for RMO preparation series.


Problem:


Show that there are infinitely many triples (x,y,z) of positive integers, such that x^3+y^4=z^{31} .


Discussion


Suppose we have found one such triplet (x, y, z). Then x^3 + y^4 = z^{31}  . Multiply a^{372}  to both sides where a is an arbitrary integer.

Clearly we have a^{372}x^3 + a^{372}y^4 = a^{372}z^{31}

\Rightarrow (a^{124}x)^3 + (a^{93}y)^4 = (a^{12}z)^{31}

Hence if (x, y, z) is a triple then (a^{124}x, a^{93}y, a^{12}z )  is another such triple. Since a can be any arbitrary integer, hence we have found infinitely many such triplets provided we have found at least one

To find one such triple, we use the following intuition: set x, y, z as some powers of 2 such that x^3 = y^4 = 2^{r}  . Then r must be of the form 12k. Finally, their sum must be x^3 + y^4 = 2^{r} + 2^{r} = 2^{r+1}  . This r+1 must be divisible by 31.

Let r = 12s  and r+1 = 31m  we get 12s +1 = 31m  . Since 12 and 31 are coprime there is integer solution to this linear diophantine equation (by Bezoat's theorem). We can solve this linear diophantine equation by euclidean algorithm.

31 = 12 \times 2 + 7
12 = 7\times 1 + 5
7 = 5\times 1 + 2
5 = 2 \times 2 + 1
\Rightarrow 1 = 5 - 2 \times 2 = 5 - 2 \times (7 - 5 \times 1)
\Rightarrow 1 = 3 \times 5 - 2 \times 7 = 3 \times (12 - 7 \times 1) - 2 \times 7
\Rightarrow 1 = 3 \times 12 - 5 \times 7 = 3 \times 12 - 5 \times (31 - 12 \times 2)
\Rightarrow 1 = 13 \times 12 - 5 \times 31
\Rightarrow 1 = 13 \times 12 - 5 \times 31 + 12 \times 31 - 12 \times 31
\Rightarrow 1 = (13 -31)\times 12 +(12- 5 )\times 31
\Rightarrow 1 = -18 \times 12 + 7\times 31
\Rightarrow 1 + 18 \times 12 = 7\times 31
Hence we use this to form an equation:
2^{18 \times 12} + 2^{18 \times 12} = 2^{216} + 2^{216} = 2^{217}=2^{7\times 31}
(2^{72})^3 + (2^{54})^4 = (2^7)^{31}

Hence we have found one such triple : (2^{72}, 2^{54} ,2^7 ) (from which we have shown earlier that infinitely more can be generated)


Chatuspathi:

  • What is this topic: Number Theory
  • What are some of the associated concept: Linear Diophantine Equation, Bézout's Theorem, Euclidean Algorithm, Sum of powers of two
  • Where can learn these topics: Cheenta I.S.I. & C.M.I. course, Cheenta Math Olympiad Program, discuss these topics in the ‘Number Theory’ module.
  • Book Suggestions: Elementary Number Theory by David Burton

7 comments on “West Bengal RMO 2015 Problem 3 Solution - Triples of Positive Integers”

  1. I found, in some question papers, it is mentioned only 'integers' not 'positive integers'. I know, that it should be 'positive integers', otherwise it will become a trivial problem by taking x=0.

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.

Cheenta. Passion for Mathematics

Advanced Mathematical Science. Taught by olympians, researchers and true masters of the subject.
JOIN TRIAL
support@cheenta.com
enter