Writing Moduler Exponentiation In Terms Of Other Roots (Related To Primitive Roots?)

Question

First, I am not a mathematician; my highest math courses were undergrad linear algebra and ODEs a decade ago, plus some additional learning on my own since then. I welcome correction on my terminology or suggestions of resources to study.

I have been playing with modular exponentiation. It's been known for centuries that some of the resulting cycles can be written in terms of others, with certain roots being "primitive" in that other cycles can be represented in terms of the primitive roots.

What I don't understand is why some cycles are obviously derivable from certain roots but non-obviously derivable from others. For example, take 2, 8, and -10 $\mod 36$:

2:  [2 4 8 16 -4 -8 -16 4 ...]
8:  [8 -8 8 ...]
-10: [-10 -8 8 -8...]

The relationship between 2 and 8 is obvious, because $8^n \mod 36 ≡ (2^3)^n \mod 36$.

What is not obvious to me is the relationship between 8 and -10 $\mod 36$, and yet $8^n \mod 36 ≡ (-10^3)^n \mod 36$. The only relationship I can see between 8, -10, and $-10^3$ is that $10^3 = 8 * 5^3$, but I don't see how that would make it obvious that 8's cycle can be derived from -10's.

More generally, is it possible to explore and discover these relationships without exhaustively creating the modular multiplication table $mod n$? Similar to how one could easily know that the 8 cycle can be represented in terms of the 2 cycle?

Answer 1

First, the precise question. Notice that $-10 \equiv 26 = 8 + 3 \cdot 6 \bmod 36$. Thus $(-10)^n \equiv (8 + 3 \cdot 6)^n \bmod 36$. For $n \geq 2$, the binomial expansion indicates that $(-10)^n \equiv (8^n + 8^{n-1} \cdot 3 \cdot 6 \cdot C_{n-1} + 0 + \cdots + 0) \equiv 8^n \bmod 36$, as $8 \cdot 3 \cdot 6 \equiv 0 \bmod 36$.

This is why $(-10)^n \equiv 8^n \bmod 36$ for $n \geq 2$

---

A very general way to think of this type of problem is locally, each prime individually, with the Chinese Remainder Theorem. There is a correspondence between integers mod $36$ and pairs $(x, y)$ where $x$ is mod $4$ and $y$ is mod $9$. This is the essence of the Chinese Remainder Theorem in this case.

For prime powers like $4$ and $9$, there are primitive roots, and all exponentiation can be put in terms of powers of these primitive roots. Once you have expressed your exponentiation in terms of these primitive roots, it is straightforward to relate exponentiation of different integers in terms of the powers of the primitive roots locally for each prime. Then you can again combine with the Chinese Remainder Theorem to deduce more general relationships.

This requires some work, though. This doesn't necessarily require making the whole multiplication table, but it does require having primitive roots and knowing how to express integers in terms of these roots --- and this frequently does entail having a multiplication table.

Answer 2

Answering your question about cycles. the You are considering the Cyclic Group ${Z_{36}^*}$,

• Primitive roots are the elements of ${Z_n}$ here n=36. iff gcd(n,k)=1 for integer k.
• If d is a positive divisor of n, the number of elements of order d in a cyclic group of order n is ${\phi(d)}$.
• Now, what you are trying to find is the relation between 8 and 26 (-10).
• Here we are dealing with multiplicative Group ${Z_{36}^*}$, you can check the relation by ${8^n}$ and ${26^{3n}}$ where ${n \in N}$, ${26^3 \equiv 8 (mod36)}$
• because ${gcd(8,36,26^3)=4}$, we can divide equation by 4, we'll have new equation, ${2 \equiv (13)^3 \cdot 2 (mod 9)}$ , where ${13^3 \equiv 1 (mod9)}$ so as (mod36), this means original equation has solution and most importantly both are in same coset generated by (mod36).

Answer 3

CRT yields a ring isomorphism $\, \Bbb Z_{36}\cong \Bbb Z_4\times \Bbb Z_9\,$ via $\,n\mapsto (n\bmod 4,\,n\bmod 9).\,$ Here $\Bbb Z_4\times \Bbb Z_9$ is a product ring, i.e. the set of pairs $\,(a_1,a_2),\ a_1\in \Bbb Z_4,\, a_2\in \Bbb Z_9$ with pointwise sum and product

$$ \begin{align} (a_1,a_2) + (b_1,b_2) &\,=\, (a_1+ b_1,\ a_2 + b_2)\\[.2em] (a_1,a_2)\ \cdot\ (b_1,b_2) &\,=\, (a_1 \ \cdot\ b_1,\ a_2\ \cdot\ b_2)\\[.2em] \Longrightarrow\ \ (a_1,\,a_2)^n\! &\,=\, (a_1^n,\ a_2^n) \end{align}\qquad$$

and where equality is pointwise congruence, i.e.

$$(a_1,a_2) = (b_1,b_2) \iff \begin{align} &a_1\equiv b_1\!\!\!\pmod{\!4}\\ \&\ \ &a_2\equiv b_2\!\!\!\pmod{\!9}\end{align}\qquad$$

Notice $\ 8\in\Bbb Z_{36}\,$ maps to $\,(0,-1),\,$ by $\,8\equiv 0\pmod{\!4},\ \ 8\equiv -1\pmod{\!9}$
and $\,{-}10\in \Bbb Z_{36}\,$ maps to $\,(2,-1)$.

Therefore $\,8^n$ maps to $\,(0,-1)^n = (0^n,(-1)^n) = (0,(-1)^n)$
and $\ (-10)^n\,$ maps to $\,(2,-1)^n = (\color{#c00}{2^n},(-1)^n) = (\color{#c00}0,(-1)^n)\,$ for $\,n\ge 2\,$ by $\,\color{#c00}{2^n\equiv 0}\pmod{\!4}$

So for $\,n\ge 2\,$ the CRT isomorphism maps $\,8^n\,$ and $\,(-10)^n\,$ to the same element, hence they must also be the same element in $\,\Bbb Z_{36},\,$ i.e congruent $\!\bmod 36,\,$ since an isomorphism is in particular a bijection of sets.

You could also prove the same without using CRT, i.e. show that $\,8^n\equiv (-10)^n\,$ mod $\,4\,$ & mod $\,9\,$ for $\,n\ge 2,\,$ so $\,8^n-(-10)^n\,$ is divisible by both $\,4$ & $9\,$ so also by $\,{\rm lcm}(4,9) = 4\cdot 9 = 36,\,$ hence $\,8^n\equiv (-10)^n\pmod{\!36}\,$ too. But this yields less insight than does using CRT.

Or we can replace CRT by a handy operational form: MDL = mod Distributive Law

$$\begin{align} \text{applying}\,\ \ \color{#c00}ab\bmod \color{#c00}ac\, =&\,\ \color{#c00}a(b\bmod c)= \text{MDL to factor out }\color{#c00}{a=4}\ \rm below\\[.3em] n\ge 2\,\Rightarrow\, \color{#c00}4\mid 8^n,10^n\,\Rightarrow\! &\ \ \ \ \ \ 8^n-(-10)^n\ \bmod 9(\color{#c00}4)\\[.3em] = &\,\ \color{#c00}4\!\left[\dfrac{{8^n-(-10)^n}^{}}4\bmod 9\right]\\[.2em] =&\,\ 4\,[\color{#0a0}0],\,\ {\rm by} \bmod 9\!:\ 8^n\!-(-10)^n\equiv (-1)^n\!-(-1)^n\equiv \color{#0a0}0\end{align}\qquad$$