## Departmental PhD Thesis Exam – Catalina V. Anghel

Everyone is welcome to attend.  Refreshments will be served in the Math Lounge before the exam.

Wednesday, December 5th, 2012 @ 2:00 PM

BA 6183, 40 St. George Street

PhD Candidate:  Catalina V. Anghel

Thesis Title: The self-power map and its image modulo a prime

http://www.math.toronto.edu/~canghel/SelfPowerMapCAnghel.pdf

Thesis Abstract:

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 with $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-1)^2\log \phi(p-1)/\phi(p-1)$, using the coupon collector problem as a model. Rigorously, 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.

Additionally, we prove nontrivial bounds on the number of solutions of $n^n \equiv a \bmod p$ for a fixed residue class $a$ when $1 \le n \le x$, extending the known bounds when $1 \le n \le p-1$.