Polynomial arithmetic

Polynomial arithmetic is a branch of algebra dealing with some arithmetic properties of polynomials which share strong analogies with similar properties of integers. It includes basic mathematical operations such as addition, subtraction, and multiplication, as well as more elaborate operations like Euclidean division, and properties related to roots of polynomials. The latter are essentially connected to the fact that the set K[X] of univariate polynomials with coefficients in a field K and the ring of integers ${\displaystyle \mathbb {Z} }$ are not only both commutative rings, but also both Euclidean domains.

Elementary operations on polynomials

Addition and subtraction of two polynomials are performed by adding or subtracting corresponding coefficients. If

${\displaystyle f(x)=\sum _{i=0}^{n}a_{i}x^{i};g(x)=\sum _{i=0}^{m}b_{i}x^{i}}$

then addition is defined as

${\displaystyle f(x)+g(x)=\sum _{i=0}^{m}(a_{i}+b_{i})x^{i}}$ where m > n

Multiplication is performed much the same way as addition and subtraction, but instead by multiplying the corresponding coefficients. If ${\displaystyle f(x)=\sum _{i=0}^{n}a_{i}x^{i};g(x)=\sum _{i=0}^{m}b_{i}x^{i}}$ then multiplication is defined as ${\displaystyle f(x)\times g(x)=\sum _{i=0}^{n+m}c_{i}x^{i}}$ where ${\displaystyle c_{k}=a_{0}b_{k}+a_{1}b_{k-1}+\cdots +a_{k-1}b_{1}+a_{k}b_{0}}$. Note that we treat ${\displaystyle a_{i}}$ as zero for ${\displaystyle i>n}$ and that the degree of the product is at most equal to the sum of the degrees of the two polynomials.

Advanced polynomial arithmetics and comparison with arithmetic of the integers

Many properties of polynomials are analogous to those of integers. This is because the structures of ${\displaystyle \mathbb {Z} }$ (the ring of relative integers) and ${\displaystyle K[X]}$ (the ring of polynomials with coefficients in ${\displaystyle K}$) have similar properties. Namely, provided that ${\displaystyle K}$ is a field, ${\displaystyle K[X]}$ is an Euclidean domain, just like ${\displaystyle \mathbb {Z} }$. This structure endows ${\displaystyle K[X]}$ with properties analogous to those of ${\displaystyle \mathbb {Z} }$, such as Bézout's identity, Euclid's lemma, Euclidean division, and the existence of greatest common divisors.

One first needs to introduce two concepts: the notion of root of a polynomial and that of divisibility for pairs of polynomials.

If one considers a polynomial ${\displaystyle P}$ of a single variable X in a field K (typically ${\displaystyle \mathbb {R} }$ or ${\displaystyle \mathbb {C} }$), and with coefficients in that field, a root ${\displaystyle r}$ of ${\displaystyle P}$ is an element of K such that

${\displaystyle P(r)=0}$

The second concept, divisibility of polynomials, allows to see a first analogy with number theory: a polynomial ${\displaystyle B}$ is said to divide another polynomial ${\displaystyle A}$ when the latter can be written as

${\displaystyle A=BC}$

with C being also a polynomial. This definition is similar to divisibility for integers, and the fact that ${\displaystyle B}$ divides ${\displaystyle A}$ is also denoted ${\displaystyle B|A}$.

The relation between both concepts above arises when noticing the following property: ${\displaystyle r}$ is a root of ${\displaystyle P}$ if and only if ${\displaystyle (X-r)|P}$. Whereas one logical inclusion ("if") is obvious, the other ("only if") relies on a more elaborate concept, the Euclidean division of polynomials, here again strongly reminding of the Euclidean division of integers.

From this it follows that one can define prime polynomials, as polynomials that cannot be divided by any other polynomials but 1 and themselves. Here again the analogy with prime integers is manifest. In fact, some of the main definitions and theorems related to prime numbers have their counterpart in polynomial algebra. The most important result is the fundamental theorem of algebra, allowing for factorization of any polynomial as a product of prime ones (a property resulting from the fact that ${\displaystyle K[X]}$, as a Euclidean domain, is also a unique factorization domain). Worth mentioning is also the Bézout's identity for polynomials, which states that two given polynomials P and Q have as greatest common divisor (GCD) a third polynomial D (D is then unique as GCD of P and Q up to a finite constant factor), if and only if there exists polynomials U and V such that

${\displaystyle UP+VQ=D}$.

See also

• Polynomial long division
• Polynomial greatest common divisor

References

• Stallings, William; : "Cryptography And Network Security: Principles and Practice", pages 121-126. Prentice Hall, 1999.

External links

• J.A. Beachy and W.D. Blair; : "Polynomials", from "Abstract algebra", 2nd edition, 1996.