Factoring integer polynomials by factoring their values then interpolating

Question

Let $f\in\mathbb Z[x]$ be a non-constant integer polynomial, and let $n$ be a positive integer which is at least $\deg f$. Choose positive integers $a_1<\cdots<a_n$ such that $f(a_i)\neq 0$ for each $i$. Then for every choice of divisors $d_1|f(a_1),\ldots, d_n|f(a_n)$ there is at most one polynomial $g\in\mathbb C[x]$ with $\deg g<\deg f$ such that $g(a_i)=d_i$ for $i=1,\ldots,n$. This generates only finitely many choices for the polynomials $g$. These are the only possible candidates for the irreducible factors of $f$.

My question: I understand that $g$ can be constructed using Interpolation polynomial formula with degree at most $n-1$, which guarantees uniqueness (when it exists). However, I am unsure about the second part. Any suggestion is appreciated. Thank you!

Answer 1

Suppose $h(x)\in\mathbb{Z}[x]$ is irreducible and divides $f(x)$. Then we can write $f(x) = h(x)q(x)$ for some $q(x)\in\mathbb{Z}[x]$. In particular, for any integer $a$, we have $f(a) = h(a)q(a)$. Thus, $h(a)\mid f(a)$ in $\mathbb{Z}$. That is:

If $g(x)$ divides $f(x)\in\mathbb{Z}[x]$, then $g(a)$ divides $f(a)$ in $\mathbb{Z}$ for every integer $a$.

(The converse does not hold: for example, $g(x)=2$ does not divide $f(x) = x^2+x$ in $\mathbb{Z}[x]$, but $g(a)=2$ always divides $a^2+a$ for any integer $a$.)

So pick $a_1\lt\cdots\lt a_n$. If $g(x)$ is an irreducible factor of $f(x)$, then $g(a_i)\mid f(a_i)$ for all $i$. For each $i$, there are only finitely many integers $d_{i1},\ldots,d_{im_i}$ that divides $f(a_i)$. Thus, there are only finitely many tuples $(e_1,\ldots,e_n)$ of integers such that $e_i\mid f(a_i)$ for $i=1,\ldots,n$. Each such tuple defines one and only one polynomial $g$ with $g(a_i)=e_i$. So there are only finitely many polynomials $g(x)\in\mathbb{Z}[x]$ with the property that $g(a_i)\mid f(a_i)$ for $i=1,\ldots,n$. If $f(x)$ has a proper irreducible factor, then it must be one of the $g(x)$ we just found, because that factor satisfies that its value at $a_i$ divides $f(a_i)$ for $i=1,\ldots,n$, and the only polynomials that have that property and have degree at most $n-1$ are the $g(x)$.