# 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).

4 years, 4 months ago

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

• Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
• Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
• Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. list
1. numbered
2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in $$ ... $$ or $ ... $ to ensure proper formatting.
2 \times 3 $2 \times 3$
2^{34} $2^{34}$
a_{i-1} $a_{i-1}$
\frac{2}{3} $\frac{2}{3}$
\sqrt{2} $\sqrt{2}$
\sum_{i=1}^3 $\sum_{i=1}^3$
\sin \theta $\sin \theta$
\boxed{123} $\boxed{123}$

Sort by:

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.

- 4 years, 4 months ago

- 4 years, 4 months ago

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.

- 4 years, 4 months ago

Thanks for the solution!

- 4 years, 4 months ago

Thanx for the solution.

- 4 years, 4 months ago

Is the first statement of your solution a lemma?

- 4 years, 4 months ago

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.

- 4 years, 4 months ago

Yes. It is a lemma. it is easy to prove

- 4 years, 4 months ago

Can you give me hint to prove it? Is it necessary to define a degree to the polynomials?

- 4 years, 4 months ago

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.

- 4 years, 4 months ago

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)$

- 4 years, 4 months ago

No need of all that.See my solution.

- 4 years, 4 months ago

9)$x^3=x+1\Rightarrow x^6=(x^2+2x+1)\Rightarrow x^7=x^3+2x^2+x=2x^2+2x+1$.

- 4 years, 4 months ago

How u got this......explain

- 4 years ago

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.

- 4 years, 4 months ago

Brilliant solution!

- 4 years, 4 months ago

Thank you. See my solution for 2nd question

- 4 years, 4 months ago

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.

- 4 years, 3 months ago

Really elegant one! Thanx for posting it!

- 4 years, 3 months ago

- 4 years, 3 months ago

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$

- 4 years, 4 months ago

Yeah you are right it was pretty simple.Sorry!

- 4 years, 4 months ago

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.

- 4 years, 4 months ago

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.

- 4 years, 4 months ago

"Clearly it would contain 2" please elaborate.

- 4 years, 4 months ago

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

- 4 years, 4 months ago

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?

- 4 years, 4 months ago

yes but i am not confident about case 2. And is case 1 and 3 correct?

- 4 years, 4 months ago

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.

- 4 years, 4 months ago

- 4 years, 4 months ago

is it correct? If not, whats the mistake?

- 4 years, 4 months ago

So, what are today's problems?

- 4 years, 4 months ago

Thanks!

- 4 years, 4 months ago

@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.

- 4 years, 4 months ago

Oh nice idea thanx!

- 4 years, 4 months ago

Looks like giving a good idea gets me a downvote :3

- 4 years, 4 months ago

@Adarsh Kumar In question 7, please mention that a,b and c are distinct. :)

- 4 years, 4 months ago

done!

- 4 years, 4 months ago

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...

- 4 years, 4 months ago

Is this solution correct? I don't think so...

- 4 years, 4 months ago

You assumed that 'n' is prime, which is not given in the question.....

- 4 years, 4 months ago

Yeah , correct.

- 4 years, 4 months ago

@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.

- 4 years, 4 months ago

@Adarsh Kumar P has to be a prime I told you that.

- 4 years, 4 months ago

Ni you didn't,go and see the conversation.

- 4 years, 4 months ago

Oh , sorry if I didn't. Please repost the problem and mention that p is prime.

- 4 years, 4 months ago

Ohk.

- 4 years, 4 months ago

I have a question. How can I give you? (not on slack)

- 4 years, 4 months ago

Give it here.

- 4 years, 4 months ago

If $x^3 = x + 1$ then determine integer a,b,c $x^7 = ax^2 + bx + c$

- 4 years, 4 months ago

Thanx for the question!Kindly delete this comment as i have posted it giving credit to you.

- 4 years, 4 months ago

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)$

- 4 years, 4 months ago

All questions are done!

- 4 years, 4 months ago

Could you please provide the solution for the $6^{th}$ one?

- 4 years, 3 months ago

Since no one has posted the solution for the 6th one yet, should I post it (solution given in the book)?

- 4 years, 3 months ago

- 4 years, 3 months ago

First problem can be solved easily by using binomial therom

- 4 years, 4 months ago

no need

- 4 years, 4 months ago

fermat's theorem, isn't it?

- 4 years, 1 month ago

@Calvin Lin Sir, is it possible for you to close this note since we already have a part 2 for this note.

- 4 years, 3 months ago

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.

Staff - 4 years, 3 months ago

can anybody solve the rmo 2008 Maharashtra region problem 5

- 4 years, 3 months ago

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.

- 4 years, 4 months ago