Polynomial Sprint: Useful Lemma

Unlocked! \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)f(x) is a polynomial with integer coefficients, then for any integers a a and bb, we have abf(a)f(b) a-b \mid f(a) - f(b)

1) Show that for any integers a,ba, b and nn, we have

abanbn. 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) f(x) is a polynomial with integer coefficients. Let nn be an odd positive integer. Let x1,x2,xn x_1, x_2, \ldots x_n be a sequence of integers such that

x2=f(x1),x3=f(x2),xn=f(xn1),x1=f(xn). 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 xix_i are equal.
Where did you use the fact that nn is an odd positive integer?

Note by Calvin Lin
5 years, 1 month ago

No vote yet
1 vote

</code>...<code></code> ... <code>.">   Easy Math Editor

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. 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 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"
MathAppears as
Remember to wrap math in </span>...<span></span> ... <span> or </span>...<span></span> ... <span> to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}

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 - 5 years, 1 month ago

Log in to reply

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

Colin Tang - 5 years, 1 month ago

Log in to reply

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

Calvin Lin Staff - 5 years, 1 month ago

Log in to reply

What does the | mean?

Milly Choochoo - 5 years, 1 month ago

Log in to reply

aba|b means aa divides bb

Daniel Lim - 5 years, 1 month ago

Log in to reply

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

Daniel Lim - 5 years, 1 month ago

Log in to reply

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

Calvin Lin Staff - 5 years, 1 month 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 - 5 years, 1 month 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 abanbn a - b \mid a^n - b^n . For example, 10710373 10 - 7 \mid 10^3 - 7^3 , or equivalently that 3657 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 - 5 years, 1 month ago

Log in to reply

@Calvin Lin Oh, ok

Daniel Lim - 5 years, 1 month ago

Log in to reply

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

Thus we get the following divisibilitites:

x1x2x2x3    x2x3=k1(x1x2)x_1-x_2\mid x_2-x_3\implies x_2-x_3=k_1(x_1-x_2)

x2x3x3x4    x3x4=k2(x2x3)x_2-x_3\mid x_3-x_4\implies x_3-x_4=k_2(x_2-x_3)

\vdots

xn1xnxnx1    xnx1=kn1(xn1xn)x_{n-1}-x_n\mid x_n-x_1\implies x_n-x_1=k_{n-1}(x_{n-1}-x_n)

xnx1x1x2    x1x2=kn(xnx1)x_n-x_1\mid x_1-x_2\implies x_1-x_2=k_n(x_n-x_1)

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

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

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

Thus, xkxk+1=±(xk1xk)x_k-x_{k+1}=\pm (x_{k-1}-x_k)

What I got so far.

Daniel Liu - 5 years, 1 month ago

Log in to reply

If some ki=1k_i=-1, then we have xk=xk+1x_k=x_{k+1}, which leads to equality of all xix_i. If all k=1, then we can sum and get x1x2=0x_1-x_2=0, so x1=x2x_1=x_2, which contradicts to your assumption that x1x_1 is different from x2x_2. Then that again leads to x1=x2=...=xnx_1=x_2=...=x_n

Bogdan Simeonov - 5 years, 1 month ago

Log in to reply

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

Daniel Liu - 5 years, 1 month 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 - 5 years, 1 month ago

Log in to reply

I do not immediately see how we get kk=0xk=xk+1k_k = 0 \Rightarrow x_k = x_{k+1} in the first scenario. I think we get xk=xk+2 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 X on the real number line. You take nn odd steps of size exactly SS. If you end back at XX, show that S=0 S = 0 .

Calvin Lin Staff - 5 years, 1 month ago

Log in to reply

We want another polynomial sprint! Soon..

Sagnik Saha - 5 years, 1 month 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 - 5 years, 1 month ago

Log in to reply

Where can I get the book?

Sanchit Ahuja - 5 years, 1 month 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 - 5 years, 1 month ago

Log in to reply

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

Benjamin Wong - 5 years, 1 month 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 - 5 years, 1 month ago

Log in to reply

  1. Let f(t)=tnbnf(t)=t^n-b^n. Then f(b)=bnbn=0f(b)=b^n-b^n=0, so tbtnbnt-b\mid t^n-b^n. Let t=at=a to get abanbna-b\mid a^n-b^n.
  2. Consider the kkth coefficient of f(a)f(b)f(a)-f(b): ak(akbk)a_k(a^k-b^k). Since abakbka-b\mid a^k-b^k, aba-b is a factor of every term in f(a)f(b)    abf(a)f(b)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 - 5 years, 1 month ago

Log in to reply

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

Samuraiwarm Tsunayoshi - 5 years, 1 month 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 - 5 years, 1 month ago

Log in to reply

@Colin Tang It's for free.

Colin Tang - 5 years, 1 month ago

Log in to reply

@Colin Tang Oh oops, never mind the url.

Colin Tang - 5 years, 1 month ago

Log in to reply

Book? What book?

Snehal Shekatkar - 5 years, 1 month 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 - 5 years, 1 month ago

Log in to reply

Oh oops, never mind the url.

Colin Tang - 5 years, 1 month ago

Log in to reply

Thanks.. will do that. :)

Snehal Shekatkar - 5 years, 1 month 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 - 5 years, 1 month ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...