# Polynomial Sprint: Useful Lemma

$\color{#D61F06} {\text{Unlocked!}}$

Mathematicians have a huge bag of tricks, which provide them with various ways of approaching a problem. In this note, we introduce an extremely useful lemma, which applies to polynomials with integer coefficients.

Lemma. If $f(x)$ is a polynomial with integer coefficients, then for any integers $a$ and $b$, we have $a-b \mid f(a) - f(b)$

1) Show that for any integers $a, b$ and $n$, we have

$a-b | a^n - b^n.$

2) Using the above, prove the lemma.

3) Come up with a (essentially) two-line solution to question 4 from the book.

Note: In Help Wanted, Krishna Ar mentioned that problem 4 from the book was hard to solve. If you looked at the solution, it was also hard to understand what exactly was happening. This provides us with a simple way of comprehending why there are no solutions.

4) Come up with an alternative solution to E6 (page 250, from the book) using this lemma.

5) * (Reid Barton) Suppose that $f(x)$ is a polynomial with integer coefficients. Let $n$ be an odd positive integer. Let $x_1, x_2, \ldots x_n$ be a sequence of integers such that

$x_2 = f(x_1), x_3 =f(x_2), \ldots x_n = f(x_{n-1}), x_1 = f(x_n) .$

Show that all the $x_i$ are equal.
Where did you use the fact that $n$ is an odd positive integer?

Note by Calvin Lin
5 years, 9 months ago

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

• Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
• Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
• Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. list
1. numbered
2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in $$ ... $$ or $ ... $ to ensure proper formatting.
2 \times 3 $2 \times 3$
2^{34} $2^{34}$
a_{i-1} $a_{i-1}$
\frac{2}{3} $\frac{2}{3}$
\sqrt{2} $\sqrt{2}$
\sum_{i=1}^3 $\sum_{i=1}^3$
\sin \theta $\sin \theta$
\boxed{123} $\boxed{123}$

Sort by:

I really like Polynomial Sprint. It would be nice if you can do some other themes using similar form.

- 5 years, 8 months ago

Yes, I entirely agree! I find these sets fun to do and I want more sets.

- 5 years, 8 months ago

This has been unlocked. Sorry for being late, I was out yesterday.

Staff - 5 years, 9 months ago

What does the $|$ mean?

- 5 years, 9 months ago

$a|b$ means $a$ divides $b$

- 5 years, 9 months ago

1) $a-b|a^n-b^n$, let $f(x)=x^n$, and plug in $a$ and $b$ into the function and we get $a-b|a^n-b^n$, is this correct?

- 5 years, 9 months ago

You have to show that it is true of all polynomials, not just specially chosen polynomials.

Staff - 5 years, 9 months ago

The lemma is true for polynomials with integer coefficients, so do you mean that I must show that this is true for non-integers too?

- 5 years, 9 months ago

I might have initially misinterpreted what you are trying to do.

The statement in question 1 is about integers (not polynomials), and you are asked to show that for any pair of integers, we have $a - b \mid a^n - b^n$. For example, $10 - 7 \mid 10^3 - 7^3$, or equivalently that $3 \mid 657$.

Note that you are not allowed to use the lemma, since we want to use question 1 to prove the lemma (in question 2).

Staff - 5 years, 9 months ago

Oh, ok

- 5 years, 9 months ago

5) We see that $x_n-x_{n+1}\mid f(x_n)-f(x_{n+1})=x_{n+1}-x_{n+2}$.

Thus we get the following divisibilitites:

$x_1-x_2\mid x_2-x_3\implies x_2-x_3=k_1(x_1-x_2)$

$x_2-x_3\mid x_3-x_4\implies x_3-x_4=k_2(x_2-x_3)$

$\vdots$

$x_{n-1}-x_n\mid x_n-x_1\implies x_n-x_1=k_{n-1}(x_{n-1}-x_n)$

$x_n-x_1\mid x_1-x_2\implies x_1-x_2=k_n(x_n-x_1)$

This means that $x_1-x_2=k_1k_2\cdots k_n(x_1-x_2)$

since $x_1\ne x_2$, we can divide both sides by $x_1-x_2$ to get $k_1k_2\cdots k_n=1$

Since we are working in the integers, this means that $|k_i|=1$ for all $i=1\to n$.

Thus, $x_k-x_{k+1}=\pm (x_{k-1}-x_k)$

What I got so far.

- 5 years, 9 months ago

If some $k_i=-1$, then we have $x_k=x_{k+1}$, which leads to equality of all $x_i$. If all k=1, then we can sum and get $x_1-x_2=0$, so $x_1=x_2$, which contradicts to your assumption that $x_1$ is different from $x_2$. Then that again leads to $x_1=x_2=...=x_n$

- 5 years, 9 months ago

Is it that simple? When did you use the condition that $n$ is odd?

- 5 years, 9 months ago

You just consider it modulo |x2 - x1| :

Let d equal |x1 – x2| and thus d = |x1 – x2| = |x2 – x3| = |x3 – x4| = … = |x{n-1} – x{n}| = |x{n} – x1|. If d is nonzero then x2 is congruent to (x1 + d) mod 2d. Similarly x3 is congruent to (x2 + d) mod 2d which is congruent to x1 mod 2d. In general x{k} is congruent to (x1 + d) mod 2d if k is even and congruent to x1 mod 2d if k is odd. Thus we have x{n} is congruent to x1 mod 2d because n is odd. However then |x{n} – x1| = 2dq for an integer q. Also d = |x{n} – x1|, hence d = 2dq and 1 = 2q. This contradicts the fact that q is an integer, hence our previous assumption that d is nonzero must be false. Therefore d = |x1 – x2| = |x2 – x3| = |x3 – x4| = … = |x{n-1} – x{n}| = |x{n} – x1| = 0 and x1 = x2 = x3 = …=x{n} and all the x{i} are equal.

- 5 years, 8 months ago

I do not immediately see how we get $k_k = 0 \Rightarrow x_k = x_{k+1}$ in the first scenario. I think we get $x_{k} = x_{k+2}$ instead, but that isn't immediately useful.

@Daniel Liu You are nearly there. Let me phrase the rest of the question in a different way. You start at some point $X$ on the real number line. You take $n$ odd steps of size exactly $S$. If you end back at $X$, show that $S = 0$.

Staff - 5 years, 9 months ago

We want another polynomial sprint! Soon..

- 5 years, 8 months ago

I guess We can write any polynomial a^n+b^n as (a-b)(a^n-1+a^n-2 b^1. .... Till b^n-1) therefore its always divisible by a-b

- 5 years, 9 months ago

Where can I get the book?

- 5 years, 9 months ago

- 5 years, 9 months ago

- 5 years, 9 months ago

1)a^n-b^n=(a-b)(a^(n-1)+a^(n-2) b+...+b^(n-1)) Which leads us to:a-b/a^n-b^n 2) let f be a polynomial f (x)=an.x^n+an-1.x^(n-1)+...+a0 We can apply question1 since it is true for any n For j {0, n}: a-b / a^j-b^j We can sum Leads us to:a-b/f (a)-f (b) 5) x1-x2 =k1 (xn-x1) x2-x3=k2 (x1-x2) . . . xn-1-xn=kn (xn-2 -xn-1) Leads us to ki=1 or =-1 If one ki=-1 We have xi are equals If all ki=1 (x1-x2)+(x2-x3)+...+(xn-1 -xn)=(xn-x1)+ (x1-x2)+...+(xn-2 - xn-1) Leads us to: x1-xn = xn- xn-1 If just xi#xi-1 We have contradiction: (xi-xi-1)=0=(xi-1 -xi-2)#0 We can make recurrence(recurrance in french) We leads to an a contradiction each time Then k#1 Then all xi are equals

- 5 years, 9 months ago

1. Let $f(t)=t^n-b^n$. Then $f(b)=b^n-b^n=0$, so $t-b\mid t^n-b^n$. Let $t=a$ to get $a-b\mid a^n-b^n$.
2. Consider the $k$th coefficient of $f(a)-f(b)$: $a_k(a^k-b^k)$. Since $a-b\mid a^k-b^k$, $a-b$ is a factor of every term in $f(a)-f(b)\implies a-b\mid f(a)-f(b)$.
For the rest, I don't know which book you're talking about.

- 5 years, 9 months ago

Problem Solving Strategies by Arthur Engel. They might be selling online I don't really know. XD

- 5 years, 9 months ago

Google "arthur engel problem solving strategies", and follow the first link, which should be a pdf. The url is below but you have to surround the italicized text with underscores:

- 5 years, 8 months ago

- 5 years, 8 months ago

Oh oops, never mind the url.

- 5 years, 8 months ago

Book? What book?

- 5 years, 9 months ago

Google "arthur engel problem solving strategies", and follow the first link, which should be a pdf. The url is below but you have to surround the italicized text with underscores: http://f3.tiera.ru/2/MMathematics/MSchSchool-level/Engel%20A.%20Problem-solving%20strategies%20(for%20math%20olympiads)(Springer,%201998)(ISBN%200387982191)(O)(415s)MSch.pdf

- 5 years, 8 months ago

Oh oops, never mind the url.

- 5 years, 8 months ago

Thanks.. will do that. :)

- 5 years, 8 months ago

You may refer to the original post Let's Get Started to understand the context of the Polynomial Sprint set.

Staff - 5 years, 9 months ago