Characterization of power digraphs modulo \(n\). (English) Zbl 1249.11002

The authors assign to each pair of positive integers \(n\) and \(k\geq 2\) a digraph \(G(n,k)\) whose set of vertices is \(Z_{n}=\{0,1,\dots n-1\}\) and for which there exists a directed edge from \(a\in Z_{n}\) to \(b\in Z_{n}\) if \(a^{k}\equiv b \pmod n\). They establish necessary and sufficient conditions such that \(G(n,k)\) has at least one isolated fixed point. Another necessary and sufficient condition on \(n\) and \(k\), such that the digraph \(G(n,k)\) contains exactly two components, is given. A new necessary and sufficient condition for the primality of the Fermat numbers is presented as well.


11A07 Congruences; primitive roots; residue systems
11A15 Power residues, reciprocity
05C20 Directed graphs (digraphs), tournaments
11A51 Factorization; primality
Full Text: EuDML EMIS