Maths Olympiad Prep

Library / NMO Selection Tests for the Junior Balkan Mathematical Olympiad /21 of 62

NMO Selection Tests for the Junior Balkan Mathematical Olympiad

Number theory Difficulty 5.5 AIME, harder Prove it Romania

Let p>5p > 5 be a prime. Find all positive integers xx such that 5p+x5p + x divides 5pn+xn5p^n + x^n, for all n∈N∗n \in \mathbb{N}^*.

Solution

1∘ 5p+x∣5pn+xn for all n≥1;1^\circ \ 5p + x \mid 5p^n + x^n \text{ for all } n \ge 1;
2∘ 5p+x∣30p2.2^\circ \ 5p + x \mid 30p^2.
To prove 1∘⇒2∘1^\circ \Rightarrow 2^\circ, set n=2n = 2 to obtain 5p+x∣5p2+x2⇒5p+x∣(x+5p)(x−5p)+30p25p+x \mid 5p^2+x^2 \Rightarrow 5p+x \mid (x+5p)(x-5p) + 30p^2, hence 5p+x∣30p25p+x \mid 30p^2, as needed. For the second implication, observe that 5p+x∣30p25p+x \mid 30p^2 implies 5p+x∣(x+5p)(x−5p)+30p25p+x \mid (x+5p)(x-5p) + 30p^2, so 5p+x∣5p2+x25p+x \mid 5p^2+x^2. The identity 5pn+1+xn+1=(5pn+xn)(p+x)−px(5pn−1+xn−1)5p^{n+1} + x^{n+1} = (5p^n + x^n)(p+x) - px(5p^{n-1} + x^{n-1}) holds for all integers n≥2n \ge 2. Consequently, by induction, the claim 1∘1^\circ is proved.
The divisors of 30p230p^2 greater than 5p5p are 6p,10p,15p,30p,p2,2p2,3p2,5p2,6p2,10p2,15p26p, 10p, 15p, 30p, p^2, 2p^2, 3p^2, 5p^2, 6p^2, 10p^2, 15p^2 and 30p230p^2. Subtracting 5p5p from the numbers listed above yields the required values for xx.

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.