Array Rotation: Dolphin Algorithm: Modular Arithmetic

[This page is auto-generated; please prefer to read the article’s PDF Form.]

Modular Arithmetic

Please refer to the proof of theorem 2 in article titled Multiples of an Integer Modulo Another Integer [3]. Based on that, we can write the following theorem:

Theorem 1. For any integers a,n with n > 0, a mod n≠0, and g = gcd(a,n), denote (ai) mod n as v_i for all integers i ≥ 0, and n∕g as t. Then:

v₀,v₁,v₂,…,v_t−1 are all distinct, and form the set
G = {0,g,2g,…,((n∕g) − 1)g},
for any integer j ≥ 0, v_t+j = v_j. That is, in the sequence of v_i values, the subsequence (v₀,v₁,v₂,…,v_t−1) keeps repeating.

Note that we did not claim anything about which value v_i maps to which value in G. Further in this theorem, what can we say about values of the form (ai + b) mod n, for some integer b ≥ 0 ? Note,

From theorem 1, we know that the v_i values only belong to the set G. Inspecting the set G, we know that if 0 ≤ b < g, then 0 ≤ (v_i + b) < n, and so:

That is, the sequence of values (ai + b) mod n is obtained simply by adding b to each element in the sequence of values (ai) mod n. We can write the following conclusion using theorem 1:

Corollary 2. For any integers a,b,n with n > 0, 0 ≤ b < g, a mod n≠0, and g = gcd(a,n), denote (ai + b) mod n as v′_i for all integers i ≥ 0, and n∕g as t. Then:

for all integers i ≥ 0, v′_i = (ai) mod n + b,
v′₀,v′₁,v′₂,…,v′_t−1 are all distinct, and form the set
G_b = {b,g + b,2g + b,…,((n∕g) − 1)g + b},
for any integer j ≥ 0, v′_t+j = v′_j. That is, in the sequence of v′_i values, the subsequence (v′₀,v′₁,v′₂,…,v′_t−1) keeps repeating.

The symbols of a,n,i,j,g used in above theorems have been chosen to match those in the referred proof of [3]; they do not correspond to other objects of this article.