Skip to Main Content

Mathematics of Computation

Published by the American Mathematical Society since 1960 (published as Mathematical Tables and other Aids to Computation 1943-1959), Mathematics of Computation is devoted to research articles of the highest quality in computational mathematics.

ISSN 1088-6842 (online) ISSN 0025-5718 (print)

The 2020 MCQ for Mathematics of Computation is 1.78.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.


The self-power map and collecting all residue classes
HTML articles powered by AMS MathViewer

by Catalina V. Anghel PDF
Math. Comp. 85 (2016), 379-399 Request permission


The self-power map is the function from the set of natural numbers to itself which sends the number $n$ to $n^n$. Motivated by applications to cryptography, we consider the image of this map modulo a prime $p$. We study the question of how large $x$ must be so that $n^n \equiv a \bmod p$ has a solution $1 \le n \le x$, for every residue class $a$ modulo $p$. While $n^n \bmod p$ is not uniformly distributed, it does appear to behave in certain ways as a random function. We give a heuristic argument to show that the expected $x$ is approximately $p^2\log \phi (p-1)/\phi (p-1)$, using the coupon collector problem as a model. We prove the bound $x <p^{2-\alpha }$ for sufficiently large $p$ and a fixed constant $\alpha > 0$ independent of $p$, using a counting argument and exponential sum bounds.
Similar Articles
Additional Information
  • Catalina V. Anghel
  • Affiliation: Department of Mathematics, University of Toronto, 40 St. George St., Toronto, ON M5S 2E4, Canada
  • Email:
  • Received by editor(s): April 21, 2013
  • Received by editor(s) in revised form: April 22, 2014
  • Published electronically: May 12, 2015
  • © Copyright 2015 American Mathematical Society
  • Journal: Math. Comp. 85 (2016), 379-399
  • MSC (2010): Primary 11A07, 11K45, 11T23; Secondary 94A60
  • DOI:
  • MathSciNet review: 3404454