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?

Markdown

Appears as

*italics* or _italics_

italics

**bold** or __bold__

bold


- bulleted
- list

bulleted
list


1. numbered
2. list

numbered
list

Note: you must add a full line of space before and after lists for them to show up correctly

paragraph 1

paragraph 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"

Math

Appears 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}

Easy Math Editor

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.
Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

Markdown	Appears as
`italics` or `_italics_`	italics
`bold` or `__bold__`	bold
- bulleted - list	bulleted list
1. numbered 2. list	numbered list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1 paragraph 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"

Math	Appears 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}$

Comments

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

Bogdan Kejžar - 6 years, 10 months ago

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

Colin Tang - 6 years, 10 months ago

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

Calvin Lin Staff - 6 years, 11 months ago

What does the $|$ mean?

Milly Choochoo - 6 years, 11 months ago

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

Daniel Lim - 6 years, 11 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?

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

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?

@Daniel Lim – 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).

@Calvin Lin – Oh, ok

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.

Daniel Liu - 6 years, 11 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$

Bogdan Simeonov - 6 years, 11 months ago

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

@Daniel Liu – 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.

Colin Tang - 6 years, 11 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$ .

We want another polynomial sprint! Soon..

Sagnik Saha - 6 years, 11 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

Chaitya Shah - 6 years, 11 months ago

Where can I get the book?

Sanchit Ahuja - 6 years, 11 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

Benjamin Wong - 6 years, 11 months ago

Remember to download it to your desktop for easier reference when without internet

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

mido asry - 6 years, 11 months ago

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$ .
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.

Cody Johnson - 6 years, 11 months ago

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

Samuraiwarm Tsunayoshi - 6 years, 11 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:

@Colin Tang – It's for free.

@Colin Tang – Oh oops, never mind the url.

Book? What book?

Snehal Shekatkar - 6 years, 11 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.

Oh oops, never mind the url.

Thanks.. will do that. :)

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

Math	Appears 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}$