Counting general power residues

Samer Seraj
Notes on Number Theory and Discrete Mathematics
Print ISSN 1310–5132, Online ISSN 2367–8275
Volume 28, 2022, Number 4, Pages 730–743
DOI: 10.7546/nntdm.2022.28.4.730-743
Full paper (PDF, 197 Kb)

Details

Authors and affiliations

Samer Seraj  
Existsforall Academy
Mississauga, Ontario, Canada

Abstract

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.

Keywords

• Modular arithmetic
• Power residues
• Primitive roots
• Geometric series
• Arithmetic functions

2020 Mathematics Subject Classification

• 11A15
• 11A07
• 11A25

References

1. Andreescu, T., Dospinescu, G., & Mushkarov, O. (2017). Number Theory: Concepts and Problems. XYZ Press, Plano, Texas.
2. Dummit, D. S., & Foote, R. M. (2004). Abstract Algebra (Third edition). John Wiley and Sons Inc., New York.
3. 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.
4. Stangl, W. D. (1996). Counting Squares in ℤ_n. Mathematics Magazine, 69(4), 285–289.
5. Vinogradov, I. M. (1954). Elements of Number Theory (Fifth edition). Dover Publications Inc., USA.

Manuscript history

• Received: 9 April 2022
• Revised: 4 November 2022
• Accepted: 4 November 2022
• Online First: 7 November 2022