1983 IMO Problems/Problem 3
Problem
Let , and be positive integers, no two of which have a common divisor greater than . Show that is the largest integer which cannot be expressed in the form , where , and are non-negative integers.
Solution 1
First off, I prove is un-achievable. Also, assume WLOG .
Assume , then take the equation to give us . By CRT and , we take this equation mod a and mod b to give us , and (and using all numbers are relatively prime pairwise). Substituting this back into the original equation gives us , contradiction (this is where the part comes in).
Now, let , and if a solution exists where then we are done because we can add to always.
Consider the set , where and where .
Therefore, we get . This is the same as after doing some simplifying. By CRT, this must hold mod a and mod b and because . Mod gives us , for which a value of obviously exists mod , which can be chosen from the set of values we have assigned for . Similar method shows a value of exists mod from the set we have given to .
Now, we already know that . Also, the LHS of the equation is at least , therefore and we are done.
This solution was posted and copyrighted by binomial-theorem. The original thread for this problem can be found here: [1]
Solution 2
First we will prove is unattainable, as such: Suppose . Then, taking this mod , we have that , so , and . Similarly, , and , so , , and . Thus, , so , which is a contradiction.
Now we will prove all is attainable, as such: consider the integer such that and . Rearranging the equation yields , so set . We see that , so is a positive integer (obviously . Now, note that since , we have that , so . Thus, so , so by Chicken Mc-Nugget theorem, there exist that satisfy the equation and are now done.
This solution was posted and copyrighted by Stormersyle. The original thread for this problem can be found here: [2]
1983 IMO (Problems) • Resources | ||
Preceded by Problem 2 |
1 • 2 • 3 • 4 • 5 • 6 | Followed by Problem 4 |
All IMO Problems and Solutions |