1977 USAMO Problems/Problem 1: Difference between revisions
Creation! |
|||
| Line 4: | Line 4: | ||
== Solution == | == Solution == | ||
{{ | |||
Denote the first and larger polynomial to be <math>f(x)</math> and the second one to be <math>g(x)</math>. In order for <math>f(x)</math> to be divisible by <math>g(x)</math> they must have the same roots. The roots of <math>g(x)</math> are the mth roots of unity, except for 1. When plugging into <math>f(x)</math>, the root of unity is a root of <math>f(x)</math> if the terms <math>x^n, x^{2n}, x^{3n}, \cdot x^{mn}</math> all represent a different mth root of unity. | |||
Note that if <math>\\gcd(m,n)=1</math>, the numbers <math>n, 2n, 3n, \cdots, mn</math> represent a complete set of residues modulo <math>m</math>. Therefore, <math>f(x)</math> divides <math>g(x)</math> only if <math>\boxed{\\gcd(m,n)=1}</math> <math>\blacksquare</math> | |||
== See Also == | == See Also == | ||
Revision as of 18:13, 5 April 2013
Problem
Determine all pairs of positive integers 
such that
$(1\plus{}x^n\plus{}x^{2n}\plus{}\cdots\plus{}x^{mn})$ (Error compiling LaTeX. Unknown error_msg) is divisible by $(1\plus{}x\plus{}x^2\plus{}\cdots\plus{}x^{m})$ (Error compiling LaTeX. Unknown error_msg).
Solution
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 mth roots of unity, except for 1. When plugging into , the root of unity is a root of if the terms 
all represent a different mth root of unity.
Note that if 
, the numbers 
represent a complete set of residues modulo 
. Therefore, divides only if 
See Also
| 1977 USAMO (Problems • Resources) | ||
| Preceded by First Question |
Followed by Problem 2 | |
| 1 • 2 • 3 • 4 • 5 | ||
| All USAMO Problems and Solutions | ||
