# 2009 IMO Problems/Problem 1

## Problem

Let be a positive integer and let be distinct integers in the set such that divides for . Prove that doesn't divide .

*Author: Ross Atkins, Australia*

## Solution

Let such that and . Suppose divides . Note implies and hence . Similarly one has for all 's, in particular, and force . Now gives , similarly one has for all 's, that is 's satisfy and , but there should be at most one such integer satisfies them within the range of for and . A contradiction!!!

## Solution 2

Let . Then after toying around with the and what they divide, we have that , and so in particular, .

Assume by way of contradiction that . Then . Now we shift our view towards the . Here each divides . Hence we have the chain of equivalences . Now we also have that . Thus . Now plugging this value of modulo , we obtain that . Hence this chain of congruences is also true for as was arbitrary. However as all the we have that not all the are distinct, and so this is a contradiction.