Difference between revisions of "1977 USAMO Problems/Problem 1"
(→Problem) |
|||
| Line 1: | Line 1: | ||
== Problem == | == Problem == | ||
Determine all pairs of positive integers <math> (m,n)</math> such that | Determine all pairs of positive integers <math> (m,n)</math> such that | ||
| − | <math> (1 | + | <math> (1+x^n+x^{2n}+\cdots+x^{mn})</math> is divisible by <math> (1+x+x^2+\cdots+x^{m})</math>. |
== Solution 1 == | == Solution 1 == | ||
Revision as of 21:41, 21 October 2015
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.
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. 
