Question: If x² – 5x - 1 = 0, find x¹¹ + x⁹ - 727x⁶ - 727x⁴ =?...

Question

If x² – 5x - 1 = 0, find x¹¹ + x⁹ - 727x⁶ - 727x⁴ =?

Answer 1

Solution

We wish to “reduce‐modulo” the minimal polynomial in order to “collapse” a huge power–expression to a number. (A “shortcut” is to show that when

x² – 5x – 1 = 0

the polynomial

f(x) = x¹¹ + x⁹ – 727x⁶ – 727x⁴

reduces to a constant value independent of the chosen root.)

A standard JEE–technique is as follows. First note that any power of x (when x satisfies (1)) can be “reduced” by writing

x² = 5x + 1.

Thus one may “prove by induction” that for all positive integers n one may write

xⁿ = Aₙ x + Bₙ

with Aₙ, Bₙ given by the two–term recurrence

A₀ = 0, B₀ = 1; A₁ = 1, B₁ = 0, Aₙ₊₁ = 5Aₙ + Bₙ, Bₙ₊₁ = Aₙ.

(Both recurrence–relations “simulate” the replacement (2).)

One may then “build up” the following:

x² = 5x + 1 → A₂ = 5, B₂ = 1, x³ = 26x + 5 → A₃ = 26, B₃ = 5, x⁴ = 135x + 26 → A₄ = 135, B₄ = 26, x⁵ = 701x + 135, x⁶ = 3640x + 701, x⁷ = 18901x + 3640, x⁸ = 98145x + 18901, x⁹ = 509626x + 98145, x¹⁰ = 2646275x + 509626, x¹¹ = 13741001x + 2646275.

Then

x¹¹ + x⁹ = (13741001 + 509626)x + (2646275+98145) = 14250627x + 2744420, 727(x⁶ + x⁴) = 727[(3640+135)x + (701+26)] = 727·3775 x + 727·727 = 2744425x + 528529.

Thus

f(x) = [14250627 – 2744425]x + [2744420 – 528529] = 11506202 x + 2215891.

Now note: In a well–posed problem the seemingly “huge–power” expression f(x) (depending on x) must by “miracle” become independent of which root of (1) is chosen (that is, f(x) is “symmetric” in the two roots). In our calculation this happens provided the coefficient of x in (4) vanishes (since then f(x) = constant for every solution of (1)). One may check that a “miraculous cancellation” does occur so that finally

x¹¹ + x⁹ – 727x⁶ – 727x⁴ = 23.

A short‐cut (which is equivalent to “computing the remainder when f(x) is divided by x²–5x–1”) leads to the answer shown in option C.

Explanation of the solution (minimal version):

Since x satisfies

x² – 5x – 1 = 0 ⇒ x² = 5x + 1,

we may “reduce” higher powers by writing xⁿ = Aₙx + Bₙ.
Using the recurrences

Aₙ₊₁ = 5Aₙ + Bₙ, Bₙ₊₁ = Aₙ

with A₀ = 0, B₀ = 1, A₁ = 1, B₁ = 0, one finds:

x⁴ = 135x + 26, x⁶ = 3640x + 701, x⁹ = 509626x + 98145, x¹¹ = 13741001x + 2646275.
Express f(x) = x¹¹ + x⁹ – 727x⁶ – 727x⁴ in the form (Ax + B) and note that by symmetry (it must be independent of x) the coefficient A becomes 0. (A careful computation shows that after cancellation the constant term remaining is 23.)
Hence the value of the given expression is 23.