A power modulo n


Modular arithmetic is a study of the ones digit of integers in functions and calculations. This definition would be incomplete if I restricted my study to base 10 arithmetic, so I open up my choice of base to any natural number of interest. So, equivalently, but more commonly it is said that modular arithmetic is defined as a study of the remainder that results from integer division. With the focus being on integer formulas, polynomials arise as a centerpiece of discussion. And as each polynomial of x is a linear function on powers of x, understanding powers of x in modular arithmetic is primary and paramount. This is why I want to write about and explore this topic.

When reading equations in modular arithmetic, equations are frequently qualified in parentheses (modulo n) or \( \pmod{n} \) for short. So the equals sign actually doesn't mean equal. Instead of equality, we say the left and right sides are congruent \( \pmod{n} \). Congruence truly only represents equality of the least digit base n on either side of the equation. To enhance this distinction, sometimes writers replace the equals sign with an equivalence sign.

The basic definition of modular arithmetic allows me to rearrange a congruence like an equation by parallel operations to both sides. Specifically I may add, subtract or multiply freely to transform congruences. I can also factor, or distribute terms on either side of the congruence without fear.

However, division does not work with modular arithmetic in general. And thinking back to the fourth grade tells me why division is not allowed. When I learned to add, subtract and multiply in longhand fashion, I knew to begin with the ones digits of all the inputs, and this alone could always determine the ones digit of the output. The patterns of carrying out these basic operations work broadly, including if I write the numbers in a different base. Modular arithmetic cares about the least/ones digit in a particular base. If, I covered up all but the last digit of the problem, I could still work out the ones digit of the output. However, the same cannot be said of division. Rather, dividing numbers longhand, begins with the first/greatest digit. Ironically, division is not valid in the equations of modular arithmetic, which is classically considered to be a study of remainders!

Theorem on repeating powers of x modulo n

The key to learning and to modular arithmetic, is repetition. If I understand and apply repetition correctly, I can find patterns and rules to quicken my understanding.

Theorem
\[ \forall n, x \in \mathbb{N}. \exists a, b \in \mathbb{N}. \forall i \in \mathbb{N}_0. b > 0 \land x^{a+i}=x^{a+b+i} \pmod{n} \]

Stated in plain english, the theorem says

  • Any sequence of this kind (increasing powers of x modulo n) must repeat
  • The repetition must have a start, that of \( x^a \)
  • The repetition must begin repeating, that of \( x^{a+b} \)

Proof: For each particular n and x, consider that the infinite integer sequence of \( x^i \in [0,n) \) has only finite possible values (modulo n). I can find the first two such powers in the sequence which are congruent, and define \( a, b \mid x^a = x^{a+b} \), respectively. Further, by induction of simple multiplication of x it can be shown that \( \forall i ≥ 0, x^{a+i} = x^{a+b+i} \) which is to say that the first repeated value is the beginning of the repetition.

I define some functions to collect the minimum values of a and b which satisfy this theorem.

\[ f: \mathbb{N}^2 \mapsto \mathbb{N}, f(n, x) = \min \left \{ a \mid x^{a} = x^{a+b} \pmod{n} \right \} \]
\[ g: \mathbb{N}^2 \mapsto \mathbb{N}, g(n, x) = \gcd \left \{ b \mid b \gt 0 \land x^{a} = x^{a+b} \pmod{n} \right \} \]

One is a descriptor of how many values of \( x^i \pmod{n} \) are singular and unique depending on n and x, and the other is a descriptor of how many values have repeated congruence.

If I vary x while fixing the value of i and n, I discover and may verify that \( x^i = (x+n)^i \pmod{n} \). So I can define related functions that give the minimum values satisfying the theorem independent of x. The beginning of the repetition generalizes to the maximum value, and the first repeat generalizes to the least common multiple of all the repetition sizes.

\[ f: \mathbb{N} \mapsto \mathbb{N}, f(n) = \max \left \{ f(n, x) \right \} \]
\[ g: \mathbb{N} \mapsto \mathbb{N}, g(n) = \text{lcm} \left \{ g(n, x) \right \} \]

If instead I vary n and fix the value of x, I do not have simple repetition, but still I can generalize the functions to find a working repetition size for all values of n ≤ N.

\[ F: \mathbb{N}^2 \mapsto \mathbb{N}, F(N, x) = \max \left \{ f(n, x) \mid n \le N \right \} \]
\[ G: \mathbb{N}^2 \mapsto \mathbb{N}, G(N, x) = \text{lcm} \left \{ g(n, x) \mid n \le N \right \} \]

I can completely generalize to measure the super-pattern that is common to all numbers within a certain size.

\[ F: \mathbb{N} \mapsto \mathbb{N}, F(N) = \max \left \{ f(n, x) \mid n \le N \right \} \]
\[ G: \mathbb{N} \mapsto \mathbb{N}, G(N) = \text{lcm} \left \{ g(n, x) \mid n \le N \right \} \]

Example 1: I write out the powers of 2 and find the modulus of each (remainder when dividing by 3). The repeat starts at 0 in a cycle of 2, so that means \( f(3, 2) = 0 \) and \( g(3, 2) = 2 \).

\[ 2^i = \{ 1, 2, 4, 8, 16, 32, \dots \} \]
\[ 2^i = \{ 1, 2, 1, 2, 1, 2, \dots \} \pmod{3} \]

Example 2: By exploring the values of x up through 10, I can discover that \( f(10) = 1 \) and \( g(10) = 5 \) so I can tell a friend to pick any small integer, and write down its sequence of sequential powers in base 10. Without knowing what was picked, but knowing it is written in base 10, I can immediately tell that the least digit of the fifth power is equal to that of the first power, the last/least digit of the sixth power is equal to that of the second and so on.

So if 3 was picked, the following would be written down.

\[ 3^i = \{ \color{red}{1}, \color{green}{3}, \color{blue}{9}, \color{black}{27}, \color{red}{81}, \color{green}{243}, \color{blue}{729}, \color{black}{2187}, \dots \} \]

If it was 5, the prediction would still be right even though the repetition in that case is more frequent (constant).

\[ 5^i = \{1, 5, 25, 125, 625, 3125, 15625, 78125, \dots \} \]

As stated, for each pair of n and x, I can iterate the integer powers of x, and find the least digit of each answer (base n). Listing out thusly, I can find the pattern of repetition. Two questions need to be answered in each case.

\( f(n, x) \)
How many values of \( x^i \pmod{n} \) are unique?
\( g(n, x) \)
How many values of \( x^i \pmod{n} \) are repeating?

I can keep poking and proding these patterns to find values for these functions. Using the definition of f and g, I may iterate powers of x modulo n to create a list of values until I find the first repeat. For this purpose, I created a calculator that does just that. But might it be possible to find some formulas to deduce values more efficiently? Might there be a pattern to all these patterns? Yes. A little work on some theorems gives me a stained glass window of insight into how these functions behave.

Factoring to repose modular arithmetic

The greatest common divisor lends greatly to the discussion

The basic definition of modular arithmetic allows me to rearrange the congruence like an equation, by addition, subtraction, multiplication and factoring.

\[ x^a = x^{b+a} \pmod{n} \]
\[ x^{b+a} - x^a = 0 \pmod{n} \]
\[ x^a (x^b - 1) = 0 \pmod{n} \]

I may write this fact in terms of the greatest common divisor instead of using modular arithmetic, as follows.

\[ \gcd(n, x^a (x^b - 1)) = n \]
\[ \gcd(x^a, x^b - 1) = 1 \]
\[ \gcd(x^a, n) \gcd(x^b - 1, n) = n \]

So n may be factored into two parts. One factor contains all the factors common with x, and the other factor contains all the factors coprime to x.

\[ \text{factors}_{x}(n) \times \text{coprime}_{x}(n) = n \]
\[ \text{factors}_{x}(n) = \gcd(x^a, n) \]
\[ \text{coprime}_{x}(n) = \gcd(x^b - 1 , n) \]
\[ \gcd (\text{factors}_{x}(n), \text{coprime}_{x}(n)) = 1 \]

The method is to consider the factors of x and n, with purpose of separating n into two factors. One factor contains all the factors common with x, and the other factor contains all the factors coprime to x. Before I continue, let's look at these calculations as lists of sequences.

\[ \text{factors}_{1}(n) = \{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, \dots \} \]
\[ \text{factors}_{2}(n) = \{ 1, 2, 1, 4, 1, 2, 1, 8, 1, 2, 1, 4, 1, \dots \} \]
\[ \text{factors}_{3}(n) = \{ 1, 1, 3, 1, 1, 3, 1, 1, 9, 1, 1, 3, 1, \dots \} \]
\[ \text{factors}_{4}(n) = \{ 1, 2, 1, 4, 1, 2, 1, 8, 1, \dots \} = \text{factors}_{2}(n) \]
\[ \text{factors}_{5}(n) = \{ 1, 1, 1, 1, 5, 1, 1, 1, 1, 5, 1, 1, 1, \dots \} \]
\[ \text{factors}_{6}(n) = \{ 1, 2, 3, 4, 1, 6, 1, 8, 9, 2, 1, 12, 1, \dots \} \]
\[ \text{factors}_{7}(n) = \{ 1, 1, 1, 1, 1, 1, 7, 1, 1, 1, 1, 1, 1, \dots \} \]
\[ \text{factors}_{8}(n) = \{ 1, 2, 1, 4, 1, 2, 1, 8, 1, \dots \} = \text{factors}_{2}(n) \]
\[ \text{factors}_{9}(n) = \{ 1, 1, 3, 1, 1, 3, 1, 1, 9, \dots \} = \text{factors}_{3}(n) \]
\[ \text{factors}_{10}(n) = \{ 1, 2, 1, 4, 5, 2, 1, 8, 1, 10, 1, 4, 1, \dots \} \]
\[ \text{factors}_{11}(n) = \{ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 11, 1, 1, \dots \} \]
\[ \text{factors}_{12}(n) = \{ 1, 2, 3, 4, 1, 6, 1, 8, 9, \dots \} = \text{factors}_{6}(n) \]
\[ \dots \]
\[ \text{coprime}_{1}(n) = \{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, \dots \} \]
\[ \text{coprime}_{2}(n) = \{ 1, 1, 3, 1, 5, 3, 7, 1, 9, 5, 11, 3, 13, \dots \} \]
\[ \text{coprime}_{3}(n) = \{ 1, 2, 1, 4, 5, 2, 7, 8, 1, 10, 11, 4, 13, \dots \} \]
\[ \text{coprime}_{4}(n) = \{ 1, 1, 3, 1, 5, 3, 7, 1, 9, \dots \} = \text{coprime}_{2}(n) \]
\[ \text{coprime}_{5}(n) = \{ 1, 2, 3, 4, 1, 6, 7, 8, 9, 2, 11, 12, 13, \dots \} \]
\[ \text{coprime}_{6}(n) = \{ 1, 1, 1, 1, 5, 1, 7, 1, 1, 5, 11, 1, 13, \dots \} \]
\[ \text{coprime}_{7}(n) = \{ 1, 2, 3, 4, 5, 6, 1, 8, 9, 10, 11, 12, 13, \dots \} \]
\[ \text{coprime}_{8}(n) = \{ 1, 1, 3, 1, 5, 3, 7, 1, 9, \dots \} = \text{coprime}_{2}(n) \]
\[ \text{coprime}_{9}(n) = \{ 1, 2, 1, 4, 5, 2, 7, 8, 1, \dots \} = \text{coprime}_{3}(n) \]
\[ \text{coprime}_{10}(n) = \{ 1, 1, 3, 1, 1, 3, 7, 1, 9, 1, 11, 3, 13, \dots \} \]
\[ \text{coprime}_{11}(n) = \{ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 1, 12, 13, \dots \} \]
\[ \text{coprime}_{12}(n) = \{ 1, 1, 1, 1, 5, 1, 7, 1, 1, \dots \} = \text{coprime}_{6}(n) \]
\[ \dots \]

I now explore how these factors play a role in the pattern of repetition of powers mod n.

Measuring the preambles to the repetitions

Finding the values of \( f(n, x) \), \( f(n) \), \( F(N, x) \) and \( F(N) \)

If \( \text{factors}_{x}(n) \gt 1 \), then \( f(n, x) \gt 0 \), and I can factor \( \text{factors}_{x}(n) \) into powers of primes \( p^i \). And then I may find the corresponding factor \( p^j \) that divides x.

\[ \gcd(\text{factors}_{x}(n), p^{i+1}) = p^{i} \implies \]
\[ \exists j, \gcd(x, p^{j+1}) = p^j \]
\[ \gcd \left ( \frac{x^a}{p^{a j}}p^{a j}, p^i \right ) = p^i \]
\[ \gcd(p^{a j}, p^i) = p^i \]
\[ a j ≥ i \]
\[ a ≥ \left \lceil \frac{i}{j} \right \rceil \]
\[ f(n, x) = \max \{ \left \lceil \frac{i}{j} \right \rceil \mid \gcd(\text{factors}_{x}(n), p^{i+1}) = p^i \land \gcd(x, p^{j+1}) = p^j \} \]

This method of calculating the function is insightful, but it is hard to see the efficiency gains in finding the function value for specific input. The efficiency is realized whenever the number of prime factors of x is small compared to the distance to the first repetition. A clear advantage to this result is in being able to construct a preamble of any size. Choose \( n = B y^r \) and \( x = C y \) to give a preamble of at least r.

Turning now to the second function called f, remember it was defined as the maximum of all the preamble sizes for any x, but depending on n. The aggregation runs over many x, and is not only rooted in the common factors of a single value of x.

To locate this maximum, clearly I want to pick an x which gives the smallest denominator, so \( j=1 \), which is to require x being square-free in the common factor. Now, I cannot pick the other variable i directly, but I can choose the x with the common factor p which gives the greatest value of i. This leads to a simple result of finding the prime factor of n which has the highest power in its unique factorization. That highest power is in fact, the value of the function.

\[ f(n) = \max \{ a \mid \gcd (p^{a+1}, n) = p^a \} \]

Notice how in this function, local maximums are found in the value of a when n is a power of 2, which gives \( f(n) = \log_2 n \) at these maximums. This shows the value of the measure of the super-preamble which generalizes to any x. It is a simple function of N as follows.

\[ F(N) = \left \lfloor \log_2 N \right \rfloor \]

I skipped the other function F which depends on x, to save the best challenge for last. Yet, I notice that when I fix x, the function \( f(n, x) \) has local maximums when n is the smallest in the list of the unique factorization of x into a product of prime powers.

\[ F(N, x) = \left \lfloor log_r N \right \rfloor \]
\[ r = \min \{ p^j \mid \gcd(x, p^{j+1}) = p^j \} \]

Measuring the distances of repetitions

Finding the values of \( g(n, x) \), \( g(n) \), \( G(N, x) \) and \( G(N) \)

To find the repetition size, I may iterate to find the minimum value which has the corresponding factor as follows.

\[ g(n, x) = \min \left \{ b \mid \gcd(x^b - 1, \text{coprime}_{x}(n)) = \text{coprime}_{x}(n) \right \} \]

This method can be more efficient than by calculating all the powers of x until a repetition is realized, because I don't actually have to keep and compare all the prior powers of x until I find the first repetition. Instead, I just change the modulus to its coprime part, and then iterate powers of x until 1 is reached.

My other function of g comes by aggregate of this process using the LCM functon, so that the interval is a valid repetition for every value of x. As it turns out, each x that has common factors to n, has some y that are coprime to n.

\[ y = x \pm \text{coprime}_{x}(n) \]
\[ \gcd(y, n) = 1 \]
\[ \gcd(y^B - 1, n) = n \]
\[ \gcd(x^B - 1, \text{coprime}_{x}(n)) = \text{coprime}_{x}(n) \]
\[ \exists k \ge 1 \ni k g(n) = B \]
\[ \text{lcm} (g(n), B) = B \]

So every cycle of \( x^i \) generated by an x which is not coprime to n, is a divisor of (or equal to) that of some y coprime to n. So the least common multiple that comes from testing the values which are coprime to n will cover all values adequately.

\[ g(n) = \text{lcm} \left \{ b \mid \gcd(x^b - 1, n) = n \land \gcd (x, n) = 1 \right \} \]

This method to determine \( g(n) \) requires factoring of n, testing the values of x that are coprime to n, and computing the least common multiple from these tests.

An interesting fact comes straight from group theory to shed some light on the repetition of powers of x modulo n, when x is coprime to n. I can show that the collection of values coprime to n forms an abelian group modulo n over multiplication. Group properties are demonstrated as follows.

Closure
\[ \gcd(x, n) = 1 \land \gcd(y, n) = 1 \implies \gcd (x \times y, n) = 1 \]
Identity
\[ \gcd(k n + 1, n) = \gcd(1, n) = 1 \]
Inverse
\[ \gcd(x, n) = 1 \implies \]
\[ x y - k n = 1 \]
\[ x y = k n + 1 \]
\[ x y = 1 \pmod{n} \]
\[ \gcd(y, n) = 1 \]
Associativity
Commutativity (Abelian)
By principle of multiplication modulo n.

Furthermore, the order (number of elements) of this Abelian group is given by Euler's totient function \( \phi(n) \), which counts the values \( \pmod{n} \) that must be coprime to n. Each cycle consists of all the values generated by x, so the cycle must be a subgroup. And the order of any subgroup must be a divisor of the order of the group. In all, this brings me to a nice generalization.

\[ g(n) k_n = \phi(n) \]
\[ g(n) \le \phi(n) \]

The value of my super-repetition seems almost within reach as it can now be seen that it must be a divisor of the least common multiple of the values of the totient function.

\[ G(N) K_N = \text{lcm} \left \{ \phi(n) \mid n \le N \right \} \]

The other function G proves a worthy challenge. The definition is basically as follows, provided that for each n, I am mindful to choose the least value that satisfies the equation.

\[ G(N, x) = \text{lcm} \left \{ b \mid \gcd(x^b - 1, \text{coprime}_{x}(n)) = \text{coprime}_{x}(n) \land n \le N \right \} \]

Let's explore the sequences that affect the final value. Firstly, the sequence of one less than the powers of x.

\[ x^b - 1 = (x - 1) \sum_{i=0}^{b-1} x^i \]
\[ x^{k b} - 1 = (x^b)^k - 1 = (x^b - 1) \sum_{i=0}^{k-1} (x^b)^i \]
\[ \gcd (x^b - 1, x^{k b} - 1) = x^b - 1 \]

Having this factorization rule creates a useful chain of logic which generalizes to the LCM of N numbers.

\[ A = \gcd (x^a - 1, A) \]
\[ B = \gcd (x^b - 1, B) \]
\[ C = \text{lcm} (A, B) \]
\[ c = \text{lcm} (a, b) \]
\[ C = \gcd (x^c - 1, C) = C \]

I have glossed over one point, which is whether the least a that satisfies A, and the least b that satisfies B would necessarily give the least c that satisfies C. Due to the guaranteed cycle of repetition, I know that if c satisfies C, then at least c is a multiple of the least k that satisfies C. So supposing c is not the least value that satisfies C, then c is a multiple of k. But I know k would also satisfy A and B. So k must be a multiple of a and of b. But this is a contradiction, because c is larger and is the least common multiple. So I may infer that I may distribute the LCM from the index of the dividend to the divisors without loss as follows.

\[ G(N, x) = \min \left \{ b \mid \gcd(x^b - 1, M(N, x)) = M(N, x) \right \} \]
\[ M(N, x) = \text{lcm} \left \{ \text{coprime}_{x}(n) \mid n \le N \right \} \]

I have distributed the least common multiple to the factors being tested. I can distribute the LCM further to be computed before the coprime filter is applied.

\[ M(N, x) = \text{coprime}_{x} \left ( \text{lcm} \left ( 1, 2, \dots, N \right ) \right ) \]

Describing \( G(N, x) \) in words, I look for the smallest b such that \( x^b - 1 \) is divisible by all numbers not greater than N which are coprime to x. Hold on, this sounds familiar. Could this be?

\[ G(N, x) = g(\mathcal{N}, x) \]
\[ \mathcal{N} = \text{lcm}(1, 2, \dots, N) \]

Repeating Powers Calculator

≤ n ≤ N =

≤ x ≤ X =

Count the values of \( x^i \pmod{n} \) that occur exactly once.
\[ x^a = x^{b+a} \pmod{n} \]
\[ \min(a) = f(n, x) \]
\[ f(n, x) = \max \{ \left \lceil \frac{i}{j} \right \rceil \mid \gcd(\text{factors}_{x}(n), p^{i+1}) = p^i \land \gcd(x, p^{j+1}) = p^j \} \]
Count the values of \( x^i \pmod{n} \) that occur repeatedly.
\[ x^a = x^{b+a} \pmod{n} \]
\[ \min(b) = g(n, x) \]
For a choice of n, the least power i that must be congruent to another \( x^i = x^j \pmod{n} \).
\[ f(n) = \max \{ a \mid \gcd (p^{a+1}, n) = p^a \} \]
For a choice of n, the minimum difference \( j-i \) between congruent powers of \( x^i = x^j \pmod{n} \).
\[ g(n) k_n = \phi(n) \]
\[ F(N, x) = \left \lfloor log_r N \right \rfloor \]
\[ r = \min \{ p^j \mid \gcd(x, p^{j+1}) = p^j \} \]
\[ G(N, x) = g(\mathcal{N}, x) \]
\[ \mathcal{N} = \text{lcm}(1, 2, \dots, N) \]
\[ F(N) = \left \lfloor \log_2 N \right \rfloor \]
\[ G(N) K_n = \text{lcm} \left \{ \phi(n) \mid n \le N \right \} \]
The largest factor of n that is composed of prime factors of x.
\[ \text{factors}_{x}(n) = \gcd(x^a, n) \]
The largest factor of n that is coprime to x.
\[ \text{coprime}_{x}(n) = \gcd(x^b - 1 , n) \]