Maths Olympiad Prep

Library / /374 of 520

Number theory Difficulty 6.4 National olympiad Find the answer

17 Find the number of all positive integers aa that satisfy the following condition: there exist non-negative integers x0,x1,x2,x_{0}, x_{1}, x_{2}, \cdots, x2001x_{2001}, such that ax0=ax1+ax2++ax2001a^{x_{0}}=a^{x_{1}}+a^{x_{2}}+\cdots+a^{x_{2001}}.

A number or a short expression. Fractions can be typed as 3/2, and spacing doesn't matter.

Solution

17. If aa is a number that satisfies the condition, then ax0>1a^{x_{0}}>1, so a>1a>1. At this point, taking

both sides modulo a1a-1, we know
so \square
ax0=ax1+ax2++ax200111++12001(moda1),a12000.\begin{array}{c} a^{x_{0}}=a^{x_{1}}+a^{x_{2}}+\cdots+a^{x_{2001}} \\ 1 \equiv \underbrace{1+\cdots+1}_{2001 \uparrow}(\bmod a-1), \\ a-1 \mid 2000 . \end{array}

On the other hand, if a>1a>1 and a12000a-1 \mid 2000, then we can take x1,x2,,x2001x_{1}, x_{2}, \cdots, x_{2001} to be aa numbers as 00, a1a-1 numbers as 11, a1a-1 numbers as 22, ..., a1a-1 numbers as k1k-1, where k=2000a1k=\frac{2000}{a-1}, and take x0=kx_{0}=k, then we have ax0=ax1+ax2++ax2001a^{x_{0}}=a^{x_{1}}+a^{x_{2}}+\cdots+a^{x_{2001}}.

Therefore, aa is a number that satisfies the condition if and only if a>1a>1 and a12000a-1 \mid 2000, and there are 20 such aa.

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.