The polynomials \(x^2 + 2\) and \(x^2+x-1\) are written on a board. If the polynomials \(f(x)\) and \(g(x)\) are already on the board (\(f(x)\) may equal to \(g(x)\)) we are allowed to add any of \(f(x) g(x), f(x) -g(x)\) or \(f(x) + g(x)\) to the board.

(a) Can the polynomial \(x\) ever be made to appear on the board?

(b) Can the polynomial \(4x-1\) ever be made to appear on the board?

Give proof.

- \(f(x)\) and \(g(x)\) can represent any two polynomials on the board

## Comments

Sort by:

TopNewest(a) Suppose \(a, b\) are integers. If \(f(a), g(a)\) are divisible by \(b\), then \(f(a)+g(a), f(a)-g(a), f(a)g(a)\) are all divisible by \(b\) as well. Thus the property "divisible by \(b\) at \(x = a\)" is an invariant; they will hold for all polynomials generated.* At \(x = 3\), \(f(x) = g(x) = 11\) and thus both of them are divisible by \(11\), so all polynomials generated will be divisible by \(11\) on \(x=3\). But \(x\) doesn't satisfy this (since it gives \(3\) on \(x=3\)). So it cannot appear.

(*) We can use induction to formalize this, inducting on the number of operations required to generate a polynomial. The base case is \(f, g\) that takes zero steps; the induction step lies on the fact that if a polynomial \(p\) can be generated (in the shortest way) from either of \(f+g, f-g, fg\), then \(f,g\) must be generated before \(p\), so we can use induction there.

(b) It can appear. Let \(F_1(x) = x^2 + 2, F_2(x) = x^2 + x - 1\). Then,

Log in to reply

Can we classify the set of polynomials which can be reached through these operations?

Hint:Bezout's Identity. – Calvin Lin Staff · 1 year, 7 months agoLog in to reply

Nice question :)

Hint:Find an Invariant.Hint:Evaluate the polynomial functions at a particular point. – Calvin Lin Staff · 1 year, 7 months agoLog in to reply

I don't really get your problem. What are g(x) and f(x)? Are g(x) and f(x) equal to \(x^{2}+1\) and/or \(x^{2} +x-1\) – Julian Poon · 1 year, 7 months ago

Log in to reply

– Sharky Kesa · 1 year, 7 months ago

\(f(x)\) and \(g(x)\) are any two polynomials on the board.Log in to reply

– Jake Lai · 1 year, 7 months ago

It's any \(f(x), g(x)\) that is written on the board.Log in to reply

– Lakshya Sinha · 1 year, 7 months ago

I think f(x) and g(x) some other polynomial functionLog in to reply