Maths Olympiad Prep

Library / /10 of 15

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 nNn \in \mathbb{N}^*.

Solution

1 5p+x5pn+xn for all n1;1^\circ \ 5p + x \mid 5p^n + x^n \text{ for all } n \ge 1;
2 5p+x30p2.2^\circ \ 5p + x \mid 30p^2.
To prove 121^\circ \Rightarrow 2^\circ, set n=2n = 2 to obtain 5p+x5p2+x25p+x(x+5p)(x5p)+30p25p+x \mid 5p^2+x^2 \Rightarrow 5p+x \mid (x+5p)(x-5p) + 30p^2, hence 5p+x30p25p+x \mid 30p^2, as needed. For the second implication, observe that 5p+x30p25p+x \mid 30p^2 implies 5p+x(x+5p)(x5p)+30p25p+x \mid (x+5p)(x-5p) + 30p^2, so 5p+x5p2+x25p+x \mid 5p^2+x^2. The identity 5pn+1+xn+1=(5pn+xn)(p+x)px(5pn1+xn1)5p^{n+1} + x^{n+1} = (5p^n + x^n)(p+x) - px(5p^{n-1} + x^{n-1}) holds for all integers n2n \ge 2. Consequently, by induction, the claim 11^\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,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.