\( \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?

## Comments

Sort by:

TopNewestI really like Polynomial Sprint. It would be nice if you can do some other themes using similar form. – Bogdan Kejžar · 2 years, 6 months ago

Log in to reply

– Colin Tang · 2 years, 6 months ago

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

We want another polynomial sprint! Soon.. – Sagnik Saha · 2 years, 6 months ago

Log in to reply

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

Log in to reply

– Bogdan Simeonov · 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\)Log in to reply

@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\)

oddsteps of size exactly \(S\). If you end back at \(X\), show that \( S = 0 \). – Calvin Lin Staff · 2 years, 6 months agoLog in to reply

– Daniel Liu · 2 years, 6 months ago

Is it that simple? When did you use the condition that \(n\) is odd?Log in to reply

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

Log in to reply

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? – Daniel Lim · 2 years, 6 months ago

Log in to reply

allpolynomials, not just specially chosen polynomials. – Calvin Lin Staff · 2 years, 6 months agoLog in to reply

– Daniel Lim · 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?Log in to reply

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

Log in to reply

– Daniel Lim · 2 years, 6 months ago

Oh, okLog in to reply

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

Log in to reply

– Milly Choochoo · 2 years, 6 months ago

What does the \( | \) mean?Log in to reply

– Daniel Lim · 2 years, 6 months ago

\(a|b\) means \(a\) divides \(b\)Log in to reply

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

Log in to reply

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

Log in to reply

Mathematics/MSchSchool-level/Engel%20A.%20Problem-solving%20strategies%20(for%20math%20olympiads)(Springer,%201998)(ISBN%200387982191)(O)(415s)MSch.pdf – Benjamin Wong · 2 years, 6 months agoLog in to reply

– Benjamin Wong · 2 years, 6 months ago

Remember to download it to your desktop for easier reference when without internetLog in to reply

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

Log in to reply

Book? What book? – Snehal Shekatkar · 2 years, 6 months ago

Log in to reply

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

Log in to reply

– Snehal Shekatkar · 2 years, 6 months ago

Thanks.. will do that. :)Log in to reply

– Colin Tang · 2 years, 6 months ago

Oh oops, never mind the url.Log in to reply

Let's Get Started to understand the context of the Polynomial Sprint set. – Calvin Lin Staff · 2 years, 6 months ago

You may refer to the original postLog in to reply

Log in to reply

– Samuraiwarm Tsunayoshi · 2 years, 6 months ago

Problem Solving Strategies by Arthur Engel. They might be selling online I don't really know. XDLog in to reply

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

Log in to reply

– Colin Tang · 2 years, 6 months ago

It's for free.Log in to reply

– Colin Tang · 2 years, 6 months ago

Oh oops, never mind the url.Log in to reply