2001 USAMO Problems/Problem 5
Let be a set of integers (not necessarily positive) such that
(a) there exist with ;
(b) if and are elements of (possibly equal), then also belongs to .
Prove that is the set of all integers.
In the solution below we use the expression is stable under to mean that if belongs to then also belongs to . If , then by (B), is stable under and , hence stable under . Similarly is stable under . Hence is stable under and whenever is an integer linear combination of numbers of the form with . In particular, this holds for , where .
Since by (A), it suffices to prove that . For the sake of contradiction, assume that . Let be a prime dividing . Then for all . In other words, for each , either or . Given , by (B), so or . Hence By (A), there exist some and in such that , that is, at least one of or cannot be divisible by . Denote such an element of by : thus, . Similarly, by (A), , so cannot divide both and . Thus, there is an element of , call it , such that . By , and . By (B), . Taking in yields either or , so . Now says that all elements of are even, contradicting (A). Hence our assumption is false and is the set of all integers.
|2001 USAMO (Problems • Resources)|
|1 • 2 • 3 • 4 • 5 • 6|
|All USAMO Problems and Solutions|