1977 USAMO Problems/Problem 1
Contents
[hide]Problem
Determine all pairs of positive integers such that is divisible by .
Solution 1
Denote the first and larger polynomial to be and the second one to be . In order for to be divisible by they must have the same roots. The roots of are the (m+1)th roots of unity, except for 1. When plugging into , the root of unity is a root of if and only if the terms all represent a different (m+1)th root of unity not equal to 1.
Note that if , the numbers represent a complete set of residues minus 0 modulo . However, if not equal to 1, then is congruent to and thus a complete set is not formed. Therefore, divides if and only if
Solution 2
We could instead consider modulo . Notice that , and thus we can reduce the exponents of to their equivalent modulo . We want the resulting with degree less than to be equal to (of degree ), which implies that the exponents of must be all different modulo . This can only occur if and only if , and this is our answer, as shown in Solution 1.
Solution 3
Notice that and , so it remains to prove that . It is clear that and . For any , we can use the fact that , where is the dth cyclotomic polynomial. If , then and share a common cyclotomic polynomial; namely, . But since all the factors of are distinct, cannot be divisible by . We find that must be the solution, since the only shared polynomial is , and we are done.
See Also
1977 USAMO (Problems • Resources) | ||
Preceded by First Question |
Followed by Problem 2 | |
1 • 2 • 3 • 4 • 5 | ||
All USAMO Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.