Subscribe to the weekly news from TrueShelf

## Graphs and Fermat's Little Theorem

Given a prime number $n$, let $\mathbb{Z}_n$, denote the set of congruence classes of integers modulo $n$. Let $a$ be a natural number having no common prime factors with $n$; multiplication by $a$ defines a permutation of $\mathbb{Z}_n$. Let $l$ be the least natural number such that $a^l \equiv a\ \mbox{mod}\ n$.

1. A functional digraph, of a function $f: A \rightarrow A$, is a digraph with vertex set $A$ and edge set {$(x,f(x)) : x \in A$}. Let $G$ be the functional digraph with vertex set $\mathbb{Z}_n$ for the permutation defined by multiplication by $a$. Prove that all cycles in $G$ (except the loop on $n$) have length $l-1$.

2. Conclude from (1) that $a^{n-1} \equiv 1\ \mbox{mod}\ n$.

Source: from book "Introduction to Graph Theory"

0

0

0

0

0

0

0

0

0

0