MathDB

9.2

Part of 1995 All-Russian Olympiad Regional Round

Problems(1)

Numbers around a circle

Source: Russia 95

12/15/2006
Is it possible to place 19951995 different natural numbers along a circle so that for any two of these numbers, the ratio of the greatest to the least is a prime? I feel that my solution's wording and notation is awkward (and perhaps unnecessarily complicated), so please feel free to critique it:
Suppose that we do have such a configuration a1,a2,...a1995a_{1},a_{2},...a_{1995}. WLOG, a2=p1a1a_{2}=p_{1}a_{1}. Then a2a3=p2,1p2\frac{a_{2}}{a_{3}}= p_{2}, \frac{1}{p_{2}} a3a4=p3,1p3\frac{a_{3}}{a_{4}}= p_{3}, \frac{1}{p_{3}} ...... a1995a1=p1995,1p1995\frac{a_{1995}}{a_{1}}= p_{1995}, \frac{1}{p_{1995}} Multiplying these all together, a2a1=∏pk∏pj=p1\frac{a_{2}}{a_{1}}= \frac{\prod p_{k}}{\prod p_{j}}= p_{1} Where ∏pk\prod p_{k} is some product of the elements in a subset of {p2,p3,...p1995}\{ p_{2},p_{3}, ...p_{1995}\}. We clear denominators to get p1∏pj=∏pkp_{1}\prod p_{j}= \prod p_{k} Now, by unique prime factorization, the set {pj}∪{p1}\{ p_{j}\}\cup \{ p_{1}\} is equal to the set {pk}\{ p_{k}\}. However, since there are a total of 19951995 primes, this is impossible. We conclude that no such configuration exists.
rationumber theoryprime factorization