Mysterious 100 degree Monic Polynomials

$f(x) | g(x)^2 - x \Rightarrow f(x) | f(x)^2 + g(x)^2 - x$ $g(x) | f(x)^2 - x \Rightarrow g(x) | f(x)^2 + g(x)^2 - x$

Since f,g coprime, we have $fg | f^2 + g^2 - x$ . So $f(x)^2 + g(x)^2 - x = a(x)f(x)g(x)$ for some function a(x).

If degree g is at least 1 and degree f = degree g, then degree if LHS = 2 deg(f) and degree of RHS = deg(a) + deg(f) + deg(g) = deg(a) + 2 deg(f). So degree of a(x)=0 and $f(x)^2 + g(x)^2 - x = af(x)g(x)$ for some constant a. Since f(x) and g(x) are both monic, then the coefficient of the highest power is 2 for LHS, and a for RHS. Therefore a=2. Rearranging the equation, we get $[f(x)-g(x)]^2 = x$ which is not possible.

Therefore, both degrees of f and g are different.

Now when we let degree of f $>$ degree of g $\geq$ 1, we have the following:

$f(x) | g(x)^2 - x \Rightarrow g(x)^2 - x = h(x)f(x) \Rightarrow h(x) | g(x)^2 -x (*)$ for some function h(x).

$g(x) | f(x)^2 - x \Rightarrow g(x) | h(x)^2f(x)^2 - xh(x)^2$

$\Rightarrow g(x) | (g(x)^2 - x)^2 - xh(x)^2$

$\Rightarrow g(x) | g(x)^4 - 2g(x)^2x + x^2 - xh(x)^2$

$\Rightarrow g(x) | x^2 - xh(x)^2$ (since $g(x) | g(x)^4 - 2g(x)^2x$ )

$\Rightarrow g(x) | x (x-h(x)^2)$

$\Rightarrow g(x) | (h(x)^2-x)x$

We note that since $g(x) | f(x)^2 - x$ , $f(x)^2 = g(x)b(x) + x$ for some b(x). This means that if x is a root of g(x), then x is also a root of f(x). But we know this is not possible since f(x) and g(x) are coprime. Thus, $g(x) | h(x)^2-x (**)$ . From $(*), (**)$ , we can conclude that $f(x) | g(x)^2 - x, g(x) | f(x)^2 - x \Rightarrow h(x) | g(x)^2 -x, g(x) | h(x)^2-x$ . From $g(x)^2 - x = h(x)f(x)$ , we note that the LHS and thus RHS are monic polynomials, and thus h(x) is monic. Also, if (x-t) is a common root of g(x) and h(x), $g(t)^2 - t = h(t)f(t) \Rightarrow 0-t=0 \Rightarrow t=0$ . But this means x is a root of g(x), and we proved earlier otherwise. Hence, we know that g(x) and h(x) in this case are also monic and coprime. Also from $g(x)^2 - x = h(x)f(x)$ , we know that 2 deg (g) = deg (f) + deg (h). Since degree of f $>$ degree of g, then degree of g $>$ degree of h.

This means that for every pair of functions (f,g) such that deg(f) $>$ deg(g), we can "jump down" and find exactly one pair (g,h) such that deg(g) $>$ deg(h). Conversely, for every pair (g,h), we can "jump up" and find exactly one pair (f,g), since $g(x)^2 - x = h(x)f(x) \Rightarrow f(x) = \frac{g(x)^2 - x}{h(x)}$ . Now we consider all functions (g,h), such that g is of degree 1 and thus h is of degree 0. The only possible h(x) = 1 since h(x) is monic. We know $g(x) | h(x)^2 - x = 1 - x$ , so $g(x) = x-1$ . Therefore, there is only 1 such pair of (g,h) with degree 1 and 0 respectively. Also since 2 deg (g) = deg (f) + deg (h), we have deg (f) - deg (g) = deg (g) - deg (h). Since deg (g) - deg (h) = 1, we can conclude that any pair of such functions will have difference of degree 1. So we conclude that there is exactly a pair of functions (f,g) with degree n and n-1 that fits the criteria. We call the specific function of degree n $f_n(x)$ .

Now, we consider $f_n(4)$ . We want to prove by induction that $f_n(4) = 2n+1$ for all non-negative integers n. It is true that $f_0(4)=1$ . Also we know that $g(x)^2 - x = h(x)f(x)$ so we can rewrite them as $f_k(x)^2 - x = f_{k-1}(x)f_{k+1}(x)$ . So we get $f_k(4)^2 - x = f_{k-1}(4)f_{k+1}(4)$ , and if $f_n(4) = 2n+1$ for all integers from 0 to k, we get $(2k+1)^2 - 4 = (2k-1)f_{k+1}(4)$ . Therefore, $f_{k+1}(4) = 2k+3 = 2(k+1) + 1$ , and thus $f_n(4) = 2n+1$ holds true for k+1. Therefore by mathematical induction, $f_n(4) = 2n+1$ for all non-negative integers n.

Now we can say that $f_{100}(4) = 200 + 1 = 201$ .