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

No vote yet

1 vote

×

Problem Loading...

Note Loading...

Set Loading...

## Comments

Sort by:

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

Log in to reply

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

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.

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

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

oddsteps of size exactly \(S\). If you end back at \(X\), show that \( S = 0 \).Log in to reply

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.

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?

Log in to reply

You have to show that it is true of

allpolynomials, not just specially chosen polynomials.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?

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

Log in to reply

Log in to reply

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

Log in to reply

What does the \( | \) mean?

Log in to reply

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

Log in to reply

Where can I get the book?

Log in to reply

http://f3.tiera.ru/2/M

Mathematics/MSchSchool-level/Engel%20A.%20Problem-solving%20strategies%20(for%20math%20olympiads)(Springer,%201998)(ISBN%200387982191)(O)(415s)MSch.pdfLog in to reply

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

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

Log in to reply

Book? What book?

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.

Log in to reply

Thanks.. will do that. :)

Log in to reply

Oh oops, never mind the url.

Log in to reply

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

Log in to reply

Log in to reply

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

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

Log in to reply

Log in to reply

Log in to reply