On simple graphs arising from exponential congruences (Q1760630)

Summary: We introduce and investigate a new class of graphs arrived from exponential congruences. For each pair of positive integers \(a\) and \(b\), let \(G(n)\) denote the graph for which \(V = \{0, 1, \dots, n - 1\}\) is the set of vertices and there is an edge between \(a\) and \(b\) if the congruence \(a^x \equiv b\pmod n\) is solvable. Let \(n = p^{k_1}_1 p^{k_2}_2 \cdots p^{k_r}_r\) be the prime power factorization of an integer \(n\), where \(p_1 < p_2 < \cdots< p_r\) are distinct primes. The number of nontrivial self-loops of the graph \(G(n)\) has been determined and shown to be equal to \(\Pi^r_{i=1}(\varphi(p^{k_i}_i)+ 1)\). It is shown that the graph \(G(n)\) has \(2^r\) components. Further, it is proved that the component \(\Gamma_p\) of the simple graph \(G(p^2)\) is a tree with root at zero, and if \(n\) is a Fermat's prime, then the component \(\Gamma_{\phi(n)}\) of the simple graph \(G(n)\) is complete.