Waste less time on Facebook — follow Brilliant.
×

RMO 2015

I have taken inspiration from my friend Swapnil's note and have decided to post this note.I have decided that I will post one or two problems every now and then that are related to the topics of RMO.They can either be proof problems, like the proof of an integral theorem e.t.c or ones like finding values.The questions will be either from preparation books or from Mathematical olympiads.I will keep on adding them one-by-one in the space below.The main rule is that there should be just one solution to one problem,unless,of course,there are more than one way of doing it.If the solution you have is the same as the one which has already been posted,kindly refrain from posting it,but if you have another method of solving the same problem,please do post it!I will post the solution only if one hasn't been posted in \(3\) days.So,\[\text{Happy problem solving!}\]\[\] 1.If p is a prime number,then prove that,\((a+b)^p\equiv(a^p+b^p)\pmod{p}\) Generalize it too!(Awesome part!)\[\] 2.For \(m>2\),prove that,\(\phi(m)\)is even where\(\phi\) is the Euler's Totient Function\[\] 3.Prove that there are infinitely many squares in the sequence \(1,3,6,10,15,21,28,......\).\[\] 4.Find all the pairs of positive integers (m,n) such that \(2^m+3^n\) is a perfect square.\(\text{INMO}\)\[\] 5.Prove that \(2^p+3^p\) is not a perfect square for a prime \(p\).\[\] 6.If \(a\equiv b\pmod{m^n}\),then prove that \(a^m\equiv b^m\pmod{m^{n+1}}\)(Given by Svatejas Shivakumar). \[\] 7.Find a polynomial with integer co-efficients such that \(P(a)=b,P(b)=c,P(c)=a\) where \(a,b,c\) are distinct.(given by Anik Mandal).We need a solution for this.Surya Prakash has posted a solution.\[\] 8.Find the number of prime \(n\) satisfying the equation \(3n+1=k^2,k\in \mathbb{Z}^+\).(Given by Mehul Arora).\[\] 9.If \(x^3=x+1\) then find integers \(a,b,c\) such that \(x^7=ax^2+bx+c\).(Given by Dev Sharma).

Note by Adarsh Kumar
1 year, 10 months ago

No vote yet
1 vote

Comments

Sort by:

Top Newest

5) We consider case when \(p=2\). Clearly \(2^2+3^2 = 4+9 = 13\) which is not a perfect square.So now consider \(p>2\). Let if possible \(2^p+3^q=q^2\) for some integer \(q\).We note that \(2^p \equiv 0 \pmod{4}\) , \(3^p \equiv 3 \pmod{4}\) , thus \(2^p+3^p \equiv 3 \pmod{4}\) but \(q^2 \equiv 0,1 \pmod{4}\) which is a contradiction. Nihar Mahajan · 1 year, 10 months ago

Log in to reply

@Nihar Mahajan Thanx for your solution. Adarsh Kumar · 1 year, 10 months ago

Log in to reply

9)\(x^3=x+1\Rightarrow x^6=(x^2+2x+1)\Rightarrow x^7=x^3+2x^2+x=2x^2+2x+1\). Adarsh Kumar · 1 year, 10 months ago

Log in to reply

@Adarsh Kumar How u got this......explain Ayush Verma · 1 year, 6 months ago

Log in to reply

9) \(x^3=x+1 \Rightarrow x^7=x^4(x+1) = x^5+x^4 = x^2(x+1)+x(x+1) = x^3+x^2+x^2+x = 2x^2+2x+1 \\ \Rightarrow (a,b,c)=(2,2,1)\) Nihar Mahajan · 1 year, 10 months ago

Log in to reply

@Nihar Mahajan No need of all that.See my solution. Adarsh Kumar · 1 year, 10 months ago

Log in to reply

7) If \(P(x)\) is a polynomial with integer coefficients then for distinct integers \(a\), \(b\), we have \(a-b|P(a)-P(b)\).

So, it implies that \(a-b|P(a)-P(b) = b-c\). Similarly we get, \(b-c|c-a\) and \(c-a|a-b\). So finally what we get is \(a-b|b-c\), \(b-c|c-a\) and \(c-a | a-b\), this is possible iff \(a-b = b-c =c-a\). But this implies that \(a=b=c\). This is a contradiction as \(a\), \(b\) and \(c\) are distinct. Therefore no such polynomial exists. Surya Prakash · 1 year, 10 months ago

Log in to reply

@Surya Prakash Is the first statement of your solution a lemma? Nihar Mahajan · 1 year, 10 months ago

Log in to reply

@Nihar Mahajan Yes. It is a lemma. it is easy to prove Surya Prakash · 1 year, 10 months ago

Log in to reply

@Surya Prakash Can you give me hint to prove it? Is it necessary to define a degree to the polynomials? Nihar Mahajan · 1 year, 10 months ago

Log in to reply

@Nihar Mahajan Take \(P(x) = a_{n} x^n + a_{n-1} x^{n-1} + \ldots + a_{0}\) where \(a_{n} , a_{n-1} , \ldots a_{0}\) are integers. Now, subtract \(P(a)\) from \(P(b)\) and observe what happens. Surya Prakash · 1 year, 10 months ago

Log in to reply

@Nihar Mahajan No,it can be proved like this,\[Since\ a-b|b-c,a-b\leq b-c\\ Since\ b-c|c-a,b-c\leq c-a\\ Since\ c-a|a-b,c-a\leq a-b\].Combining these you get that the equality holds. Adarsh Kumar · 1 year, 10 months ago

Log in to reply

@Surya Prakash Thanx for the solution. Adarsh Kumar · 1 year, 10 months ago

Log in to reply

@Surya Prakash Thanks for the solution! Anik Mandal · 1 year, 10 months ago

Log in to reply

6) \(a^{m}-b^{m}=(a-b)(a^{m-1}+a^{m-2}b+\ldots+ab^{m-2}+b^{m-1})\).

Since \(a \equiv b \pmod {m^{n}},a \equiv b \pmod {m}\).

Hence, \(a^{m-i}b^{i} \equiv b^{m} \pmod {m}\) and \(a^{m-1}+a^{m-2}b+\ldots+ab^{m-2}+b^{m-1} \equiv mb^{m} \equiv 0 \pmod {m}\)

Hence, \(a^{m}-b^{m}\) is divisible by \(m^{n+1}\).

Note: This solution is not original.

Credit: An Excursion in Mathematics. Svatejas Shivakumar · 1 year, 9 months ago

Log in to reply

@Svatejas Shivakumar Really elegant one! Thanx for posting it! Adarsh Kumar · 1 year, 9 months ago

Log in to reply

@Adarsh Kumar Your welcome :) Svatejas Shivakumar · 1 year, 9 months ago

Log in to reply

For the \(3rd\) question,

The sequence is, \(S=1+3+6+10+15........+{t}_{n} \)

To get the \( {t}_{n} \) we can write it as,

\(S=0+1+3+6+10+15........+{t}_{n} \)

\(S=1+3+6+10+15+.....\)

Now, Subtracting both the sums,

\(0=-1-2-3-4-5-.......{t}_{n} \)

Therefore we can get,

\( {t}_{n}=\frac {n(n+1)}{2} \)

Now to prove that there are infinitely many squares, Assume that \({t}_{n} \) is a square. From here we see that if \( {t}_{n}\) is a square,

\( {t}_{4n(n+1)}=4\frac{n(n+1)}{2}.{(2n+1)}^{2} \) is also a square.

Hence if \({t}_{1}=1\) is a square then \( {t}_{8}=36\) is a square. And if \({t}_{8} \) is a square then \( {t}_{4*8(8+1)}={t}_{288}=144*289\) is a square.

Therefore,we get a sequence of infinite squares from here. Saarthak Marathe · 1 year, 10 months ago

Log in to reply

@Saarthak Marathe Brilliant solution! Adarsh Kumar · 1 year, 10 months ago

Log in to reply

@Adarsh Kumar Thank you. See my solution for 2nd question Saarthak Marathe · 1 year, 10 months ago

Log in to reply

Comment deleted Sep 25, 2015

Log in to reply

@Adarsh Kumar \((m,n) = (4,2)\) Dev Sharma · 1 year, 10 months ago

Log in to reply

@Dev Sharma \(2^m + 3^n = a^2\)

so \(m = 2x\) and \(n = 2y\)

then \(2^{2x} = a^2 - 3^{2y}\) Dev Sharma · 1 year, 10 months ago

Log in to reply

Comment deleted Sep 25, 2015

Log in to reply

@Adarsh Kumar By working on modulo 3 and 4 , we can get that.... Harsh Shrivastava · 1 year, 10 months ago

Log in to reply

Comment deleted Sep 25, 2015

Log in to reply

@Adarsh Kumar I think that was a mere guess. Nihar Mahajan · 1 year, 10 months ago

Log in to reply

@Nihar Mahajan OR it was plug and check. Mehul Arora · 1 year, 10 months ago

Log in to reply

@Mehul Arora Or this margin is too small to contain his proof ......😛 Harsh Shrivastava · 1 year, 10 months ago

Log in to reply

@Harsh Shrivastava

We have a large margin to fit in! :P
Mehul Arora · 1 year, 10 months ago

Log in to reply

can anybody solve the rmo 2008 Maharashtra region problem 5 Devang Patil · 1 year, 9 months ago

Log in to reply

@Calvin Lin Sir, is it possible for you to close this note since we already have a part 2 for this note. Svatejas Shivakumar · 1 year, 9 months ago

Log in to reply

@Svatejas Shivakumar I don't see why this note should be locked. It is still valid for discussion, and adding of more comments / problems.

I might consider doing so if OP requests for it. Calvin Lin Staff · 1 year, 9 months ago

Log in to reply

First problem can be solved easily by using binomial therom Sameer Pimparkhede · 1 year, 10 months ago

Log in to reply

@Sameer Pimparkhede fermat's theorem, isn't it? Raghav Rathi · 1 year, 7 months ago

Log in to reply

@Sameer Pimparkhede no need Saarthak Marathe · 1 year, 10 months ago

Log in to reply

All questions are done! Saarthak Marathe · 1 year, 10 months ago

Log in to reply

@Saarthak Marathe Could you please provide the solution for the \(6^{th}\) one? Adarsh Kumar · 1 year, 9 months ago

Log in to reply

@Adarsh Kumar Since no one has posted the solution for the 6th one yet, should I post it (solution given in the book)? Svatejas Shivakumar · 1 year, 9 months ago

Log in to reply

@Svatejas Shivakumar Yes,please! Adarsh Kumar · 1 year, 9 months ago

Log in to reply

For the \(8th\) question,

\(3n=(k-1)(k+1) \)

By the Prime factorisation principle, There is a unique prime factorisation for every number.

From here we can say that,

\( 3=k-1\) and \(k+1=n\)

Therefore,\( n=5\) is the only prime of this form. Saarthak Marathe · 1 year, 10 months ago

Log in to reply

For the \(2nd\) question, Case \(1\): If there is atleast one odd prime factor of \(m\),

Then by Euler's Totient function corolary, We can say that if prime \(p\) divides a number \(m\) then \(p-1\) divides \(\phi(m) \) . As \(p\) is odd, \(p-1\) is even, Therefore,\( 2|\phi(m) \).

Case \(2\): If there is no odd prime factor of \(m\),

Then \(m\) can be written as \(m={2}^{k} \) We can easily say that \( \phi(m)={2}^{k}-{2}^{k-1} \) Hence,\(2|\phi(m) \) Saarthak Marathe · 1 year, 10 months ago

Log in to reply

Comment deleted Sep 26, 2015

Log in to reply

@Svatejas Shivakumar Please refrain from posting questions here.You can give them to me and i will post them at the top mentioning that it has been given by you.That way,it is more accessible. Adarsh Kumar · 1 year, 10 months ago

Log in to reply

Comment deleted Sep 26, 2015

Log in to reply

@Svatejas Shivakumar Yes,please.I have posted it giving credit to you.BTW from where did you get this? Adarsh Kumar · 1 year, 10 months ago

Log in to reply

@Adarsh Kumar An excursion in Mathematics. Svatejas Shivakumar · 1 year, 10 months ago

Log in to reply

@Svatejas Shivakumar BTW who is the author? @Svatejas Shivakumar Adarsh Kumar · 1 year, 10 months ago

Log in to reply

@Svatejas Shivakumar Ok!Thanx! Adarsh Kumar · 1 year, 10 months ago

Log in to reply

6) \(3n + 1 = a^2\)

\(3n = a^2 - 1\)

\(3n = (a + 1)(a - 1)\)

so \(a + 1 = 3 so a = 2\) OR

\(a - 1 = 3 so a = 4\)

then \(n = 1 or n = 5\)

so there are two n... Dev Sharma · 1 year, 10 months ago

Log in to reply

@Dev Sharma Is this solution correct? I don't think so... Harsh Shrivastava · 1 year, 10 months ago

Log in to reply

@Dev Sharma @Harsh Shrivastava @Nihar Mahajan @Dev Sharma @Mehul Arora I am sorry but question 6 is wrong.It is satisfied fro more than one value of \(n\).It is my fault as i should have checked the problem before posting it.Sorry for the inconvenience caused.I am going to delete it. Adarsh Kumar · 1 year, 10 months ago

Log in to reply

@Adarsh Kumar @Adarsh Kumar P has to be a prime I told you that. Mehul Arora · 1 year, 10 months ago

Log in to reply

@Mehul Arora Ni you didn't,go and see the conversation. Adarsh Kumar · 1 year, 10 months ago

Log in to reply

@Adarsh Kumar Oh , sorry if I didn't. Please repost the problem and mention that p is prime. Mehul Arora · 1 year, 10 months ago

Log in to reply

@Mehul Arora Ohk. Adarsh Kumar · 1 year, 10 months ago

Log in to reply

@Adarsh Kumar I have a question. How can I give you? (not on slack) Dev Sharma · 1 year, 10 months ago

Log in to reply

@Dev Sharma Give it here. Mehul Arora · 1 year, 10 months ago

Log in to reply

@Mehul Arora If \(x^3 = x + 1\) then determine integer a,b,c \(x^7 = ax^2 + bx + c\) Dev Sharma · 1 year, 10 months ago

Log in to reply

@Dev Sharma Thanx for the question!Kindly delete this comment as i have posted it giving credit to you. Adarsh Kumar · 1 year, 10 months ago

Log in to reply

Comment deleted Sep 26, 2015

Log in to reply

@Nihar Mahajan yes. Thanks. Dev Sharma · 1 year, 10 months ago

Log in to reply

@Dev Sharma You assumed that 'n' is prime, which is not given in the question..... Harsh Shrivastava · 1 year, 10 months ago

Log in to reply

@Harsh Shrivastava Yeah , correct. Nihar Mahajan · 1 year, 10 months ago

Log in to reply

@Adarsh Kumar In question 7, please mention that a,b and c are distinct. :) Mehul Arora · 1 year, 10 months ago

Log in to reply

@Mehul Arora done! Adarsh Kumar · 1 year, 10 months ago

Log in to reply

Comment deleted Sep 26, 2015

Log in to reply

@Adarsh Kumar \(n = 1\) Dev Sharma · 1 year, 10 months ago

Log in to reply

@Dev Sharma We would appreciate if you post a complete solution :) Nihar Mahajan · 1 year, 10 months ago

Log in to reply

@Adarsh Kumar @Mehul Arora Thanks for the problem :) Nihar Mahajan · 1 year, 10 months ago

Log in to reply

@Nihar Mahajan You're welcome @Nihar Mahajan Mehul Arora · 1 year, 10 months ago

Log in to reply

@Adarsh Kumar I believe that you can add a comment to the board, whenever you add a question. otherwise, it would be difficult to keep track.

You can add a comment like "Q3. is up" or "Next question!" so that people who are interested or have commented on this board get a notification, and they can check it out. Thanks. Mehul Arora · 1 year, 10 months ago

Log in to reply

@Mehul Arora Oh nice idea thanx! Adarsh Kumar · 1 year, 10 months ago

Log in to reply

@Adarsh Kumar Looks like giving a good idea gets me a downvote :3

Anyway, Glad to help :) Mehul Arora · 1 year, 10 months ago

Log in to reply

Comment deleted Sep 25, 2015

Log in to reply

@Adarsh Kumar Never blamed you for it ;) Mehul Arora · 1 year, 10 months ago

Log in to reply

Thanks! Harsh Shrivastava · 1 year, 10 months ago

Log in to reply

So, what are today's problems? Swapnil Das · 1 year, 10 months ago

Log in to reply

let us try 2nd question :

we can make following case and i am writing totient function as E,

Case 1 - when \(m\) is prime then E(m) = m - 1, which is even.

Case 2 - when \(m\) is even, clearly it would contain 2 so it even. Dev Sharma · 1 year, 10 months ago

Log in to reply

@Dev Sharma "Clearly it would contain 2" please elaborate. Adarsh Kumar · 1 year, 10 months ago

Log in to reply

@Adarsh Kumar I am sorry. I explained wrong.

Case 2. If m is even then m would be in form m = even . odd then we know that euler of odd number is even. So it would be even. Well, there would be one more, that is, even = even. Even Dev Sharma · 1 year, 10 months ago

Log in to reply

@Dev Sharma I believe i am not correctly understanding your method.Do you mean that \(m=2^{k}*(2a+1)\) where \(2^k\) is the even part of the number and \(2a+1\) the odd part? Adarsh Kumar · 1 year, 10 months ago

Log in to reply

@Adarsh Kumar yes but i am not confident about case 2. And is case 1 and 3 correct? Dev Sharma · 1 year, 10 months ago

Log in to reply

@Dev Sharma Could you explain after this in your case 2?Your case 1 is correct,i am not so sure about case 3,sorry.You could ask someone else.Actually there is a very simple way of proving this.If you want me to post i will. Adarsh Kumar · 1 year, 10 months ago

Log in to reply

@Adarsh Kumar Please post solution. Dev Sharma · 1 year, 10 months ago

Log in to reply

@Adarsh Kumar is it correct? If not, whats the mistake? Dev Sharma · 1 year, 10 months ago

Log in to reply

@Dev Sharma Case 3 - when \(m\) is odd (composite), then m would be divisible by any prime (3,5,7etc) and we know that totient function is multiplicative so, E(m) = E(any prime)E(left out)

also from case 1 we know E(prime) is even, so its even. Dev Sharma · 1 year, 10 months ago

Log in to reply

would it help?

The following results are by Fermet Little Theorm:

\(a^p = a modp\)

\(b^p = b modp\)

then \(a^p + b^p = a + b modp\)

now \((a + b)^p = a + b modp\)

so \((a + b)^p = a^p + b^p modp\) Dev Sharma · 1 year, 10 months ago

Log in to reply

Comment deleted Sep 24, 2015

Log in to reply

@Adarsh Kumar No , his solution is correct. Well there are two forms of Fermat's little theorem.

1) \(a^{p-1} \equiv 1 \pmod{p}\) where \(p\) is a prime and \(a\) is an integer such that \(gcd(a,p)=1\).

2) \(a^p \equiv a \pmod{p}\) where \(p\) is a prime and \(a\) is an integer.

You can see that if you use form (2) , there is no restriction saying \(gcd(a,p)=1\). Nihar Mahajan · 1 year, 10 months ago

Log in to reply

@Dev Sharma Yeah you are right it was pretty simple.Sorry! Adarsh Kumar · 1 year, 10 months ago

Log in to reply

Comment deleted Sep 26, 2015

Log in to reply

Comment deleted Sep 25, 2015

Log in to reply

Comment deleted Sep 26, 2015

Log in to reply

@Nihar Mahajan No not that,i thought it was not simple and i posted it. Adarsh Kumar · 1 year, 10 months ago

Log in to reply

Comment deleted Sep 26, 2015

Log in to reply

@Nihar Mahajan Good point!Ok i am removing it. Adarsh Kumar · 1 year, 10 months ago

Log in to reply

Comment deleted Sep 26, 2015

Log in to reply

@Nihar Mahajan Hey, I posted many RMO practice proof problems but there are 0 comment. (go to my profile to see them). Dev Sharma · 1 year, 10 months ago

Log in to reply

@Nihar Mahajan Thanks for \(Latex\) Dev Sharma · 1 year, 10 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...