Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

2009 IMO Problems/Problem 1

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

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!!!

Solution 2

Let $n = p_1^{b_1}p_2^{b_2} \cdots p_s^{b_s}$. Then after toying around with the $p_i^{b_i}$ and what they divide, we have that $p_i^{b_i} \nmid a_k$, and so in particular, $n \nmid a_k$.

Assume by way of contradiction that $n \mid a_k(a_1 - 1)$. Then $n \mid a_1 - 1$. Now we shift our view towards the $a_i(a_{i + 1} - 1)$. Here each $p_i^{b_i}$ divides $a_i(a_{i + 1} - 1) \implies a_ia_{i + 1} \equiv a_i \pmod{p_i^{b_i}}$. Hence we have the chain of equivalences $a_1a_2 \equiv a_1 \pmod{p_i^{b_i}}, a_2a_3 \equiv a_2 \pmod{p_i^{b_i}}, \dots, a_{k - 1}a_k \equiv a_{k - 1} \pmod {p_i^{b_i}}$. Now we also have that $p_i^{b_i} \mid n \mid a_1 - 1$. Thus $a_1 \equiv 1 \pmod{p_i^{b_i}}$. Now plugging this value of $a_1$ modulo $p_i^{b_i}$, we obtain that $a_1 \equiv a_2 \equiv a_3 \equiv \cdots a_k \equiv 1 \pmod{p_i^{b_i}}$. Hence this chain of congruences is also true for $n$ as $p_i$ was arbitrary. However as all the $a_i \in \{1, 2, \dots, n\}$ we have that not all the $a_i$ are distinct, and so this is a contradiction.

See Also

2009 IMO (Problems) • Resources
Preceded by
First Problem 		1 • 2 • 3 • 4 • 5 • 6 Followed by
Problem 2
All IMO Problems and Solutions
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2009_IMO_Problems/Problem_1&oldid=204538"