I'm doing some homework for a computer science class. It's been so long since I've done math, I have a question that assumes math knowledge that confuses me.
Given:
Whether a diophantine polynomial in a single variable has integer roots.
With the given question I need to determine if that question is solvable using computers. I know how to do that, but I don't the math required to answer this question.
So I understand "Whether a …. polynomial in a single variable has integer …?"
My question:
- What does diophantine mean
- What is an integer root
- How do you determine if a diophantine polynomial in a single variable has integer roots?
The math behind this question is assumed to be known, once I know the answers to those three questions (really just the last one) I can answer my homework.
Note: it may or may not be obvious that this is computable, since I don't know enough about the math to say, I will say a lot of things that seem computable are not unless their input and output are acceptable to a finite precision.
Best Answer
There are various definitions of Diophantine equation, not all equivalent. But one standard definition goes as follows. Let $P(x_1,x_2,\dots,x_k)$ be a polynomial with integer coefficients. A solution of the Diophantine equation $P(x_1,x_2,\dots,x_k)=0$ is a $k$-tuple $(x_1,x_2,\dots,x_k)$ of integers that satisfies the equation. An equation is Diophantine partly because of its shape, but much more because of the kinds of solutions we are looking for.
General Diophantine equations can be exceedingly difficult. However, in principle one variable equation are simple. We have a polynomial $P(x)$ with integer coefficients. Let $$P(x)=a_0x^n+a_1x^{n-1}+a_2x^{n-2}+\cdots +a_n.$$ Without loss of generality we may assume that the constant term $a_n$ is not equal to $0$. It is straightforward to show that any integer solution of the equation $P(x)=0$ must divide the constant term $a_n$.
So there is a simple (in principle!) algorithm for finding all the integer solutions of $P(x)=0$:
(i) Find all the divisors (positive and negative) of the constant term and then
(ii) Find out, by substitution, which ones of these divisors "work."
As you know, factorization of large numbers can be computationally difficult. However, there certainly is an algorithm for factoring.
Remark: There is a very famous related problem, called Hilbert's 10th Problem. Hilbert asked for a general algorithm that would, for any polynomial $P$ with integer coefficients, and possibly many variables, determine whether the equation $P=0$ has integer solutions. After earlier progress by a number of people, Matijasevich showed that there is no general algorithm of the type that Hilbert asked for. But as we noted in our answer to your question, there certainly is an algorithm that works for polynomials in one variable.
Diophantus himself in his Arithmetica looked mainly for rational solutions. Often, a problem is called Diophantine if we are interested in solutions that are somehow fairly closely related to the integers.
Note that (at least to people in Logic) the famous Fermat equation $x^n+y^n=z^n$ is not a Diophantine equation, since the exponents are also variable. Such equations are sometimes called exponential Diophantine, or, more casually, Diophantine.
A simple example: Consider the equation $3x^4-12x^3-x^2+4x=0$. We want to find all integer solutions of this equation. First rewrite our equation as $x(3x^3-12x^2-x+4)=0$. This has the obvious solution $x=0$. Any other solutions must be solutions of the equation $$3x^3-12x^2-x+4=0.$$ By the result mentioned in the main post, any integer solution of this equation must divide the constant term $4$. The divisors of $4$ are $\pm 1$, $\pm 2$, and $\pm 4$. Substitute these values in turn for $x$. We find that $x=4$ is a root, but none of the others are. So we have found all the integer solutions of our original equation: they are $x=0$ and $x=4$.