[seqfan] Re: x^k-1 divisible by an irreducible polynomial in a finite field. A371164 and A106309

[Max Alekseyev]

We can notice that k is a divisor of p^deg(q)-1, and so k can be found as
the smallest divisor that does the job.
There is no need to construct the extension and perform any computations
there.

Regards,
Max

On Tue, Mar 26, 2024 at 7:25 PM <israel at math.ubc.ca> wrote:

> This is relevant to A371164 and A106309. I think this is correct, but I'd
> like confirmation from someone better acquainted with finite fields than I
> am.
>
> Suppose the monic polynomial q(z) of degree d >1 is irreducible over a
> finite field F (the integers modulo a prime p, if that makes a
> difference).
> I want to find the least positive integer k such that z^k - 1 is divisible
> by q(z) over F. If I take the extension field K = F[r] where r is a root
> of
> q(z), is the answer the order of r in the multiplicative group K^x$ of K?
>
> For example, take F to be the integers mod 13, and
> q(z) = x^4 + 5 x^2 + x + 10.
> Maple (using the GF package) tells me the order of r in this case is
> 14280.  Indeed z^{14280}-1 is divisible by q(z) over F in this case,
> and no divisor of 14280 will work.
>
> Cheers,
> Robert
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/
>