Waste less time on Facebook — follow Brilliant.
×

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
3 years, 3 months ago

No vote yet
1 vote

Comments

Sort by:

Top Newest

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

Bogdan Kejžar - 3 years, 3 months ago

Log in to reply

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

Colin Tang - 3 years, 3 months ago

Log in to reply

We want another polynomial sprint! Soon..

Sagnik Saha - 3 years, 3 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 - 3 years, 3 months ago

Log in to reply

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 - 3 years, 3 months ago

Log in to reply

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

Calvin Lin Staff - 3 years, 3 months ago

Log in to reply

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

Daniel Liu - 3 years, 3 months ago

Log in to reply

@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 - 3 years, 3 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 - 3 years, 3 months ago

Log in to reply

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

Calvin Lin Staff - 3 years, 3 months ago

Log in to reply

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 - 3 years, 3 months ago

Log in to reply

@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 Staff - 3 years, 3 months ago

Log in to reply

@Calvin Lin Oh, ok

Daniel Lim - 3 years, 3 months ago

Log in to reply

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

Calvin Lin Staff - 3 years, 3 months ago

Log in to reply

What does the \( | \) mean?

Milly Choochoo - 3 years, 3 months ago

Log in to reply

\(a|b\) means \(a\) divides \(b\)

Daniel Lim - 3 years, 3 months ago

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 - 3 years, 3 months ago

Log in to reply

Where can I get the book?

Sanchit Ahuja - 3 years, 3 months ago

Log 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

Benjamin Wong - 3 years, 3 months ago

Log in to reply

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

Benjamin Wong - 3 years, 3 months ago

Log 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 - 3 years, 3 months ago

Log in to reply

Book? What book?

Snehal Shekatkar - 3 years, 3 months ago

Log in to reply

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.

Colin Tang - 3 years, 3 months ago

Log in to reply

Thanks.. will do that. :)

Snehal Shekatkar - 3 years, 3 months ago

Log in to reply

Oh oops, never mind the url.

Colin Tang - 3 years, 3 months ago

Log in to reply

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

Calvin Lin Staff - 3 years, 3 months ago

Log in to reply

  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.

Cody Johnson - 3 years, 3 months ago

Log in to reply

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

Samuraiwarm Tsunayoshi - 3 years, 3 months ago

Log in to reply

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

Colin Tang - 3 years, 3 months ago

Log in to reply

@Colin Tang It's for free.

Colin Tang - 3 years, 3 months ago

Log in to reply

@Colin Tang Oh oops, never mind the url.

Colin Tang - 3 years, 3 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...