V. A. Maleev and A. P. Arkhangel’skii.

On the determination of the least exponent \(\omega\) for which the expression \(X^\omega-1\) is divisible exactly by the polynomial \(F(x)=x^n+a_1x^{n-1}+a_2x^{n-2}+\cdots+a_{n-1}x+a_n\), modulo a prime modulus \(p\).

Let
\[ F(x)=x^n+a_1x^{n-1}+a_2x^{n-2}+\cdots+a_{n-1}x+a_n \ldots \tag{1} \]
be an irreducible function modulo \(p\).

Consider the process of algebraic division modulo the prime modulus \(p\) of the expression
\[ x^\omega-1 \]
by the polynomial
\[ x^n+a_1x^{n-1}+a_2x^{n-2}+\cdots+a_{n-1}x+a_n . \]

If we express the quotient of the division in the form of the polynomial
\[ E_0x^{\omega-n}+E_1x^{\omega-n-1}+E_2x^{\omega-n-2}+\cdots+E_{\omega-n-1}x+E_{\omega-n}, \]
and the remainder as
\[ b_0x^{n-1}+b_1x^{n-2}+\cdots+b_{n-2}x+b_{n-1}, \]
then we shall have the following congruence modulo \(p\):
\[ \begin{aligned} x^\omega-1 \equiv{}& (x^n+a_1x^{n-1}+a_2x^{n-2}+\cdots+a_{n-1}x+a_n) (E_0x^{\omega-n}+E_1x^{\omega-n-1} \\ &+E_2x^{\omega-n-2}+\cdots+E_{\omega-n-1}x+E_{\omega-n}) +b_0x^{n-1}+b_1x^{n-2}+b_2x^{n-3}+\cdots \\ &+b_{n-2}x+b_{n-1}\ldots\ldots\ldots(\bmod p) \end{aligned} \tag{2} \]

Carrying out the multiplication and comparing, modulo \(p\), the coefficients of like powers of \(x\) on both sides of congruence (2), we obtain the following series of congruences
\[ \left. \begin{aligned} E_0&=1\\ E_1+a_1E_0&\equiv0\\ E_2+a_1E_1+a_2E_0&\equiv0\\ &\ldots\ldots\ldots\ldots\\ &\ldots\ldots\ldots\ldots\\ E_{n-1}+a_1E_{n-2}+a_2E_{n-3}+\cdots+a_{n-2}E_1+a_{n-1}E_0&\equiv0, \end{aligned} \right\}\quad(\bmod p)\ldots \tag{3} \]
for the initial values \(E_0,E_1,E_2,\ldots,E_{n-1}\) of the coefficients of the quotient; and also the recurrence formula for computing all subsequent coefficients of the quotient for \(i=n,n+1,\ldots\),
\[ E_i+a_1E_{i-1}+a_2E_{i-2}+\cdots+a_nE_{i-n}\equiv0\pmod p. \tag{I} \]

and the following system of congruences for the \(n\) last values of the coefficients of the quotient

\[ \begin{aligned} a_1 E_{\omega-n}+a_2 E_{\omega-n-1}+\cdots+a_n E_{\omega-2n+1}+b'_0&\equiv 0\\ a_2 E_{\omega-n}+a_3 E_{\omega-n-1}+\cdots+a_n E_{\omega-2n+2}+b_1&\equiv 0\\ a_3 E_{\omega-n}+a_4 E_{\omega-n-1}+\cdots+a_n E_{\omega-2n+3}+b_2&\equiv 0\\ \cdots\cdots\cdots\cdots\cdots\cdots\cdots\cdots\cdots\cdots\cdots\cdots\cdots&\\ a_{n-1}E_{\omega-n}+a_n E_{\omega-n-1}+b_{n-2}&\equiv 0\\ a_n E_{\omega-n}-1+b_{n-1}&\equiv 0 \end{aligned} \qquad \begin{array}{r} \cdots\ (4)\\ (\bmod\ p) \end{array} \]

From congruences (4), taking (I) into account, we have:

\[ \left. \begin{aligned} b_0&\equiv-a_1E_{\omega-n}-a_2E_{\omega-n-1}-\cdots-a_nE_{\omega-2n+1}\equiv E_{\omega-n+1}\\ b_1&\equiv-a_2E_{\omega-n}-a_3E_{\omega-n-1}-\cdots-a_nE_{\omega-2n+2}\equiv E_{\omega-n+2}+a_1E_{\omega-n+1}\\ &\cdots\cdots\cdots\cdots\cdots\cdots\cdots\cdots\cdots\cdots\cdots\cdots\cdots\cdots\\ b_{n-2}&\equiv-a_{n-1}E_{\omega-n}-a_nE_{\omega-n-1}\equiv E_{\omega-1}+a_1E_{\omega-2}+\cdots+a_{n-2}E_{\omega-n+1}\\ b_{n-1}&\equiv-a_nE_{\omega-n}+1\equiv E_{\omega}+a_1E_{\omega-1}+a_2E_{\omega-2}+\cdots+a_{n-1}E_{\omega-n+1} \end{aligned} \right\} \qquad \begin{array}{r} \cdots\ (5)\\ (\bmod\ p) \end{array} \]

On the basis of formulas (5), the remainder

\[ b_0x^{n-1}+b_1x^{n-2}+b_2x^{n-3}+\cdots+b_{n-2}x+b_{n-1} \]

is written in the form

\[ E_{\omega-n+1}x^{n-1}+\bigl(E_{\omega-n+2}+a_1E_{\omega-n+1}\bigr)x^{n-2}+\cdots+E_\omega+\bigl(E_{\omega-1}a_1+ \]

\[ +a_2E_{\omega-2}+\cdots+a_{n-1}E_{\omega-n+1}\bigr)-1 \qquad\cdots\cdots\cdots (6) \]

We now return to congruence (I) and replace \(i\) in it by \(n+i\); then we shall have

\[ E_{i+n}+a_1E_{i+n-1}+a_2E_{i+n-2}+\cdots+a_{n-1}E_{i+1}+a_nE_i\equiv0\pmod p \]

From it, substituting for \(i\) the series of values \(i=-1,-2,\ldots,-n+1\), we obtain

\[ \left. \begin{aligned} E_{n-1}+a_1E_{n-2}+\cdots+a_{n-1}E_0+a_nE_{-1}&\equiv0\\ E_{n-2}+a_1E_{n-3}+\cdots+a_{n-1}E_1+a_nE_{-2}&\equiv0\\ \cdots\cdots\cdots\cdots\cdots\cdots\cdots\cdots\cdots&\\ \cdots\cdots\cdots\cdots\cdots\cdots\cdots\cdots\cdots&\\ E_1+a_1E_0+a_3E_3+\cdots+a_{n-1}E_{-n+2}+a_nE_{-n+1}&\equiv0 \end{aligned} \right\} \qquad \begin{array}{r} \cdots\ (7)\\ (\bmod\ p) \end{array} \]

From comparison of congruences (3) and (7) we obtain the series

\[ E_{-n+1}\equiv E_{-n+2}\equiv\cdots\equiv E_{-2}\equiv E_{-1}\equiv0;\quad E_0\equiv1\pmod p.\qquad (8) \]

or

\[ E_{-n+1}=0;\quad E_{-n+2}=0;\quad \ldots\quad E_{-2}=0;\quad E_{-1}=0;\quad E_0=1 \quad(\mathrm{II}) \]

Let \(\alpha_1,\alpha_2,\ldots,\alpha_n\) be the roots of the function

\[ F(x)=x^n+a_1x^{n-1}+a_2x^{n-2}+\cdots+a_{n-1}x+a_n . \]

Let us express the coefficients of the quotient

\[ E_0,\ E_1,\ E_2,\ldots,\ E_n \]

as functions of the roots

\[ \alpha_1,\ \alpha_2,\ldots,\alpha_{n-1},\ \alpha_n . \]

Indeed, by the very meaning of the algebraic operation, we have:

\[ \frac{x^\omega-1}{F(x)} = x^{\omega-n}+E_1x^{\omega-n-1}+E_2x^{\omega-n-2}+\cdots+E_{\omega-n}+ \]

\[ +\frac{E_{\omega-n+1}}{x}+\frac{E_{\omega-n+2}}{x^2}+\cdots-\frac{1}{F(x)}\qquad\cdots\cdots\cdots (9) \]

On the other hand,

\[ \frac{x^\omega-1}{F(x)} = x^{\omega-n}\cdot \frac{1}{1-\frac{\alpha_1}{x}}\cdot \frac{1}{1-\frac{\alpha_2}{x}}\cdot \ldots \cdot \frac{1}{1-\frac{\alpha_n}{x}} -\frac{1}{F(x)} \]

\[ = x^{\omega-n} \left(1+\frac{\alpha_1}{x}+\frac{\alpha_1^2}{x^2}+\ldots\right) \left(1+\frac{\alpha_2}{x}+\frac{\alpha_2^2}{x^2}+\ldots\right) \ldots \left(1+\frac{\alpha_n}{x}+\frac{\alpha_n^2}{x^2}+\ldots\right) -\frac{1}{F(x)} \tag{10} \]

From (9) and (10) we find:

\[ E_1=\alpha_1+\alpha_2+\alpha_3,\ldots,+\alpha_n=\sum \alpha_i \]

\[ E_2=\alpha_1^2+\alpha_2^2+\ldots+\alpha_n^2+\alpha_1\alpha_2+\alpha_1\alpha_3+\ldots+\ldots =\sum \alpha_i^2+\sum \alpha_i\alpha_j \]

\[ \ldots\ldots\ldots\ldots\ldots\ldots\ldots\ldots\ldots\ldots\ldots\ldots\ldots \]

\[ \ldots\ldots\ldots\ldots\ldots\ldots\ldots\ldots\ldots\ldots\ldots\ldots\ldots \]

Thus, each \(E_i\) is an integral homogeneous symmetric function of the \(i\)-th degree of all roots of the equation

\[ F(x)=0 \]

Suppose that \(\omega\) is the least exponent for which the expression \(x^\omega-1\) is divisible without remainder modulo a prime \(p\) by a function \(F(x)\) irreducible modulo this modulus.

In this case, for the coefficients of the remainder

\[ b_0x^{n-1}+b_1x^{n-2}+\ldots+b_{n-2}x+b_{n-1} \]

we obtain a series of congruences

\[ b_0\equiv b_1\equiv b_2\equiv b_3\equiv \ldots \equiv b_{n-2}\equiv b_{n-1}\equiv 0 \pmod p \]

whence, on the basis of (5),

\[ \left. \begin{aligned} E_{\omega-n+1}&\equiv 0\\ E_{\omega-n+2}+a_1E_{\omega-n+1}&\equiv 0\\ &\ldots\ldots\ldots\ldots\\ &\ldots\ldots\ldots\ldots\\ E_\omega+a_1E_{\omega-1}+a_2E_{\omega-2}+\ldots+a_{n-1}E_{\omega-n+1}-1&\equiv 0 \end{aligned} \right\} \ldots \tag{11} \]

or

\[ E_{\omega-n+1}\equiv E_{\omega-n-2}\equiv \ldots E_{\omega+1}\equiv 0;\quad E_\omega\equiv 1 \pmod p \tag{III} \]

Thus, if \(\omega\) is the least exponent for which the division of the expression \(x^\omega-1\), modulo a prime \(p\), by a function \(F(x)\) irreducible modulo this modulus is performed without remainder, then the sequence of values of the quantities \(E_0,E_1,\ldots,E_i\), formed according to the recurrence formula

\[ E_i+a_1E_{i-1}+\ldots+a_nE_{i-n}\equiv 0 \pmod p \]

is, modulo \(p\), a periodic sequence, with the number of terms in the period equal to \(\omega\).

Let us show that for the function \(F(x)=x^kF_1(x)\), where

\[ F_1(x)=x^n+Ax^{n-1}+Bx^{n-2}+\ldots L \tag{12} \]

the sequence of values \(E_i\) will consist of \(k\) zeros and of the periodic sequence for the function (12), i.e.

\[ \begin{array}{c} 0\\ 0\\ \cdot\\ \cdot\\ \cdot\\ \cdot\\ \cdot\\ 0\\ 0\\ 0\\ \cdot\\ \cdot\\ E_0\\ E_1\\ \cdot\\ \cdot\\ \cdot\\ \cdot \end{array} \left\{ \begin{array}{l} k\ \text{zeros}\\[5.5em] \text{for the function}\\ x^n+A x^{n-1}+B x^{n-2}+\cdots L \end{array} \right. \]

Indeed, the function \(F(x)\) will be of degree \(n+k\) and, consequently, for it the recurrence formula has the form

\[ E_{n-k+1}\equiv 0;\quad E_{n-k+2}\equiv 0;\quad E_{n-k+3}\equiv 0;\quad \ldots\quad E_1\equiv 0;\quad E_2\equiv 1 \pmod p \]

All subsequent values \(E_1, E_2, E_3,\ldots\), will coincide with the values of the quantities \(E'_1, E'_2, E'_3,\ldots\) of the coefficients of the quotient

\[ \frac{x^\omega-1}{F_1(x)} \]

and therefore the sequence of values of the quantities \(E_i\) for the function \(F(x)\) will differ from the same sequence for \(F_1(x)\) only in that \(k\) zeros will enter into it.

Let the function be decomposed into a sequence of irreducible functions \(F_1(x), F_2(x)\ldots,F_s(x)\), among which there are none congruent to one another modulo \(p\).

Denote the least exponents for the function \(F(x)\) by \(\omega\), and for \(F_1(x), F_2(x)\ldots,F_s(x)\), respectively, by

\[ \omega_1,\ \omega_2,\ldots,\omega_s. \]

Let

\[ \omega_1=\delta\omega'_1,\quad \omega_2=\delta\omega'_2,\ldots,\quad \omega_s=\delta\omega'_s \]

where \(\delta\) is the greatest common divisor of the numbers

\[ \omega_1,\ \omega_2,\ldots,\omega_s, \]

then the differences

\[ x^\omega-1,\quad x^{\omega_1}-1,\ldots,\quad x^{\omega_s}-1 \]

are divided respectively without remainder by

\[ F(x),\ F_1(x),\ F_2(x)\ldots,F_s(x) \]

In view of this, the congruences hold

\[ \omega \equiv 0 \pmod{\partial\omega'_1} \]

\[ \omega \equiv 0 \pmod{\partial\omega'_2} \]

\[ \cdots\cdots\cdots\cdots \]

\[ \cdots\cdots\cdots\cdots \]

\[ \omega \equiv 0 \pmod{\partial\omega'_s} \]

and, consequently, the congruence

\[ \omega \equiv 0 \pmod{\omega_1,\ \omega_2,\ldots,\omega_s}. \]

Thus, if the function \(F(x)\) can be represented in the form of a product of several irreducible and pairwise incongruent modulo \(p\) functions

\[ F_1(x),\ F_2(x),\ldots,F_s(x), \]

then the least exponent \(\omega\) for \(F(x)\) is equal to the least common multiple of the corresponding least exponents \(\omega_1,\omega_2,\ldots,\omega_s\) for the functions \(F_1(x), F_2(x),\ldots,F_s(x)\).

Let the function \(F(x)\) decompose into a product of factors

\[ F_1(x)^{m_1},\ F_2(x)^{m_2},\ldots,F_s(x)^{m_s}, \]

among which there are some congruent modulo \(p\).

Denote by \(\omega\) the least exponent for which the division of \(x^\omega-1\) by the function \(F(x)\) is exact, and by

\[ \alpha_1,\ \alpha_2,\ldots,\alpha_n \]

the roots of the function \(F(x)\).

If

\[ \alpha_1 \equiv \alpha_2 \pmod p \]

then, since every \(E\) is an integral homogeneous symmetric function of the roots of the equation \(F(x)=0\), we have

\[ \begin{aligned} E_{\omega-n+1} &\equiv (\omega-n+2)\alpha_1^{\omega-n+1} +(\omega-n+1)\alpha_1^{\omega-n}E'_1+\cdots+E'_{\omega-n+1}\equiv 0\\ E_{\omega-n+2} &\equiv (\omega-n+3)\alpha_1^{\omega-n+2} +(\omega-n+2)\alpha_1^{\omega-n+1}E'_1+\cdots+E'_{\omega-n+2}\equiv 0\\ &\cdots\cdots\cdots\cdots\cdots\cdots\cdots\cdots\cdots\cdots\cdots\cdots\cdots\cdots\cdots\\ &\cdots\cdots\cdots\cdots\cdots\cdots\cdots\cdots\cdots\cdots\cdots\cdots\cdots\cdots\cdots\\ E_{\omega-1} &\equiv \omega\alpha_1^{\omega-1} +(\omega-1)\alpha_1^{\omega-2}E'_1+\cdots+E'_{\omega-1}\equiv 0\\ E_{\omega} &\equiv (\omega+1)\alpha_1^{\omega} +\omega\alpha_1^{\omega-1}E'_1+\cdots+E'_{\omega}\equiv 0, \end{aligned} \qquad (\bmod\ p) \]

where

\[ E'_0,\ E'_1,\ E'_2,\ldots,E'_\omega \]

are the coefficients of the quotient

\[ \frac{(x^\omega-1)(x-\alpha_1)^2}{F(x)}, \]

Write the quotient obtained by dividing the function \(F(x)\) by \((x-\alpha_1)^2\) in the form of the following polynomial

\[ \frac{F(x)}{(x-\alpha_1)^2} = x^{n-2}+b_1x^{n-3}+b_2x^{n-4}+\cdots+b_{n-2}, \]

substituting the values

\[ E_\omega,\ E_{\omega-1},\ldots,E_{\omega-n+2} \]

into the expression

\[ E_\omega+b_1E_{\omega-1}+b_2E_{\omega-2}+\cdots+b_{n-2}E_{\omega-n+2}, \]

we obtain

\[ (\omega+1)\alpha_1^\omega \equiv 1 \pmod p \]

Likewise, substituting the same values \(E\) into the expression

\[ E_{\omega-1}+b_1E_{\omega-2}+b_1E_{\omega-3}+\cdots+b_{n-2}E_{\omega-n+1}, \]

we find

\[ \omega\alpha_1^{\omega-1}\equiv 0 \pmod p \]

Whence it follows that

\[ \omega\equiv 0 \pmod p, \]

i.e., if the function \(F(x)\) decomposes into the product of functions

\[ F_1(x)^{m_1},\ F_2(x)^{m_2},\ldots,F_s(x)^{m_s} \]

among which there are functions comparable modulo the prime modulus \(p\), then the least exponent \(\omega\) is divisible by the modulus \(p\).