# Neat problems using roots of polynomials

On a recent test in a course I'm TAing, students were asked to prove that sin(x) is not a rational function by using the fact that polynomials only have finitely many zeroes. During my tutorial, I'd like to show them some other interesting problem whose (reasonably short!) solution uses the fact that polynomials only have finitely many zeroes. What's your favourite?

-
I should specify that the students are first year students, but it's a fairly advanced course, so they are generally bright but don't know much college math other than calculus and linear algebra. –  A Stewart Feb 15 '12 at 18:47

I know a proof of the fact that given two square $n \times n$ real matrices $A$ and $B$, then $AB$ and $BA$ have the same characteristic polynomial. This is very easy if $A$ or $B$ is invertible because $$\det (AB+\lambda I)=\det(A)\det(B+ \lambda A^{-1})=\det(BA+\lambda I)$$

Now, for fixed $\lambda$ denote: $$g(\mu)=\det((A+\mu I)B+\lambda I)$$ and $$h(\mu)=\det(B(A+\mu I)+\lambda I)$$ Then $g,h$ are polynomials in $\mu$. Moreover, given the initial remark and the fact that $A+\mu I$ is invertible for all but finitely many $\mu$, it follos that $$g(\mu)-h(\mu)=0$$ for all but finitely many $\mu$. But since a polynomial which has more roots than its degree is zero, it follows that $g=h$ and in particular, for $\mu=0$ it follows that

$$\det(AB+\lambda I)=\det(BA+\lambda I)$$

-

A nice application that deserves to be better known: if a polynomial $\:f(x)\:$ over $\:\mathbb Z/n\:$ has more roots than its degree, then we can quickly compute a nontrivial factor of $\:n\:$ via a simple $\rm\:gcd\:$ calculation.

The quadratic case of this is at the heart of many integer factorization algorithms, which attempt to factor $\:n\:$ by searching for a nontrivial square root in $\rm\: \mathbb Z/n\:,\:$ e.g. a square root of $1$ that is not $\:\pm 1$.

-