Proof. We will represent the value (ak) mod n, for any integer k (not necessarily in ℤn), as v_k.

For any integer a, say a′ = a mod n, and so a′ ∈ ℤn. Thus, any value v_i = (ai) mod n = ((a mod n)i) mod n = (a′i) mod n. That means, the set of values obtained for a and a′ are exactly the same.

Thus, for the purpose of our proof we can assume a ∈ ℤn, and the theorem will stand proved for any integer a.

Say, t is the least positive integer such that v_t = 0. That is,

Since a ∈ ℤn and a mod n≠0, so a > 0. Also, t > 0, implying at > 0. Say m > 0 is an integer such that nm = at. But this is a positive common-multiple of a and n. Since we are looking for the least such t, so:

Note, g being the gcd of a and n, n∕g is an integer. The desired value t is n∕g. If g > 1, t = n∕g is in ℤn.

But if g = 1, t = n, i.e. t is not in ℤn. That means, (ai) mod n = 0 is attained only for i = 0 in ℤn.

Now, consider all i < t, i.e. i = 0,1,2,…,t− 1. Say, for some i₁ and i₂ among these, with i₁ < i₂, we obtain same value of v_i. Then,

Say t′ = i₂ − i₁. So, (at′) mod n = 0. But 0 < (i₂ − i₁) < t. So, 0 < t′ < t, which is impossible since t is the least positive integer with (at) mod n = 0. Hence, for all i < t in ℤn, values v_i are distinct. Note that when g = 1, in which case t = n, all v_i for i = 0,1,2,…,n − 1 are distinct.

Now, for any positive integer j, consider v_t+j: v_t+j = (a(t+j)) mod n = (at+aj) mod n = ((at) mod n+aj) mod n = (aj) mod n = v_j.

That is, v_t+1 = v₁,v_t+2 = v₂,…,v_t+t = v_t = 0 = v₀. The cycle of v_k values: (v₀ = 0),v₁,v₂,…,v_t−1, consisting of t distinct elements, keeps repeating for all integers k = t onward. That means, for i ∈ ℤn, values v_i consist of this t = n∕g sized cycle repeated g times.

We can now conclude that set A contains t = n∕g elements. What are these elements?

Consider any element (ai) mod n. (ai) mod n is nothing but ai − nq for some integer q (Division Theorem). Since g∣a and g∣n, so: g∣(ai − nq) ⇔ g∣((ai) mod n).

So, each element v_i of set A is a multiple of g. Also, 0 ≤ v_i ≤ n − 1 for any element v_i of A (they are modulo n), and there are n∕g such elements. In the sequence of n consecutive integers 0,1,2,…,n− 1 (where all v_i belong), there are total n∕g multiples of g: 0,g,2g,…,((n∕g) − 1)g.

So, the total n∕g distinct elements of A, each being a multiple of g, can only be: G = {0,g,2g,…,((n∕g) − 1)g}. □

Proof. Consider the set A′ = {(ai) mod n : i ∈ ℤn} which is same as G = {0,g,2g,…,((n∕g) − 1)g}, due to Theorem 2.

For any integer i ∈ ℤn, an element in set A, (ai + b) mod n, will equal ((ai) mod n + b) mod n. But (ai) mod n is an element in set A′. So, (considering every i ∈ ℤn) all the elements of A can simply be obtained by taking all elements of A′, adding b to each and taking mod n. But all elements of A′ are the set G. So, set A can be obtained from set G, such that each element k in G is modified to (k + b) mod n.

Now, for any two distinct integers j and k in ℤn, we must have (j + b) mod n≠(k + b) mod n. So, modifying the elements of G (which is a subset of ℤn) as above does not make any two of them equal. That is, A consists of same number of elements as are in G, which is n∕g.

In other words, A consists of: b,b+g,b+2g,…,b+((n∕g)−1)g, all taken mod n. □

Proof. From Corollary 3, and g = 1, set A consists of below values after taking mod n: b,b + 1,b + 2,…,b + (n − 1).

But any set of n consecutive integers, when every element is taken mod n, will give the set of integers: {0,1,2,…,n − 1}. So, set A will also be same as {0,1,2,…,n − 1}. □