Prove that if is the -cycle , then for all , , where is the least positive residue of mod . Deduce that .
We proceed by induction on . Note that the least positive residue of mod is precisely the (unique) remainder satisfying , given by the Division Algorithm.
The base case follows from the definition of cycle notation; either , so and we have , or , so that and we have .
Now suppose the conclusion holds for 1 and for some with . Then we have , where p is the least positive residue of mod m, and the least positive residue of mod m; say with and with . Solving the second equation for and substituting into the first, we have , and by the uniqueness part of the Division Algorithm, is in fact the least positive residue of mod m. Thus, by induction, the conclusion holds for all .
Note in particular that for all ; hence . Moreover, if , since in particular, ; if then we have mod m, a contradiction. Hence .