Notes on Number Theory and Discrete Mathematics
Print ISSN 1310–5132, Online ISSN 2367–8275
Volume 28, 2022, Number 4, Pages 730–743
Download PDF (197 Kb)
Authors and affiliations
Suppose every integer is taken to the power of a fixed integer exponent k ≥ 2 and the remainders of these powers upon division by a fixed integer n ≥ 2 are found. It is natural to ask how many distinct remainders are produced. By building on the work of Stangl, who published the k = 2 case in Mathematics Magazine in 1996, we find essentially closed formulas that allow for the computation of this number for any k. Along the way, we provide an exposition of classical results on the multiplicativity of this counting function and results on the number of remainders that are coprime to the modulus n.
- Modular arithmetic
- Power residues
- Primitive roots
- Geometric series
- Arithmetic functions
2020 Mathematics Subject Classification
- Andreescu, T., Dospinescu, G., & Mushkarov, O. (2017). Number Theory: Concepts and Problems. XYZ Press, Plano, Texas.
- Dummit, D. S., & Foote, R. M. (2004). Abstract Algebra (Third edition). John Wiley and Sons Inc., New York.
- Niven, I., Zuckerman, H. S., & Montgomery, H. L. (1991). An Introduction to the Theory of Numbers (Fifth edition). John Wiley and Sons Inc., New York.
- Stangl, W. D. (1996). Counting Squares in ℤn. Mathematics Magazine, 69(4), 285–289.
- Vinogradov, I. M. (1954). Elements of Number Theory (Fifth edition). Dover Publications Inc., USA.
- Received: 9 April 2022
- Revised: 4 November 2022
- Accepted: 4 November 2022
- Online First: 7 November 2022
Cite this paper
Seraj, S. (2022). Counting general power residues. Notes on Number Theory and Discrete Mathematics, 28(4), 730-743, DOI: 10.7546/nntdm.2022.28.4.730-743.