Powers and polynomials in \(\mathbb{Z}_m\) (Q1976822)

The authors consider powers and polynomials in the ring \(\mathbb{Z}_m\), where \(m\in \mathbb{N}\) is arbitrary, and ask for ``reduction formulas'' which allow the exponent to be reduced. Of course in general the formula \[ a^b\equiv a^{b\bmod m}\bmod m \] is false. In the second section they investigate for which numbers \(m\) such a reduction formula holds. They obtain the values 1, 2, 6, 42 and 1806. In the third and the two following sections they consider generalizations of Fermat's little theorem and Euler's theorem which allow them to replace (in \(\mathbb{Z}_m\)) certain powers \(a^b\) by a polynomial \(f(a)\) of degree \(\deg(f)\) which is strictly less than \(b\). Such formulas can be useful for various reasons: From an algorithmic point of view, it is cheaper to compute the polynomial \(f(a)\) modulo \(m\) than the full power \(a^b\) modulo \(m\). On the other hand one may wish for algebraic reasons to replace an arbitrary polynomial \(g(a)\) by a polynomial of fixed (lower) degree (depending only on \(m\) but not on \(g\)) which is, as a function in \(\mathbb{Z}_m\), identical to \(g\). In the last section, they address the question of the minimal degree \(e(m)\) such that every polynomial in \(\mathbb{Z}_m\) can be written as a polynomial of degree \(q< e(m)\). They give a complete answer to this question by determining minimal (normed) null-polynomials modulo \(m\). This article was done jointly with Hans Läuchli who died in August 1997.