Roots of polynomials modulo prime powers

DOI10.1006/EUJC.1996.0124MaRDI QIDQ1367589zbMATH OpenOpenAlexFDO

Authors Bruce Dearden, Jerry Metzger

Publication date 25 September 1997

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1006/eujc.1996.0124

zbMATH Keywords

modular arithmeticnumber of root setsroot sets modulo \(n\)table

Mathematics Subject Classification ID

Polynomials in number theory (11C08) Polynomials over finite fields (11T06)

Review text

For \(n\in\mathbb{N}\), a subset \(R\) of \(\mathbb{Z}/n\mathbb{Z}\) is called a root set modulo \(n\) provided that there exists a polynomial \(f(x)\) such that \(f(\alpha)\equiv 0\pmod n\) if and only if \(\alpha\in R\). The trivial cases are the empty set and \(\mathbb{Z}/n\mathbb{Z}\), which are always root sets modulo \(n\). Also, for \(p\) a prime, \(\mathbb{Z}/p\mathbb{Z}\) is a root set modulo \(p\). However, in general, root sets are rare. The seminal works on root sets modulo \(n\) are [\textit{M. M. Chojnacka-Pniewska}, Ann. Polon. Math. 3, 9-12 (1956; Zbl 0071.03803); and \textit{W. Sierpiński}, Ann. Polon. Math. 1, 89-90 (1954; Zbl 0055.27101)]. The authors of the paper under review provide methods for efficient computation of the number of roots sets modulo a prime power. One result established is that only a small portion of all possible polynomials modulo \(p^k\) need be solved to determine the total number of root sets modulo \(p^k\). In particular, only the number of root sets modulo a prime power \(p^k\) containing only multiples of \(p\) needs to be determined. The paper concludes with a section on numerical results including a table giving values for the above.

Recommendations

• Root sets of polynomials modulo prime powers
• On the number of roots of an integral polynomial modulo \(q\)
• Counting roots of polynomials over $\mathbb{Z}/p^2\mathbb{Z}$
• Polynomials with roots modulo every integer

Cited in

(12)

• Short polynomial representations for square roots modulo p
• Polynomial products modulo primes and applications
• Polynomials with roots mod \(p\) for all primes \(p\)
• scientific article; zbMATH DE number 4148233 (Why is no real title available?)
• scientific article; zbMATH DE number 1305308 (Why is no real title available?)
• Polynomials with roots modulo every integer
• Counting basic-irreducible factors \(\operatorname{mod} p^k\) in deterministic poly-time and \(p\)-adic applications
• Counting roots of polynomials over $\mathbb{Z}/p^2\mathbb{Z}$
• Root sets of polynomials modulo prime powers
• An effective description of the roots of bivariates mod pk and the related Igusa’s local zeta function
• Solving polynomial systems over non-fields and applications to modular polynomial factoring
• On algorithms to find \(p\)-ordering

This page was built for publication: Roots of polynomials modulo prime powers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1367589)