2009 IMO Problems/Problem 1
Contents
[hide]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.
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 |