University of Surrey

Test tubes in the lab Research in the ATI Dance Research

Null Polynomials modulo m

Li, SJ (2005) Null Polynomials modulo m .

Available under License : See the attached licence file.

Download (385kB)
Text (licence)

Download (33kB)


This paper studies so-called "null polynomials modulo m", i.e., polynomials with integer coefficients that satisfy f(x)=0 (mod m) for any integer x. The study on null polynomials is helpful to reduce congruences of higher degrees modulo m and to enumerate equivalent polynomial functions modulo m, i.e., functions over Z_m={0, ..., m-1} generated by integer polynomials. The most well-known null polynomial is f(x)=x^p-x modulo a prime p. After pointing out that null polynomials modulo a composite can be studied by handling null polynomials modulo each prime power, this paper mainly focuses on null polynomials modulo p^d (d>=1). A typical monic null polynomial of the least degree modulo p^d is given for any value of d>=1, from which one can further enumerate all null polynomials modulo p^d. The most useful result obtained in this paper are Theorem 32 in Sec. 4.4 and its derivative -- Theorem 34 in Sec. 4.5. The results given in Sec. 4.3 form a basis of the induction proofs given in Sec. 4.4. However, if you do not care how the proofs in Sec. 4.4 were established, you can simply skip Sec. 4.3. Theorems 28 and 31 are very important for the proof of Theorem 32 and should be paid more attention. Note: After finishing this draft, we noticed that some results given in this paper have been covered in Kempner's papers [3,4]. Since we use a different way to obtain the results, this work can be considered as an independent and different proof. For a brief introduction to Kempner's proof, see the Appendix of this paper.

Item Type: Other
Divisions : Faculty of Engineering and Physical Sciences > Computing Science
Authors :
Li, SJ
Date : 14 November 2005
Related URLs :
Additional Information : This is an arXiv publication
Depositing User : Symplectic Elements
Date Deposited : 26 Aug 2015 13:43
Last Modified : 31 Oct 2017 14:35

Actions (login required)

View Item View Item


Downloads per month over past year

Information about this web site

© The University of Surrey, Guildford, Surrey, GU2 7XH, United Kingdom.
+44 (0)1483 300800