Journal of Applied Mathematics
Volume 2012 (2012), Article ID 292895, 10 pages
Research Article

On Simple Graphs Arising from Exponential Congruences

Department of Mathematics, University of the Punjab, Lahore 54590, Pakistan

Received 19 March 2012; Revised 17 June 2012; Accepted 3 September 2012

Academic Editor: Maurizio Porfiri

Copyright © 2012 M. Aslam Malik and M. Khalid Mahmood. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.


We introduce and investigate a new class of graphs arrived from exponential congruences. For each pair of positive integers and , let denote the graph for which is the set of vertices and there is an edge between and if the congruence is solvable. Let be the prime power factorization of an integer , where are distinct primes. The number of nontrivial self-loops of the graph has been determined and shown to be equal to . It is shown that the graph has components. Further, it is proved that the component of the simple graph is a tree with root at zero, and if is a Fermat's prime, then the component of the simple graph is complete.