By what can we reduce the exponent of an element in a finite order Group?

The group {{c2:: \(\langle \mathbb{Z}_n; \oplus \rangle\)}} is generated by \(1\).

The generators of \(\langle \mathbb{Z}_n; \oplus \rangle\) are all \(g \in \mathbb{Z}_n\) for which \(\gcd(g, n) = 1\) (i.e., \(g\) is coprime to \(n\)).

The group \(\langle \mathbb{Z}_n; \oplus \rangle\) is cyclic for every \(n\), where \(1\) is always a generator.

Front

What is a polynomial over a commutative ring?

Back

A polynomial \(a(x)\) over a commutative ring \(R\) in the indeterminate \(x\) is a formal expression of the form: \[ a(x) = {{c2::a_d x^d + a_{d-1}x^{d-1} + \cdots + a_1 x + a_0}} = \sum_{i=0}^d a_i x^i \] for some non-negative integer \(d\), with \(a_i \in R\).

The set of polynomials in \(x\) over \(R\) is denoted .

Front

Lagrange Interpolation for polynomials in a Field

Back

Let \(\beta_i = a(\alpha_i)\) for \(i = 1, \dots, d+1\).

Then \(a(x)\) is given by Lagrange's Interpolation formula: \[a(x) = \sum_{i=1}^{d+1} \beta_i u_i(x)\] where the polynomial \(u_i(x)\) is: \[u_i(x) = \frac{{{c2::(x - \alpha_1) \cdots (x - \alpha_{i-1})(x - \alpha_{i+1}) \cdots (x - \alpha_{d+1})}}}{{{c3::(\alpha_i - \alpha_1) \cdots (\alpha_i - \alpha_{i-1})(\alpha_i - \alpha_{i+1}) \cdots (\alpha_i - \alpha_{d+1})}}}\]

Note that for \(u_i(x)\) to be well-defined, all constant terms \(\alpha_i - \alpha_j\) in the denominator must be invertible. This is guaranteed in a field since \(a_i - a_j \neq 0\) for \(i \neq j\) (as they are all distinct).