Take the 2-minute tour ×

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.

share|improve this question
"Diophantine" should just mean that the polynomial has integer coefficients. A root $r$ of a polynomial $p(x)$ is a number such that $p(r) = 0$. As for the third question, there are actually a couple of ways to do this but one is to use the rational root theorem (Google this). –  Qiaochu Yuan Mar 21 '12 at 19:53
That's exactly what I needed. If you want to make it an answer I'll +1 and accept even though it was pretty simple. –  brandon Mar 21 '12 at 19:55
Relevant: Hilbert's 10th problem –  user2468 Mar 21 '12 at 19:57
@J.D. Exactly what I'm working on, I should have known it was a classic problem. Thanks for the reference –  brandon Mar 21 '12 at 19:58
add comment

2 Answers

up vote 7 down vote accepted

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$.

share|improve this answer
So just so I understand, there is only one root of a given single variable polynomial and that's the value of x such that P(x) = 0? Also, as long as the algorithm eventually halts it's fine. Something like writing out Pi would not be computable by this definition because it's answer isn't expressible as a finite string and it never halts. –  brandon Mar 21 '12 at 20:14
@brandon: No, you can have more than one root. For example, if the polynomial is $(x-1)(x-2)=x^2-3x+2$ there are two roots, 1 and 2. –  Ross Millikan Mar 21 '12 at 20:18
@RossMillikan that makes a lot of sense. I also remember hearing that way before I started college. Thanks for answering, I tend to forget this basic stuff after a while. –  brandon Mar 21 '12 at 20:23
add comment

A Diophantine equation is one where the variables are required to take integer values. A root of a polynomial is a value of the variable(s) that gives the polynomial the value $0$.

share|improve this answer
add comment

Your Answer


