Counting Integer Roots of a Polynomial Using Sturm Sequences

[Klaus_Hoffmann]

Hi,.. using a Sturm or other sequence, could we find how many integer roots have the Polynomial

K(x)= \sum_{n=0}^{d} a_{n}x^{n}

where all the 'a_n' are integers (either positive or negative)

 

[mathman]

Sturm sequence will tell you the number of REAL roots greater than a preassigned number. However, it does not specifically single out integers.

With some effort you could used it by counting roots > n-e and roots >n+e (where e is small). If the difference is 1, then n (or something close to it) is a root.

 

[HallsofIvy]

This may not be what you are looking for but you can start with the rational root theorem: All rational roots have numerators that evenly divide a₀ and denominators that evenly divide a_d. Integer roots are rational roots with denominators equal to 1 so all possible integer roots must divide a₀. Once you have determined all possible integer roots you will have to try them in the equation to see if they really are roots.

 

[Gib Z]

This may not be what you are looking for but you can start with the rational root theorem: All rational roots have numerators that evenly divide a₀ and denominators that evenly divide a_d. Integer roots are rational roots with denominators equal to 1 so all possible integer roots must divide a[0]. Once you have determined all possible integer roots you will have to try them in the equation to see if they really are roots.

That sounds like that is what Klaus is exactly looking for
I've read this thread before..why didn't I think of that >.<..

 

[HallsofIvy]

I thought it was a little too simple- and it doesn't determine the number of integer roots, it helps you determine those roots so you can then count them!