TITLE: Prove Expression cannot be factored
QUESTION [0 upvotes]: I am currently working on primes which can be expressed in form of a polynomial. For eg,

Find all primes which can be expressed in form $n^4-52n^2+595$

It is very essential to tell whether a polynomial can be factored or not. The polynomial above is very easy to factor but for some polynomials, it's extremely hard to tell.
Is there any way to prove whether a polynomial can be factored or not?

REPLY [2 votes]: There are various advanced techniques to factor polynomials over the rationals or over the integers. See Wikipedia.
There is also a simple, well-known way to find if a polynomial of the form
$$
f(x)=a_n x^n+a_{n-1}x^{n-1}+\cdots+a_1x+a_0
$$
and integer coefficients $a_0,\dots,a_n$ has linear factors over the rationals.
Indeed, if $x = p/q$ is a reduced solution of the equation $f(x)=0$, and equivalently $qx-p$ or $x-p/q$ is a factor of $f(x)$, then $p$ must be a (signed) divisor of $a_0$ and $q$ must be a divisor of $a_n$. 
If $a_n=1$, then this means the only linear factors of $f(x)$ over the rationals, if they exist, are of the form $x+t$ where $t$ is a divisor of $a_0$. 
For example, in your case the divisors of 595 are 
$$
\{{\pm1, \pm5, \pm7, \pm17, \pm35, \pm85, \pm119, \pm595}\}
$$
thus if one of these values, say $t$, nullifies $t^4-52t^2+595$ then $x-t$ is a factor. If none of these values nullify $x^4-52x^2+595$, then you are sure there are no linear factors.
You can also check the Eisenstein's criterion.
{"set_name": "stack_exchange", "score": 0, "question_id": 1652916}