Why a Pattern Repeats?

1. Introduction

We consider two problems:

Problem 1: compute the $n$-th Fibonacci number modulo $m$.

Recall that the Fibonacci sequence is defined as follows: $F_0=0, F_1=1$ and $ F_{n+2}=F_{n+1}+F_n$. For example, $m=3$, the Fibonacci sequence $\pmod3$ is: $0, 1, 1, 2, 0, 2, 2, 1, 0, 1, 1, 2, 0, 2, 2, 1, …$

Another example, for $n=2816213588 , m=239$, $F_{2816213588}$ is extremely large and would require hundreds pages to write it down, but $F_{2816213588} \pmod{239} = 151$.

Problem 2 (from Codility.com): Cyclic Rotation

An array A consisting of $n$ integers is given. Rotation of the array means that each element is shifted right by one index, and the last element of the array is moved to the first place. For example, the rotation of array A = [3, 8, 9, 7, 6] is [6, 3, 8, 9, 7] (elements are shifted right by one index and 6 is moved to the first place).

The goal is to rotate array A K times; that is, each element of A will be shifted to the right K times.

Write a function:

def solution(A, K)

that, given an array A consisting of $n$ integers and an integer K, returns the array A rotated K times.

For example, given A = [3, 8, 9, 7, 6] and K = 3, the function should return [9, 7, 6, 3, 8]. Three rotations were made:

[3, 8, 9, 7, 6] -> [6, 3, 8, 9, 7]
[6, 3, 8, 9, 7] -> [7, 6, 3, 8, 9]
[7, 6, 3, 8, 9] -> [9, 7, 6, 3, 8]

These two problems are not difficult, but we need an efficient algorithm to deal with large $n$. The solutions are easily found online and the key observation in both problems is that, the pattern will repeat after certain steps.

In this post, I want to step back from the algorithms and ask a more conceptual question: Why must repetition occur at all? Rather than treating these as isolated tricks, we will see that both problems are governed by the same underlying mechanism. By reframing them in the language of group theory, repetition stops being a coincidence and becomes inevitable – a direct consequence of iterating a symmetry in a finite world. This unified viewpoint not only explains why patterns repeat, but also reveals a simple and powerful principle that applies far beyond these two examples.

2. The group-theoretic view

First of all, what is a group? A group is a collection of objects (or a set) together with a rule (i.e. operation) for combining them, such that:

you can always combine two objects and stay in the collection,
there is a “do nothing” element (also called neutral element)
every action can be undone.

A typical example of group is $ \mathbb{Z}_n=\{0, 1, 2, …, n-1\}$. The operation corresponding to this group is addition modulo $n$. In other words, $ \mathbb{Z}_n$ consists of all possible remainders when diving an integer by $n$. For example, $ \mathbb{Z}_5=\{0, 1, 2, 3, 4\}$, the neutral element is $0$. In this group:

$3+4= 7 = 2 \pmod5$
$4+1= 5 =0 \pmod5$
$1+2= 3 \pmod5$

Let $ G$ be a group with operation $ \ast$. Then the automorphism group of $ G$, denoted by $ \mathrm{Aut}(G)$ consists of functions $ \phi: G \rightarrow G$ such that

$\phi$ preserves group structure: $ \phi(x\ast y)=\phi(x) \ast \phi(y)$
$\phi$ is bijective (reversible); i.e., the inverse $\phi^{-1}$ exists.

The neutral element of $ \mathrm{Aut}(G)$ is the identity function $id$, which sends every $ x \in G$ to itself (“do nothing” function). For $ \phi \in \mathrm{Aut}(G)$, we write

\[ \phi^k =\underbrace{\phi \circ \phi \dots \circ \phi}_{k \; \textrm{times}}\]

If for certain $k, \;\; \phi^k=id$, then $ \phi^{k+1}=\phi, \phi^{k+2}=\phi^2, \dots$ That’s when the action starts repeating. The fact that the patterns in both problem are periodic is no coincidence. The key principle lies in this theorem in group theory:

If $ G$ is a finite group and $ \phi \in \mathrm{Aut}(G)$, then

\[ \exists k \geq 1 \; \text{such that} \; \phi^k=id \]

Let me explain in more details why both problems share the same structure.

Problem 1: for the Fibonacci problem , we consider the group $ G=\mathbb{Z}_m \times \mathbb{Z}_m$. For each $ n$ , we track the state as a pair $ (F_n, F_{n+1}) \in G$. We define $ \phi: G \rightarrow G$ as

$ \phi(x,y)=(y,x+y)$

It’s easy to see that $\phi$ is an automorphism since it is structure-preserving and reversible:

$ \phi\big( (x,y)+(x’,y’) \big)=(y+y’, x+x’+y+y’)=\phi(x,y)+\phi(x’,y’)$
$ \phi^{-1}(u,v)=(v-u,u)$

Now starting with $ v_0:=(0,1) \in G$, Fibonacci pairs can be seen as :

$ \phi^n(v_0)=(F_n, F_{n+1}) \pmod m$

Thus, from the theorem we know that there is some $k$ such that $ \phi^k=id$, which implies that

\[ (F_k, F_{k+1}) =\phi^k(v_0)=id(v_0)=v_0=(0,1)\]

This means the Fibonacci recursion $\pmod m$ restarts, and $ F_{n+k}=F_n \pmod m$ for all $n$.

Problem 2: for the array rotation, we let$ G=\mathbb{Z}_n=\{0, 1, 2, …, n-1\}$ where $n$ is the length of the array A. The rotation is actually an automorphism $ \sigma: G \rightarrow G$ defined as

$ \sigma(i)=i+1$

That is, each index is shifted by $1$ to the right. In particular, $ \sigma(n-1)=n=0 \pmod n$. For the same reason, the rotation becomes $ id$ after some iterations and in this case $ \sigma^n=id$. I.e., the array will return to its original state after $n$. rotations.

3. The solutions

To illustrate the theory, I present my solutions below.

			
### PROBLEM 1
def fibo_huge_fast(n, m):
    # naive function
    def fibo_huge_naive(n, m):
        if n <= 1:
            return n
        previous = 0
        current = 1
        for _ in range(n - 1):
            previous, current = current % m, (previous + current) % m
        return current % m
    # find the period
    def p(m):
        i = 1
        while True:
            if fibo_huge_naive(i, m) == 0 and fibo_huge_naive(i+1,m)==1:
                return i
            i = i + 1
    # combine 2 functions
    r = n % p(m)
    return fibo_huge_naive(r, m)

		

For the array rotation problem, since we know $\sigma^n=id$, the result of K rotations is the same as K % n rotations.

			
### PROBLEM 2
def CyclicRotation(A,K):
    n=len(A)
    B=A.copy()
    for i in range(n):
        B[(i+K)%n]=A[i]
    return B

		

4. Conclusion

At first glance, Fibonacci numbers modulo $m$ and array rotation look like unrelated problems. One involves number sequences, the other simple data manipulation. But at a deeper level, they are governed by the same mathematical principle:

When a reversible operation is repeatedly applied inside a finite group, the operation will be periodic (repeat the pattern after some certain steps).

Group theory gives a precise language for this idea. In both cases, we are iterating a group automorphism – a symmetry of a finite structure. Finiteness leaves no room for infinite novelty, and reversibility prevents collapse. The result is a cycle.

From a programming perspective, this observation is often all you need: the process will repeat, so large $n$ can be reduced modulo the period and brute-force simulation can be avoided. From a mathematical perspective, one can go further. For both problems, there exist explicit formulas to determine the exact length of the cycle $k$:

in the Fibonacci case, this is known as the Pisano period
in the array rotation case, it is given by the order of the cyclic permutation.

These results are classical and well understood, but the discussion lies beyond the scope of this post.