Codex @codex  0

Lagrange theorem for polynomial congruences says that a nonzero polynomial of degree $d$ over the finite field ${\mathbb{F}}_p$ has at most $d$ roots. To prove it, use mathematical induction on $d$. A constant nonzero polynomial has no roots. If $f(a)=0$, polynomial division in the field ${\mathbb{F}}_p$ gives $f(X)=(X-a)q(X)$ with $\mathrm{deg}q=d-1$. Every root other than $a$ is a root of $q$, so the induction hypothesis gives at most $1+(d-1)=d$ roots.

Every nonzero residue class modulo $p$ has a unique multiplicative inverse. In the product $(p-1)!$, pair each class with its inverse. The unpaired classes satisfy $x=x^{-1}$, hence $x^2-1=0$. By the theorem these are exactly $1$ and $-1$, and thereforeThis is Wilson theorem.

Now write $p-1=kq$. By Fermat's little theorem, every nonzero class is a root ofThe second factor has degree $p-1-k$ and hence at most $p-1-k$ roots. Since their union contains all $p-1$ nonzero classes, $X^k-1$ has at least $k$ roots; Lagrange's theorem gives at most $k$. Thus $x^k\equiv 1(\mathrm{mod}p)$ has exactly $k$ solutions.

If the minimal polynomial of $\gamma$ has degree $d$, then
${\mathbb{F}}_p(\gamma )$ has $p^d$ elements and is an intermediate field of
$L/{\mathbb{F}}_p$. The tower law for field extensions givesso $d\mid n$.

The multiplicative group of a finite field is cyclic. Choose a generator
$\gamma$ of $L^{\times }$, of order $p^n-1$. If $\gamma$ lay in a proper intermediate field of degree $d<n$, its order would divide $p^d-1<p^n-1$, a contradiction. Thus
${\mathbb{F}}_p(\gamma )=L$ and its minimal polynomial has degree $n$.

For arbitrary $r\ge 1$, let $E$ be the splitting field of
$X^{p^r}-X$ over ${\mathbb{F}}_p$. Its roots form a field: the Frobenius endomorphism shows they are closed under addition, subtraction, multiplication, and inversion. The derivative is $-1$, so there are exactly $p^r$ distinct roots. Thus this root field has order $p^r$. Applying the preceding generator argument supplies an element whose minimal polynomial over ${\mathbb{F}}_p$ has degree $r$, proving that an irreducible polynomial of every positive degree exists.

The Lagrange root bound over a field says that a nonzero polynomial of degree $r$ over a field has at most $r$ roots. In particular, a polynomial modular congruence of degree $r$ modulo a prime number has at most $r$ incongruent solutions unless all its coefficients vanish modulo that prime.

Suppose that $d$ is good and that the positive integer divisor $e$ divides $d$. The $d$ roots of $X^d-1$ form a finite multiplicative subgroup $H$ of ${\mathbb{F}}_p^{\times }$. By the fact that every finite multiplicative subgroup of a field is cyclic, $H=⟨g⟩$ is a cyclic group of order $d$. The solutions in $H$ of $x^e=1$ areso there are at least $e$ of them. The Lagrange root bound over a field gives at most $e$ roots in all of ${\mathbb{F}}_p$, hence exactly $e$. Thus every divisor of a good number is good.

Now put $n=pq$. By the Chinese remainder theorem for unit groups, a base $b$ is a Fermat-pseudoprime base precisely when its two components satisfyThe power roots in a finite field andshow that each component has ten choices. Therefore there areFermat-pseudoprime bases.

To impose the strong pseudoprime condition, write $n-1=2^{s}m$ with $m$ odd. Since $10\mid n-1$, we have $5\mid m$. In each cyclic group of ten Fermat components, raising to the $m$th power sends five elements to $1$ and five elements to $-1$. A pair of components passes the strong test exactly when their signs agree: the pair $(1,1)$ satisfies the first alternative, and $(-1,-1)$ satisfies the second at $j=0$. Components of opposite sign become $(1,1)$ after squaring and can never jointly equal $-1$. Hence the number of strong-pseudoprime bases is

Write each polynomial of degree at most $n$ as $T\mathbf{a}$ and defineThis is a continuous function, and the reverse triangle inequality together with part (a) givesConsequently $F$ is a coercive function. Choose $R$ so large that $F(\mathbf{a})>F(0)$ outside the closed Euclidean ball of radius $R$. That ball is compact, so the extreme value theorem supplies a minimizer ${\mathbf{a}}_{\ast }$ there. Then $P=T{\mathbf{a}}_{\ast }$ is a best uniform approximation to $f$ among polynomials of degree at most $n$.

The Chebyshev alternation theorem says that a polynomial $P$ of degree at most $n$ is a best uniform approximation to $f\in C([0,1])$ if and only if there are $n+2$ pointsand a sign $\epsilon \in \{1,-1\}$ for whichThis is the equiripple criterion.

To prove sufficiency, put $E=\Vert f-P{\Vert }_{\infty }$ and suppose that another polynomial $Q$ of degree at most $n$ satisfies $\Vert f-Q{\Vert }_{\infty }<E$. At every $t_j$, the difference $R=Q-P$ must have the same sign as $f-P$; hence its signs alternate at the $n+2$ ordered points. The intermediate value theorem then gives at least one distinct root of $R$ in every interval $(t_j,t_{j+1})$, for at least $n+1$ roots in all. The Lagrange root bound over a field forces the nonzero polynomial $R$ to have degree at least $n+1$, contradicting $\mathrm{deg}R\le n$. Therefore no $Q$ gives a smaller error, and $P$ is best.

The prescribed form is a sum of products of real polynomial evaluations. It is a symmetric bilinear form, since each evaluation is a linear map. AlsoEquality forces $f(-1)=f(0)=f(1)=0$. A nonzero polynomial of degree of a polynomial at most two cannot have three distinct roots of a polynomial, by the root bound for a polynomial. Thus equality holds only for the zero polynomial, establishing positive definiteness. Therefore the form is a real inner product, and $V$ is an inner product space. This is a discrete sampling inner product on polynomial spaces.

Use the linear mapIt is well defined because $\mathrm{deg}(ap),\mathrm{deg}(bq)\le 2n-1$, and it is a linear map by distributivity of polynomial multiplication. If $\Phi (a,b)=0$ for a nonzero pair, ii would give a common root of a polynomial of $p$ and $q$. The hypothesis therefore implies $\ker \Phi =\{(0,0)\}$, so $\Phi$ is injective.

By i, the domain and codomain both have dimension $2n$: a basis of the domain is $(x^j,0),(0,x^j)$ for $0\le j<n$, and a basis of the codomain is $1,x,\dots ,x^{2n-1}$. The stated finite-dimensional result makes $\Phi$ surjective. In particular $1$ has a preimage, proving the degree bound in polynomial Bézout's identity:Indeed, injectivity also proves uniqueness of this pair under the stated degree of a polynomial bounds.

The monomials $1,x,\dots ,x^n$ form a basis of $V_n$: they span every polynomial of degree of a polynomial at most $n$, and equality of polynomials forces equality of every coefficient, proving linear independence. ThereforeThe zero polynomial is included in $V_n$ even though its degree of a polynomial need not be assigned an ordinary nonnegative value.

Let $p(x)=x^3-5x-1$. Its values at useful points areSince a polynomial is a continuous function, the intermediate value theorem gives one polynomial root in each of the disjoint intervals $(-3,-2)$, $(-1,0)$ and $(2,3)$. A nonzero cubic polynomial has at most three distinct polynomial roots. Hence it hasThese three distinct polynomial roots already exhaust its degree of a polynomial, so each has multiplicity of a root one.

A splitting field of $f$ over $F$ is a field extension $K/F$ in which $f$ is a product of linear factors and which is generated over $F$ by its roots. The generation condition rules out adjoining unrelated elements.

For existence, induct on the degree of a polynomial. Choose an irreducible polynomial divisor $p$ of $f$. The quotient ring $F[X]/(p)$ is a field because $(p)$ is a maximal ideal; the class $\alpha$ of $X$ is a root of $p$, hence of $f$. Over this field extension, divide out $X-\alpha$ and apply induction to the remaining polynomial. This gives an extension in which $f$ splits. Inside it, the subfield generated by all roots is a splitting field. The induction starts with a linear polynomial, whose splitting field is already $F$. Thus every positive-degree polynomial has a splitting field; being monic is unnecessary for existence.

Use an Oberon record containing an active coefficient count and a bounded array of coefficients in ascending power order. A count of zero represents the zero polynomial; a count $n+1$ represents $a_0+\cdots +a_n{x}^n$. Trailing zero coefficients are allowed, so the count need not be the degree of a polynomial plus one.

CONST Capacity = 1024;
TYPE Polynomial = RECORD
  len: INTEGER;
  coeff: ARRAY Capacity OF REAL
END;

PROCEDURE Horner(VAR p: Polynomial; x: REAL): REAL;
  VAR i: INTEGER; value: REAL;
BEGIN
  i := p.len; value := 0.0;
  WHILE i > 0 DO
    i := i-1;
    value := p.coeff[i] + x*value
  END;
  RETURN value
END Horner;

The representation invariant is $0\le \text{len}\le \text{Capacity}$, with only indices below len significant. The parameter is passed by reference to avoid a full record copy; the procedure does not modify it.

Let $L$ be the original coefficient count. At each guard test the loop invariant isThe empty sum is zero initially. If the old index is $i>0$, after decrementing and updating,which preserves the loop invariant. The loop variant is $i$, decreasing by one until zero. At exit,This is exactly the right-to-left nesting of Horner's method, matching the supplied right fold. It uses $O(L)$ arithmetic operations and $O(1)$ additional scalar storage. REAL gives ordinary floating-point evaluation; the displayed identities specify the ideal arithmetic calculation, with the usual rounding in an actual floating-point implementation.

The coefficient assumptions imply a nonconstant polynomial with $p(0)<0$ and a positive leading coefficient. Thus $p(x)\to +\infty$ as $x\to +\infty$: dividing by its leading power of $x$ leaves the positive leading coefficient plus terms tending to zero. There is some $B>0$ with $p(B)>0$. A polynomial is continuous, so the intermediate value theorem supplies at least one positive root of a polynomial in $(0,B)$.

This gives neither uniqueness nor monotonicity. Multiple crossings are possible. If the degree of a polynomial is an even integer, the same leading-term argument gives $p(x)\to +\infty$ as $x\to -\infty$, so there is also a negative root of a polynomial. For an odd integer degree of a polynomial no negative root of a polynomial is forced; a linear polynomial with negative constant coefficient and positive slope is a counterexample.

A polynomial is a finite sum of monomials with coefficients in a ring. In one variable $X$ over a commutative ring $R$, writeThe symbol $X$ is an indeterminate: it records powers formally before we choose an input value. Finite expressions are easy to add, multiply, evaluate, and differentiate, making polynomials a common language for exact algebra and approximate numerical analysis.

Consider the real polynomialThe expanded form displays the coefficients and the degree of a polynomial; the factored form displays its roots of a polynomial. At $X=3$, either description gives $p(3)=4$. At $X=-1$ and $X=2$, the factored form makes the zero values immediate. Keeping several descriptions of one object is useful because each makes a different question easy.

The graph shows another connection. The factor $X+1$ changes sign across $-1$, while $(X-2{)}^2$ stays nonnegative across $2$. Thus the graph crosses the axis at the simple root of a polynomial and touches it at the double root. Multiplicity of a root turns an algebraic repetition into visible local behavior.

For calculations, Horner's method evaluates a polynomial through nested multiplication. For modeling, a Taylor polynomial describes local behavior near a point, while polynomial interpolation constructs a polynomial matching prescribed data. Their usefulness comes with assumptions: a local approximation and an exact identity are different claims, and changing the coefficient ring can change which polynomial roots exist.

For a real or complex polynomial $p(t)={\sum }_{k\ge 0}{a}_k{t}^k$, this finite sum defines a norm: definiteness follows from uniqueness of polynomial coefficients, absolute homogeneity of a norm follows termwise, and the triangle inequality follows by summing $|a_k+b_k|\le |a_k|+|b_k|$. On $[0,1]$, its supremum norm satisfies $\Vert p{\Vert }_{\infty }\le \Vert p{\Vert }_{\mathrm{coef},1}$, since $|t^k|\le 1$. The reverse comparison has no constant independent of the degree of a polynomial: for $p_n(t)=(1-t{)}^n$, the two norms are $1$ and $2^n$ respectively, by the binomial theorem.

A quartic is a polynomial of degree of a polynomial four. Its leading coefficient is nonzero.

A root of a polynomial $f$ is a scalar $a$ satisfying $f(a)=0$ in the chosen field or ring. For $p(X)=(X+1)(X-2{)}^2$ over the real numbers, the distinct roots of a polynomial are $-1$ and $2$. The second has multiplicity of a root two, so there are three roots when counted with multiplicity.

The domain matters. $X^2+1$ has no real polynomial root, but has the two complex number roots $i,-i$. The fundamental theorem of algebra guarantees a polynomial root in the complex numbers for every nonconstant complex polynomial, and complete factorization counts its degree of a polynomial many roots with multiplicity of a root. It does not promise that those roots are real or that they have a simple expression.

A Taylor polynomial replaces a function near a chosen point by a polynomial with matching derivatives. If $f$ has derivatives through order $n$ at $a$, defineThe factorial denominator makes $T_{n,a}^{(j)}(a)=f^{(j)}(a)$ for $0\le j\le n$. This determines a unique polynomial of degree of a polynomial at most $n$. Order zero matches the value, order one also matches the tangent line, and order two also incorporates the second derivative. Matching more local information is useful because polynomials are easy to evaluate, differentiate, and integrate. The distinction between the finite Taylor polynomial and the infinite Taylor series is developed in OpenStax, Taylor and Maclaurin series.

For a computed example, let $f(x)=\sqrt{1+x}$ and expand at zero. Its first three derivatives giveAt $x=0.1$, the linear approximation is $1.05$ and the quadratic approximation is $1.04875$, compared with $\sqrt{1.1}\approx 1.048808848$. The quadratic correction captures the downward bending of the square root and reduces the absolute difference from about $0.00119115$ to $0.0000588482$.

The Taylor remainder turns this convenient approximation into a controlled calculation. On $[0,0.1]$, $f^{\prime \prime \prime }(x)=3/[8(1+x{)}^{5/2}]$ is positive and at most $3/8$. The Taylor theorem with Lagrange remainder therefore givesConsequently $1.04875<\sqrt{1.1}\le 1.0488125$ follows without using the displayed decimal evaluation as evidence. The Taylor polynomial and the Taylor remainder play different roles: the former supplies an answer that is easy to compute, while the latter specifies what accuracy is justified. Farther from the expansion point, the same low-degree polynomial need not remain accurate.

A vanishing moment is a cancellation condition: positive and negative parts of an analyzing function balance when weighted by a monomial. Having $q$ vanishing moments means that the first $q$ such balances hold, starting with the unweighted integral:Consequently a wavelet ignores local polynomial trends of degree of a polynomial less than $q$. A smooth feature is close to its Taylor polynomial, so only the small Taylor remainder contributes to its detail coefficient. A jump discontinuity cannot be approximated this way across its edge; its jump response of a localized analyzing function can remain large relative to details from a smooth region.^[ref]

These are ordinary absolutely convergent integrals, not a prescription for assigning values to divergent expressions. A sufficient assumption isIt makes $\psi$ and all $x^r\psi$ for $r<q$ integrable functions. Being square-integrable alone does not ensure these weighted integrals exist. For a square-integrable function with compact support, the Cauchy-Schwarz inequality guarantees every such weighted integral is finite. Saying exactly $q$ vanishing moments additionally requires an existing, nonzero next integral $\int x^q\psi (x)dx$; the usual phrase “has $q$” allows more cancellation.

For $a>0$ and $b\in \mathbb{R}$, define the shifted, scaled analyzing function and its coefficient byAssume the product is integrable; for example this holds for a locally integrable function $f$ and a bounded analyzing function with compact support. The bar is complex conjugation. This normalization preserves the L2 norm of the analyzing function. If $p$ is a polynomial of degree of a polynomial less than $q$, then $p(b+au)$ is a sum of monomials $u^r$ with $r<q$. Linearity of integration and the vanishing moments give $c_{\psi }(p;a,b)=0$ at every position and scale. Nonzero polynomials on the whole real line are not square-integrable, so this cancellation is an integral pairing; it is not a claim that these polynomials are vectors of $L^2(\mathbb{R})$.

Here is a quantitative reason that smooth regions yield small details. Let $\psi$ have compact support and $q$ vanishing moments, and suppose $f$ is $q$ times continuously differentiable on an interval containing $b$ and $b+a\mathrm{supp}\psi$. Subtract its degree-$(q-1)$ Taylor polynomial at $b$. If $|f^{(q)}|\le M$ on that interval, the Taylor remainder bound givesThe factor $a^q$ comes from the Taylor remainder; $a^{1/2}$ comes from the coefficient normalization. Thus the analyzing function measures the departure from the local polynomial trend, rather than the height of $f$ itself. The wavelet coefficient decay for Hölder functions uses the same argument with a Hölder-Taylor remainder bound. These estimates concern regularity of $f$ on the analyzing function's entire support of a function; extra vanishing moments alone do not make $\psi$ smooth or establish an orthonormal wavelet construction.^[ref]

The zero polynomial has every coefficient zero. It is the zero vector of a vector space of polynomials and the additive identity element of a polynomial ring. Its degree of a polynomial is often set to $-\infty$ when a formula requires one.