1987 IMO Problems/Problem 6
Problem
Let be an integer greater than or equal to 2. Prove that if is prime for all integers such that , then is prime for all integers such that .
Solution
First observe that if is relatively prime to , , , , then is relatively prime to any number less than . Since if , then we can choose some to make lies in range , so is relatively prime to . Hence is also. If we also have , then we can conclude that is a prime. Since there must be a factor of less than .
Let where , so is the greatest integer less than or equal to .(to see this, just let , then we can write , so ).
Assume that is prime for . We show that is prime for . By our observation above, it is sufficient to show that and is relatively prime to all of . We have . Since , we have , and . Hence Now if has a factor which divides in the range to , then so does which have the form with in range to .
1987 IMO (Problems) • Resources | ||
Preceded by Problem 5 |
1 • 2 • 3 • 4 • 5 • 6 | Followed by Last question |
All IMO Problems and Solutions |