The structure of digraphs associated with the congruence $x^k\equiv y \pmod n$

summary:We assign to each pair of positive integers $n$ and $k\ge 2$ a digraph $G(n,k)$ whose set of vertices is $H=\{0,1,\dots ,n-1\}$ and for which there is a directed edge from $a\in H$ to $b\in H$ if $a^k\equiv b\pmod n$. We investigate the structure of $G(n,k)$. In particular, upper bounds are given for the longest cycle in $G(n,k)$. We find subdigraphs of $G(n,k)$, called fundamental constituents of $G(n,k)$, for which all trees attached to cycle vertices are isomorphic