Difference between revisions of "2009 IMO Problems/Problem 1"

Revision as of 05:23, 23 July 2009

Problem

Let $n$ be a positive integer and let $a_1,\ldots,a_k (k\ge2)$ be distinct integers in the set $\{1,\ldots,n\}$ such that $n$ divides $a_i(a_{i+1}-1)$ for $i=1,\ldots,k-1$ . Prove that $n$ doesn't divide $a_k(a_1-1)$ .

Author: Ross Atkins, Australia

--Bugi 10:23, 23 July 2009 (UTC)Bugi

Solution

Let $n=pq$ such that $p\mid a_1$ and $q\mid a_2-1$ . Suppose $n$ divides $a_k(a_1-1)$ . Note $q\mid a_2-1$ implies $(q,a_2)=1$ and hence $q\mid a_3-1$ . Similarly one has $q\mid a_i-1$ for all $i$ 's, in particular, $p\mid a_1$ and $q\mid a_1-1$ force $(p,q)=1$ . Now $(p,a_1-1)=1$ gives $p\mid a_k$ , similarly one has $p\mid a_i$ for all $i$ 's, that is $a_i$ 's satisfy $p\mid a_i$ and $q\mid a_i-1$ , but there should be at most one such integer satisfies them within the range of $1,2,\ldots,n$ for $n=pq$ and $(p,q)=1$ . A contradiction!!!