% This template was created by Stephen on 27th March 2000


% Set the document class
\documentclass[12pt,a4paper]{article}

% Resize the page, to save the forests.
\setlength{\topmargin}{-1cm} \setlength{\textheight}{24cm}
\setlength{\textwidth}{15cm} \setlength{\oddsidemargin}{0.5cm}
\setlength{\evensidemargin}{0.5cm}

% Just in case we want to do Black Board Bold letters.
%\input{amssymb.sty}
\usepackage{amssymb}

% So we can do multicolumns
\usepackage{multicol}
\setlength\columnseprule{0pt}   % no vertical lines inbetween columns
\setlength\multicolsep{0.5ex}     % space preceding a multicolumn

% A command to generate the header text
\newcommand{\myheader}
{\footnotesize December 2005}

% Change the headers and footers
\pagestyle{myheadings} \markboth{\myheader}{\myheader}

% New Commands to make numbered lists easier
\newcommand{\be}{\begin{enumerate}}
\newcommand{\ee}{\end{enumerate}}

% New Commands to make in-text displayed math easier
\newcommand{\bdm}{$ \displaystyle}
\newcommand{\edm}{$}

% New Commands to do handle the black board bold sets:
\newcommand{\R}{\mathbb{R}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\Q}{\mathbb{Q}}

% New command for conjugates, arguments, etc.
\def\conj#1{\overline{#1}}
\def\arg{\,\mbox{arg}\,}
\def\Arg{\,\mbox{Arg}\,}
\def\cis{\,\mbox{cis}\,}
\def\Cis#1{\cos {#1} + i \sin {#1}}
\def\Re{\, \mbox{Re}\,}
\def\Im{\, \mbox{Im}\,}
\def\cosec{\,\mbox{cosec}\,}
\def\deg{\,\mbox{deg}\,}

% New command for does not divide
\def\notdivide{\!\not|\,}

% New command for the heading
\newcommand{\WorksheetHeading}[1]{{\par\noindent \bf \Large #1}}

% New command to fix spelling
\newenvironment{centre}{\begin{center}}{\end{center}}

% New command for itemised titles
\def\it#1{\item{\bf #1.}}

%--------------------------------------------------------
% Let the document begin!
\begin{document}

\begin{centre}
  \bf \Large
 Polynomials (S)
\end{centre}

\subsection*{Theory}

\begin{enumerate}

\it{Definition} A polynomial is an expression of the form
$p(x)=a_nx^n+a_{n-1}x^{n-1}+\cdots+a_0$. $a_n\neq0$ unless $p(x)$
is the zero polynomial. The coefficients $a_i$ can be from
$\R,\C,\Z,\Q,\Z_n$ etc, if the coefficients are from $R$, we say
this is a polynomial (in $x$) over $R$. We call $a_n$ the leading
coefficient, say the \textit{degree} of $p(x)$ is $n$, and if
$a_n=1$, we call the polynomial \textit{monic}.

\it{Division Algorithm} For polynomials $f$, $g$, there exist
unique polynomials $q$, $r$ such that $f=qg+r$ and $\deg r<\deg g$
or $r=0$. ($p=p(x)$)

\it{Factor Theorem} Suppose that $p(a)=0.$ When this occurs we say
$a$ is a \textit{root} of $p(x)$. Then $p(x)=(x-a)q(x)$ for some
polynomial $q(x)$. If $p(x)=(x-a)^mq(x)$ for some $q(x)$ with
$q(a)\neq 0$, then we say $a$ is a root of multiplicity $m$. If
$f(x)\mid g(x)$ then all roots of $f$ are automatically roots of
$g$.

\it{Rational Root Theorem} If
$p(x)=a_nx^n+a_{n-1}x^{n-1}+\cdots+a_0$ is a polynomial with
integer coefficients and $p/q$ is a rational root written in
reduced form then $p|a_0$ and $q|a_n$.

\it{Vieta's Theorem} This gives the expressions for the
coefficients of a polynomial in terms of its roots, which you
should know.

\it{Lagrange Interpolation Formula} One of the most important
tools in polynomial problems is the fact that if two polynomials
of degree at most $n$ agree at $n+1$ (or an infinite) number of
places, then the polynomials are identical. This is equivalent to
the statement that a polynomial of degree $n$ can have at most $n$
roots. The Lagrange Interpolation Formula gives an explicit form
for the degree $n$ polynomial through $n+1$ predetermined points
$(a_0,b_0),(a_1,b_1),\ldots,(a_n,b_n)$.

\it{Fundamental Theorem of Algebra} Every nonconstant polynomial
with coefficients in $\C$ has a root (in $\C$).

\it{Corollory} A polynomial of degree $n$ over $\C$ has exactly
$n$ roots counted according to multiplicity.



\it{Irreducible Polynomials} A polynomial is said to be
\textit{irreducible}  if it cannot be factored into two
polynomials of smaller degree. Over $\Z$, $\Q$, $\R$, $\C$ and
$\Z_p$ where $p$ is a prime, every polynomial can be factored
uniquely into irreducibles up to a constant factor.



\it{Eisenstein's Criterion} Let
$f(x)=a_nx^n+a_{n-1}x^{n-1}+\cdots+a_0$ be a polynomial with
integer coefficients. Suppose that there exists a prime $p$ such
that

\begin{enumerate}
\item $p\notdivide a_n$

\item $p\mid\! a_i \ \mbox{ for }\  0\leq i<n$

\item $p^2\notdivide a_0$
\end{enumerate}

Then $f(x)$ is irreducible over $\Z[x]$ (and hence by Gauss' Lemma
below is also irreducible over $\Q[x]$).

\it{Gauss' Lemma} Let $f(x)$ be a polynomial with integer
coefficients. If we can factor $f(x)$ as $f(x)=g(x)h(x)$ over the
rationals, then we can factor $f(x)$ over the integers
$f(x)=g_1(x)h_1(x)$ where $g_1(x)$ and $h_1(x)$ are rational
multiples of $g(x)$ and $h(x)$.

\it{Descartes' Rule of Signs} The number of positive roots of a
real polynomial is at most the number of sign changes in the list
of coefficients of the polynomial, and is equal in parity to this
number. (To determine the number of negative roots, use $p(-x)$.)

\it{Minimal Polynomials} Suppose $\alpha$ is the root of a
polynomial over $R$ in an extension of $R$. Then there exists a
minimal polynomial for $\alpha$, $d(x)$ with the properties that
$d(\alpha)=0$ and if $p(x)$ is any polynomial for which
$p(\alpha)=0$, then $d(x)$ divides $p(x)$. $d(x)$ is necessarily
irreducible.

\end{enumerate}

\subsection*{Problems}

\begin{enumerate}

\item Show that $\cos^{-1}(\frac{4}{5})$ is an irrational multiple
of $\pi$.

\item (2000 AMO Q1) Find all polynomials $f$ with real
coefficients such that $$(x-27)f(3x)=27(x-1)f(x)$$ for every real
number $x$.

\item (1970 Canada) Let $P(x)$ be a polynomial with integral
coefficients. Suppose there exist four distinct integers $a,b,c$
and $d$ with $P(a)=P(b)=P(c)=P(d)=5$. Prove that there is no
integer $k$ with $P(k)=8$.

\item (1993 IMO Q1) Let $f(x)=x^n+5x^{n-1}+3$, where $n>1$ is an
integer. Prove that $f(x)$ cannot be expressed as a product of two
nonconstant polynomials with integer coefficients.

\item (1999 Canada) If $a$, $b$, $c$ are the roots of $x^3-x-1=0$,
compute $$\frac{1+a}{1-a}+\frac{1+b}{1-b}+\frac{1+c}{1-c}.$$

\item (1997 China) Let $0<a_0\leq a_1\leq\ldots\leq a_{n-1}\leq1$
be real numbers. Let $z$ be a complex root of the equation
$x^n+a_{n-1}x^{n-1}+\ldots+a_1 x+a_0=0$ such that $|z|\geq 1.$
Prove that $z^{n+1}=1.$

\item (1974 IMO Q6) Let $P(x)$ be a polynomial with integer
coefficients of degree $d>0$. Let $n$ be the number of distinct
integers $k$ such that $(P(k))^2=1$. Prove that $n\leq d+2.$

\item (1991 AUO) Let $a_1,a_2,\ldots,a_{100}$,
$b_1,b_2,\ldots,b_{100}$ be distinct real numbers. A table of
$100\times 100$ numbers is filled so that the number $a_i+b_j$ is
written down on the intersection of the $i$'th row with the $j$'th
column. Given, that in each column the product of all numbers is
equal to 1, prove that in each row the product of all numbers is
equal to $-1$.

\item (1999 Czech-Slovak) Find all natural numbers $k$ for which
the following assertion holds: If $F(x)$ is a polynomial with
integer coefficients which satisfies $0\leq F(c)\leq k$ for all
$c\in\{0,1,\ldots,k+1\}$ then $F(0)=F(1)=\cdots=F(k+1).$

\item (2002 IMO Q3) Find all pairs of integers $m,n\geq 3$ such
that there exist infinitely many positive integers $a$ for which
$$\frac{a^m+a-1}{a^n+a^2-1}$$ is an integer.

\item (2001 APMO Q4) A point in the plane with a cartesian
coordinate system is called a \textit{mixed point} if one of its
coordinates is rational and the other one is irrational. Find all
polynomials with real coefficients such that their graphs do not
contain any mixed point.

\item (1975 USAMO) Let $P(x)$ be a polynomial of degree $n$, so
that $P(k)=k/(k+1)$ for $k=0,1,\ldots n$. Find $P(n+1)$.

\item (1997 UKMO) Find the number of polynomials of degree 5 with
distinct coefficients from the set $\{1,2,\ldots,9\}$ that are
divisible by $x^2-x+1$.

\item Let $P(x)=a_0x^n+a_1x^{n-1}+\cdots+a_n$ be a nonzero
polynomial with integer coefficients such that $P(r)=P(s)=0$ for
some integers $r$ and $s$, with $0<r<s$. Prove that $a_k\leq -s$
for some $k$.

\item It is known of a polynomial over $\Z$ that $p(n)>n$ for
every positive integer $n$. Consider $x_1=1,x_2=p(x_1),\ldots$. We
know that, for any positive integer $N$, there exists a term of
the sequence divisible by $N$. Prove that $p(x)=x+1$.

\end{enumerate}


\end{document}
