Maths Olympiad Prep

Library / Silk Road Mathematics Competition competition problems /2 of 25

Silk Road Mathematics Competition competition problems

Number theory Difficulty 4.7 AIME Prove it Silk Road Mathematics Competition

Let aa, bb, cc, dd be positive integers such that dd divides a2b+ca^{2b} + c and d≥a+cd \ge a + c. Prove that d≥a+a2bd \ge a + \sqrt[2b]{a}.

Solution

We have a2b+c≡(d−a)2b+c(modd)a^{2b} + c \equiv (d - a)^{2b} + c \pmod d, since
a2b−(d−a)2b=(a2−(d−a)2)××(a2(b−1)+a2(b−2)(d−a)2+⋯+a2(d−a)2(b−2)+(d−a)2(b−1)) a^{2b} - (d - a)^{2b} = (a^2 - (d - a)^2) \times \\ \times (a^{2(b-1)} + a^{2(b-2)}(d - a)^2 + \dots + a^2(d - a)^{2(b-2)} + (d - a)^{2(b-1)})
a2b−(d−a)2b⋮(a+(d−a))=d. a^{2b} - (d - a)^{2b} \vdots (a + (d - a)) = d.
We deduce consequently (d−a)2b+c≥d(d - a)^{2b} + c \ge d
⇒(d−a)2b≥(d−c)≥a⇒d−a≥a2b⇒d≥a+a2b. \Rightarrow (d - a)^{2b} \ge (d - c) \ge a \Rightarrow d - a \ge \sqrt[2b]{a} \Rightarrow d \ge a + \sqrt[2b]{a}.

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.