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

too easy no? $ a_1\equiv a_1\cdot a_2\equiv a_1\cdot a_2\cdot a_3\equiv \dots \equiv a_1\cdot\dots\cdot a_k\equiv a_1\cdot\dots\cdot a_{k - 2}\cdot a_k\equiv\dots\equiv a_1\cdot a_{k}\equiv a_k$. Therefore, $ 0 < |a_1 - a_k| < n$ is divisible by $ n$. Contradiction. P.S Please add 's' in the statement, integers

We prove inductively that $ n|a_1a_l - a_1$ for $ l=2, 3, \ldots, k$. We know that it's true for $ l=2$. Suppose that it's true for $ l$. Since $ n|a_1a_l-a_1$ and $ n|a_la_{l+1} - a_l$ we know that also $ n|(a_1a_l-a_1)a_{l+1} - a_1a_l+a_1$ and $ n|a_1a_la_{l+1} - a_1a_l$. Substracting gives exactly what we want and the induction proof is complete. Since $ n|a_1a_k - a_1$ we can't have $ n|a_k(a_1-1)=a_ka_1 - a_k$ since it would imply $ n|a_1-a_k$, which is impossible.

It is an easy problem!!! I solved it!!! It's very similar to ychjae's, but I complicated stuff with prime factors of n...

Another wording for the same approach : all equalities are considered modulo $ n$. We know that $ a_{i+1}a_i = a_i$ for all $ i \leq k-1$, thus clearly $ a_ia_{i-1} \cdots a_1 = a_1$ for all $ i \leq k$. But, leaving $ a_i$, this also gives $ a_i(a_{i-1} \cdots a_1) = a_ia_1$ for all $ i \leq k$. It follows that $ a_ka_1 = a_1$. Since $ k \geq 2$ and $ a_k,a_1$ belong to $ \{1, \cdots , n \}$ we cannot have $ a_k = a_1$, thus $ a_ka_1 \neq a_k$, as desired. Pierre.

too easy I think, it only took me 15 minutes. my approach is similar to ychjae's. i used chinese remainder theorem.

Same solution as ychjae, but to finish the problem I used chinese remainder theorem as well as johan I think it is simple, yet very nice problem

Suppose the contrary is true.Then we have $ n^{k} |\prod^{k}_{i = 1} a_{i}(a_{i}-1)$ which imply there exist j such that $ n|a_{j}(a_{j} - 1)$ Then by considering two cases $ "n|a_{j}"$ and $ "n|a_{j } - 1"$ we have $ a_{j} = a_{j - 1}$ or $ a_{j} = a_{j + 1}$.A contradiction.

There is a simple method to prove the last. $ p|a_{i} -a_{i+1}$, $ q|(a_{i}-1)-(a_{i+1}-1)$, so $ pq|a_{i} -a_{i+1}$. A Contradiction!!

I solved it in the exam from this way: clearly a1=a1.a2 (mod n) then a1.a3=a1.a2.a3 (mod n) and from a2.a3=a2 (mod n) we have a1=a1.a2=a1.a3 (mod n) and we have from the same way a1=a1.a2=a1.a3=...=a1.ak (mod n) so a1=a1.ak (mod n) (*) For the sake of contradiction we may assume that ak=a1.ak (mod n) then we have a1=ak (mod n) from (*) ,contradiction.

Suppose $ n|a_k(a_1 - 1)$. If $ \gcd (a_1,n) = 1$, we have $ n|a_2-1$, then $ \gcd (a_2,n) = 1$ and so $ n|a_3 - 1 \rightarrow a_2 = a_3$, a contradiction. If $ \gcd (a_1,n) = n$, we have $ \gcd (a_1-1,n)=1$, hence $ n|a_k \rightarrow a_1=a_k=n$, contradiction again. Now, we know that $ 1 < \gcd (a_1,n) < n$. This means that there is a prime $ p$ such that $ p$ divides both $ a_1$ and $ n$, yet the exponent of $ p$ in the prime factorization of $ a_1$ is less than the exponent of $ p$ in the prime factorization of $ n$. Hence, $ p|a_2-1$. But then $ p$ does not divide $ a_2$, so $ p|a_3-1$, and so on, until we get $ p|a_1-1$, which is absurd because we said $ p|a_1$.

uglysolutions why $ p$ divides $ a_2-1$?

Because $ n|a_1(a_2 - 1)$ and the exponent of $ p$ in the prime factorization of $ a_1$ is less than the exponent of $ p$ in the prime factorization of $ n$, hence there must be at least one more $ p$ factor in $ a_2 - 1$. I mean, if $ p^{\alpha}||n$ and $ p^{\beta}||a_1$, we have $ p^{\alpha - \beta}|a_2 - 1$, since $ \alpha > \beta \rightarrow \alpha - \beta \geq 1$ we can say $ p|a_2 - 1$.

Easy but very good one.

Remember this is problem 1, so it's meant to be attack-able by most of the contestants.

For what it's worth, my writeup: We'll prove the contrapositive. Suppose $ n | a_i(a_{i + 1} - 1)$ with cyclic indices. We need to show that the $ a_i$ aren't distinct. In fact, they're all equal. Let $ p^r$ be a prime power dividing $ n$. If $ p | a_i$ for a particular $ i$ then $ p^r | a_{i - 1}(a_i - 1)$ implies $ p^r | a_{i - 1}$, so by induction $ p^r | a_i$ for all $ i$. If $ p \not | a_i$ for a particular $ i$ then $ p^r | a_i(a_{i + 1} - 1)$ implies $ p^r | a_{i + 1} - 1$, so by induction $ p^r | a_i - 1$ for all $ i$. In either case the $ a_i$ are all equal $ \bmod p^r$. By CRT the $ a_i$ are all equal $ \bmod n$.

Simple reduction: Say $ a_ma_n \equiv a_m$, and $ a_na_k \equiv a_n$; then $ a_ma_k \equiv a_ma_na_k \equiv a_na_m$; applying this to the edge case $ a_{k-1}a_k \equiv a_{k-1}$ and $ a_ka_1 \equiv a_k$, notice that $ a_{k-1}a_1 \equiv a_ka_{k-1} \equiv a_{k-1}$; this reduces the case $ k$ to $ k-1$. For $ k=2$, the condition becomes $ a_1 \equiv a_1a_2 \equiv a_2$, a clear contradiction.

I do not know if my solution is correct, but here is what I deduced: Suppose that $ n|a_k (a_1-1).$ Consider $ p$ a prime such that $ p|n$ and $ p|a_1$. Because $ p|a_k(a_1-1)$ and $ (a_1,a_1-1)=1$ it results that $ p|a_k.$ Now, $ p|a_{k-1}(a_k-1) \Rightarrow p|a_{k-1} \Rightarrow ... \Rightarrow p|a_2.$ In conclusion, $ p|a_i$ where $ i=1,2,...,k.$ A similar argument can be used to prove that if $ q$ is a prime with $ q|n$ and $ q|a_1-1$, then $ q|a_i-1$, where $ i=1,2,...,k.$ Because $ n|a_1(a_2-1)$, there exist $ A$ and $ B$ such that $ A|a_1$ and $ B|a_2-1$, where $ (A,B)=d$ and $ AB=n$. It is obvious that $ (A,B)=1$ because otherwise there is a prime $ p$ so that $ p|a_1$ and $ p|a_2-1 \Rightarrow p|a_1 -1 \Rightarrow p|1,$ impossible. $ A|a_1 \Rightarrow A|a_2 \Rightarrow A|a_1-a_2$ $ B|a_2-1 \Rightarrow B|a_1-1 \Rightarrow B|a_1-a_2$ $ \Rightarrow AB=n|a_1-a_2$, impossible, because $ a_1 \not= a_2$ and $ |a_1-a_2|<n.$

The authors of problems 1,2,3 at IMO'2009 have been posted at http://www.artofproblemsolving.com/Wiki/index.php/IMO_Problems_and_Solutions

almost midnight problem solving, and i hate and love it. building up my confidence bit by bit. FTSOC let $n|a_k(a_1-1)$. $n|a_1(a_2-1)$. multiply this by $a_3-1$ which gives us $n|a_1(a_3-1)$ by $n|a_2(a_3-1)$. We repeat this and get $n|a_1(a_k-1)$. Which means that $a_1 \equiv a_k (mod n)$. Since both $a_1$ and $a_k$ are equal or less than $n$, we get a contradiction. $\blacksquare$

Assume FTSOC that $n$ divides $a_k(a_1-1)$. Then, taking indices modulo $k$, the condition implies that $a_i \equiv a_ia_{i+1} \pmod n$ for all $i$. Then we have \[ a_1 \equiv a_1a_2 \equiv a_1a_2a_3 \equiv \dots \equiv a_1a_2\dots a_k \equiv a_2a_3 \dots a_k \equiv a_2a_3 \dots a_{k+1}\equiv \dots \equiv a_2 \pmod n, \]so $a_1 = a_2$, contradiction. Therefore, $n \nmid a_k(a_1-1)$.

$a_1a_2 \equiv a_1 \pmod n$. $a_2a_3 \equiv a_2 \pmod n \implies a_1a_2a_3 \equiv a_1a_2 \equiv a_1 \pmod n$ Again, $a_1a_2 \equiv a_1\pmod n \implies a_1a_2a_3 \equiv a_1a_3 \pmod n$. So, $a_1a_3 \equiv a_1 \pmod n$. Continuing this process, we can easily say that $a_1a_k\equiv a_1\pmod n$. So, $a_k(a_1-1)\equiv a_k-a_1 \pmod n.$ Now, $0<|a_k-a_1|<n$ as $a_i \in \{1,2,\cdots n\}\; \forall \;i\in\{1,2,\cdots,k\}$. So, $\boxed{n \nmid a_k(a_1-1)} $

Assume for the sake of contradiction that $n$ divided all of $a_i(a_{i+1} - 1)$, taking indices modulo $n.$ Extend $a_i$ such that $a_{n+i} = a_i$ for all $i.$ Claim: $$a_i a_{i+1} \dots a_{i+k} \equiv a_i \pmod{n}$$for all positive $i$ and nonnegative $k.$ Proof: By induction on $k.$ The base case $k=0$ is obvious, and for the inductive step, assume that this holds for a certain $k$ and all positive $i.$ Then $$a_{i+1} \dots a_{i+k+1} \equiv a_{i+1} \pmod{n},$$so multiplying both sides by $a_i$ gives $$a_i a_{i+1} \dots a_{i+k+1} \equiv a_i a_{i+1} \equiv a_i \pmod{n}$$by the problem condition, so our induction is complete. In particular, taking $k = n-1,$ we get that $a_1 \dots a_n \equiv a_1 \equiv a_2 \equiv \dots \equiv a_n \pmod{n},$ contradiction since all the $a_i$ are distinct.

Sketch: Try a proof by contradiction. We will see that $a_ia_{i+1} \equiv a_1a_2a_3 \dots a_k \pmod{n}$. From here, it follows that $a_1 \equiv a_2 \equiv a_3 \dots \equiv a_k \pmod{n}$ which is a contradiction.

Assume that this is possible, we force a contradiction. First, clearly observe $a_i$ can never be $n$, because then we would have $n \mid a_{i - 1}(a_{i} - 1)$ (indices taken modulo $k$ since assuming that $n \mid a_k (a_1 - 1)$ means that $n \mid a_i (a_{i + 1} - 1)$ for all $i$), which is clearly forces $a_{i - 1}$, violating the distinct condition. Take some arbitrary index $i$. Now there exist integers $p, q > 1$ such that $pq = n, p \mid a_{i}, q \mid a_{i + 1} - 1$. Now since $\gcd(p, a_i - 1) = 1$, and $p \mid a_{i - 1} (a_i - 1)$, we have $p \mid a_{i - 1}$. Repeating this logic, we have $p \mid a_{i}$ for all $i$. Likewise, we can show $q \mid a_{i + 1} - 1$ for all $i$. Now if $p,q$ share a common factor, we have an obvious contradiction since this common factor divides $a_i$ and $a_i - 1$. If they don't we can use $CRT$ to show all $a_i$ are congruent mod $n$, which is a contradiction.

let us assume to the contrary that $n \mid a_k(a_1-1)$ that is $a_ka_1 \equiv a_k \pmod n$. now since $n$ divides $a_i(a_{i+1} - 1)$ for $i = 1,2,\dots,k-1$, we have \[ a_1a_2 \equiv a_1 \pmod n \]\[ a_1a_2a_k \equiv a_1a_k \pmod n \]\[ a_2a_k \equiv a_k \pmod n \]and similarly \[ a_2a_3 \equiv a_2 \pmod n \]\[ a_2a_3a_k \equiv a_2a_k \pmod n \]\[ a_3a_k \equiv a_k \pmod n \]and so on we get $a_{k-1}a_k \equiv a_k \pmod n$, but we also have $a_{k-1}a_k \equiv a_{k-1} \pmod n$. This implies \[a_{k-1} \equiv a_k \pmod n\]but both $a_{k-1}$ and $a_k$ are distinct integers $\leq n$, which is not true, thus our initial assumption i.e. $n$ divides $a_i(a_{i+1} - 1)$ is false

Redacted

Assume otherwise. We have $$a_1(a_2-1)\equiv 0\pmod n$$$$a_2(a_3-1)\equiv 0\pmod n$$$$a_3(a_4-1)\equiv 0\pmod n$$$$\dots$$$$a_{k-1}(a_{k}-1)\equiv 0\pmod n$$$$a_{k}(a_{1}-1)\equiv 0\pmod n.$$Let $q=p^e$ be any prime power dividing $n$. Note that we have $$a_1\equiv 0\pmod q$$or $$a_{i+1}\equiv 1\pmod q.$$ If $a_1\equiv 0\pmod q$, we have $a-1\ne 1\pmod q$, so $a_k\equiv 0\pmod q$. Repeating this argument gives $a_i\pmod q$ constant. If $a_2\equiv 1\pmod q$, we have $a_2\ne 0\pmod q$, so $a_3\equiv 1\pmod q$. Repeating this argument gives $a_i\pmod q$ constant. By the Chinese Remainder Theorem, we have $a_i\pmod n$ constant. However, this finishes.

Key idea: break into prime powers and do divisibility stuff, then combine using CRT.

Slick question. Let $n= p_{1}^{a_{1}}\cdot p_{2}^{a_{2}} \cdot … \cdot p_{l}^{a_{l}}$ is the unique prime factorization of $n$. Assume that for some $1 \le j \le k $, $j \in \mathbb{N}$, $p_{s} \mid a_{j}-1$, where $p_{s}$ is a prime factor of $n$. Then $p_{s} \nmid a_{j} \implies p_{s}^{a_{s}} \mid a_{j+1}-1$, $\forall 1\le s \le l$ $\implies a_{j+1}-1 \ge p_{1}^{a_{1}}\cdot p_{2}^{a_{2}} \cdot … \cdot p_{l}^{a_{l}}=n$, which is a contradiction since $\{a_{1},a_{2},…,a_{k}\} \in \{1,2,…,n\}$. Hence, $p_{s}^{a_{s}} \mid a_{j-1}$, which again gives $\implies a_{j-1} \ge p_{1}^{a_{1}}\cdot p_{2}^{a_{2}} \cdot … \cdot p_{l}^{a_{l}}=n$, $ \forall$ $1\le j\le k$, another contradiction. $\blacksquare$ edit: my proof implies that such a set up cannot even exist irrespective of whether $n \mid a_{1}(a_{k}-1)$ or not. Is it correct? I cannot find any mistake.

FTSOC assume otherwise. Then $$a_k \equiv a_1 a_k \equiv a_1a_2a_k \equiv \cdots \equiv a_1a_2a_3 \cdots a_{k-1}a_k \equiv a_1a_2 \cdots a_{k-1} \equiv \cdots \equiv a_1a_2 \equiv a_1 \pmod n,$$a contradiction. QED

Assume FTSOC that $n \mid a_k(a_1 - 1)$. Consider a prime $p \mid n$. Suppose $p^e \mid n$ but $p^{e+1} \nmid n$. Claim: We either have $p^e \mid a_i - 1$ for all $i = 1, 2, \dots, k$, or we have $p^e \mid a_i$ for all $i = 1, 2, \dots, k$. Proof. Note that from the divisibilities, \[ p \mid a_1 - 1 \implies p^e \mid a_2 - 1 \implies p^e \mid a_3 - 1 \implies \dots \implies p^e \mid a_k - 1 \]similarly, \[ p \mid a_k \implies p^e \mid a_{k-1} \implies p^e \mid a_{k-2} \implies \dots \implies p^e \mid a_1 \]obviously since $p \mid a_1 - 1$ and $p^e \mid a_1$ cannot hold simultaneously, then \[ p \mid a_1 - 1 \implies p \nmid a_k \implies p^e \mid a_1 - 1 \]Similarly, \[ p \mid a_k \implies p \nmid a_1 - 1 \implies p^e \mid a_k \]which establishes the two cases. $\blacksquare$ Then by CRT, this implies that all $a_i$ have the same residue modulo $n$, which is a clear contradiction. $\blacksquare$

OG! We proceed with contradiction. FTSOC, Assume that $ n$ divides $ a_i(a_{i + 1} - 1)$ for $ i = 1,2,\ldots,k $ $k \leq n$. Consider a prime $p$ dividing $n$, let $t= v_p(n)$ we have that $p^t$ divides $ a_i(a_{i + 1} - 1)$ for $ i = 1,2,\ldots,k $ set $i=k$, $p \mid a_k(a_1 - 1)$ Case 1: $p^t|a_k$ Since $p^t|(a_{k-1})(a_k-1).$ Now, since $p^t|a_k \implies p^t \nmid (a_k-1)$, hence $p^t|(a_{k-1})$ we continue this similarly till we get that $p^t|a_i$ for all $i = 1 \cdots k$. Thus $\prod_{p \mid n}p^{v_p(n)} =n \mid a_i $ for all $i= 1 \cdots k$ But $a_1,a_2$ are distinct and are in the range $[1,n]$. Since, $n$ divides $a_1,a_2$ hence both must be equal to $n$. A contradiction! Case2: $p \nmid a_k$ This means that $p^t \mid a_1-1$. Since $p^t|(a_{1})(a_2-1).$ Now, since $p^t|a_1-1 \implies p^t \nmid (a_1)$, hence $p^t|(a_{2}-1)$ we continue this similarly till we get that $p^t|a_i-1$ for all $i = 1 \cdots k$. Thus $\prod_{p \mid n}p^{v_p(n)} =n \mid a_i-1 $ for all $i= 1 \cdots k$ But $a_1-1,a_2-1$ are distinct and are in the range $[0,n-1]$. Since, $n$ divides $a_1-1,a_2-1$ hence both must be equal to $0$. A contradiction! Hence we are done!

headsolve