×

# Polynomial Sprint: Useful Lemma

$$\color{red} {\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
2 years, 6 months ago

Sort by:

I really like Polynomial Sprint. It would be nice if you can do some other themes using similar form. · 2 years, 6 months ago

Yes, I entirely agree! I find these sets fun to do and I want more sets. · 2 years, 6 months ago

We want another polynomial sprint! Soon.. · 2 years, 6 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. · 2 years, 6 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$$ · 2 years, 6 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 · 2 years, 6 months ago

Is it that simple? When did you use the condition that $$n$$ is odd? · 2 years, 6 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. · 2 years, 6 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? · 2 years, 6 months ago

You have to show that it is true of all polynomials, not just specially chosen polynomials. Staff · 2 years, 6 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? · 2 years, 6 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 · 2 years, 6 months ago

Oh, ok · 2 years, 6 months ago

This has been unlocked. Sorry for being late, I was out yesterday. Staff · 2 years, 6 months ago

What does the $$|$$ mean? · 2 years, 6 months ago

$$a|b$$ means $$a$$ divides $$b$$ · 2 years, 6 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 · 2 years, 6 months ago

Where can I get the book? · 2 years, 6 months ago

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 · 2 years, 6 months ago

Remember to download it to your desktop for easier reference when without internet · 2 years, 6 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 · 2 years, 6 months ago

Book? What book? · 2 years, 6 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

it's for free. · 2 years, 6 months ago

Thanks.. will do that. :) · 2 years, 6 months ago

Oh oops, never mind the url. · 2 years, 6 months ago

You may refer to the original post Let's Get Started to understand the context of the Polynomial Sprint set. Staff · 2 years, 6 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. · 2 years, 6 months ago

Problem Solving Strategies by Arthur Engel. They might be selling online I don't really know. XD · 2 years, 6 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 · 2 years, 6 months ago

It's for free. · 2 years, 6 months ago