Problem 1 from the IMO 2009

Here is Problem 1 from the IMO 2009:

Solution

|Activities| |Contact| |Front page| |Contents| |Algebra| |Store|

Let first k = 2, and assume that n|b(a - 1). No non-trivial factor of t may divide b, and no non-trivial factor of s may divide a - 1, implying that s|b. We are therefore in a position to apply the Chinese Remainder Theorem:

The theorem tells us that there is a unique solution modulo lcd(s, t) = n. However, due to the symmetry in the conditions for a and b, we also have

which contradicts the assumption that a and b are different.

For k = 3, we are given that n|b(c - 1) where c = a₃. Assume, as before, n|c(a - 1).

There are s and t different from 1 and n such that s|a and t|(b - 1). No non-trivial factor of t may divide b. From n|b(c - 1) it then follows that t|(c - 1). If not s itself, then one of its factors, say, s₀ divides b: s₀|b, s₁t|(c - 1), where s = s₀s₁.

Similarly, n|c(a - 1) implies that σ₀|c and σ₁s₁t|(a - 1), where σ₀σ₁ = s₀. It's now one of the two, either σ₁s₁ = 1 or not. In the former case, the Chinese Remainder theorem leads to a contradiction. In the latter case, there appears a non-trivial factor common to both a and and a - 1. Again a contradiction.

For greater k, we always have t|a_i+1 - 1. As we progress from 1 to larger i, additional factors may be borrowed from s. If this happens, then a and a - 1 will have shown to have common factors. Otherwise a contradiction is reached via the Chinese Remainder theorem.

A shorter and a more formal solution was posted at the artofproblemsolving.com forum by mathman145.

We know that n divides a_i(a_{i + 1} - 1), i = 1, ..., k - 1. The condition is equivalent to saying that

so that

Now assume that a_k(a₁ - 1) is divisible by n. Then, similarly to the above

implying that a₁ = a₂ (mod n) which is impossible for two distinct positive integers both less than n.

|Activities| |Contact| |Front page| |Contents| |Algebra| |Store|