Difference between revisions of "1977 USAMO Problems/Problem 1"
Chess12500 (talk | contribs) (Added another solution using cyclotomic polynomials) |
Chess12500 (talk | contribs) m (→Solution 3) |
||
Line 15: | Line 15: | ||
==Solution 3== | ==Solution 3== | ||
− | Notice that <math>1+x^n+x^{2n}+...+x^{mn}=\frac{x^{mn+n}-1}{x^n-1}</math> and <math>1+x+x^2+...+x^m=\frac{x^{m+1}-1}{x-1}</math>, so it remains to prove that <math>(x^n-1)(x^{m+1}-1) \mid (x^{mn+n}-1)(x-1)</math>. It is clear that <math>(x^n-1) \mid (x^{mn+n}-1)</math> and <math>(x^{m+1}-1) \mid (x^{mn+n}-1)</math>. For any <math>k \in \mathbb{N}</math>, we can use the fact that <math>x^k-1=\prod_{d \mid k} \ | + | Notice that <math>1+x^n+x^{2n}+...+x^{mn}=\frac{x^{mn+n}-1}{x^n-1}</math> and <math>1+x+x^2+...+x^m=\frac{x^{m+1}-1}{x-1}</math>, so it remains to prove that <math>(x^n-1)(x^{m+1}-1) \mid (x^{mn+n}-1)(x-1)</math>. It is clear that <math>(x^n-1) \mid (x^{mn+n}-1)</math> and <math>(x^{m+1}-1) \mid (x^{mn+n}-1)</math>. For any <math>k \in \mathbb{N}</math>, we can use the fact that <math>x^k-1=\prod_{d \mid k} \Phi _d(x)</math>, where <math>\Phi _d(x)</math> is the dth cyclotomic polynomial. If <math>\gcd(m+1,n) = d > 1</math>, then <math>x^{m+1}-1</math> and <math>x^n-1</math> share a common cyclotomic polynomial; namely, <math>\Phi _d(x)</math>. But since all the factors of <math>x^{mn+n}-1</math> are distinct, <math>(x^{mn+n}-1)(x-1)</math> cannot be divisible by <math>(x^n-1)(x^{m+1}-1)</math>. We find that <math>\gcd(m+1,n) = 1</math> must be the solution, since the only shared polynomial is <math>\Phi _1(x)=x-1</math>, and we are done. |
== See Also == | == See Also == |
Latest revision as of 15:58, 23 June 2022
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.