Subscribe to the weekly news from TrueShelf

0

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"

Related Content