Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "1977 USAMO Problems/Problem 1"

(→‎Solution)
(→‎Solution)
Line 5: Line 5:
 
== 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.  
+
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}, \cdots 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>
 
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>

Revision as of 18:13, 5 April 2013

Problem

Determine all pairs of positive integers $(m,n)$ 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 $f(x)$ and the second one to be $g(x)$. In order for $f(x)$ to be divisible by $g(x)$ they must have the same roots. The roots of $g(x)$ are the mth roots of unity, except for 1. When plugging into $f(x)$, the root of unity is a root of $f(x)$ if the terms $x^n, x^{2n}, x^{3n}, \cdots x^{mn}$ all represent a different mth root of unity.

Note that if $\\gcd(m,n)=1$, the numbers $n, 2n, 3n, \cdots, mn$ represent a complete set of residues modulo $m$. Therefore, $f(x)$ divides $g(x)$ only if $\boxed{\\gcd(m,n)=1}$ $\blacksquare$

See Also

1977 USAMO (Problems • Resources)
Preceded by
First Question 		Followed by
Problem 2
1 • 2 • 3 • 4 • 5
All USAMO Problems and Solutions
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1977_USAMO_Problems/Problem_1&oldid=52154"