A Parlor Trick with Primitive Roots

OK, the title is a bit of a pun -- really, the parlor trick uses elementary number theory. A primitive root modulo n however, is an integer g such that every integer relatively prime to n can be expressed as some power of g modulo n. In other words, g can generate all numbers relatively prime to n through its powers.

When dealing with modular arithmetic, cyclic groups, and primitive roots, we find patterns emerge. For example, we can see the powers of 3 are congruent to a cyclic pattern that repeats with numbers modulo 7, the powers of 3 give: 3, 2, 6, 4, 5, 1 — and then it loops back to 3.

\begin{array}{rcrcrcrcrcr}3^{1}&=&3^{0}\times 3&\equiv &1\times 3&=&3&\equiv &3{\pmod {7}}\\3^{2}&=&3^{1}\times 3&\equiv &3\times 3&=&9&\equiv &2{\pmod {7}}\\3^{3}&=&3^{2}\times 3&\equiv &2\times 3&=&6&\equiv &6{\pmod {7}}\\3^{4}&=&3^{3}\times 3&\equiv &6\times 3&=&18&\equiv &4{\pmod {7}}\\3^{5}&=&3^{4}\times 3&\equiv &4\times 3&=&12&\equiv &5{\pmod {7}}\\3^{6}&=&3^{5}\times 3&\equiv &5\times 3&=&15&\equiv &1{\pmod {7}}\\3^{7}&=&3^{6}\times 3&\equiv &1\times 3&=&3&\equiv &3{\pmod {7}}\\\end{array}

This kind of repetition shows up even in something as simple as the last digit of powers. A neat trick is using this modular property to deduce the last digit of a large integer.

For example, consider the integer 7. As we increment the powers of 7, the last digit begins to repeat: 7, 9, 3, 1, and so on.

Those four numbers repeat over and over again. So, we say that it has a cycle length of four:

\begin{align*} 7^1 &\equiv 7 \\ 7^2 &\equiv 49 \\ 7^3 &\equiv 343 \\ 7^4 &\equiv 2401 \\ 7^5 &\equiv 16807 \\ 7^6 &\equiv 117649 \\ 7^7 &\equiv 823543 \\ 7^8 &\equiv 5764801 \\ 7^9 &\equiv 40353607 \\ \end{align*}

Why do powers repeat like this? The answer is modular arithmetic, again. Similar to how primitive roots generate cycles, our last digit is a product of mod 10 -- and there are only ten possible numbers it can be, so it eventually cycles, too.

So, how can we use this knowledge to do a fun parlor trick, like guess the last digit of an extremely large integer, such as \(7^{3001}\)?

As demonstrated, the powers of 7 have a cycle length of four, so the last digit repeats every 4 numbers. It follows that we first divide our exponent, 3001, by 4.

\[ 3001 \div 4 = 750 \text{, with a remainder of } 1 \]

Since we are left with a remainder, we use it, calculating \(7^{1} = 7\). Thus, we know the last digit of the number \(7^{3001}\) is 7.

But what if the division has no remainder? For example, let's consider \(7^{3000}\). Dividing 3000 by 4 gives:

\[ 3000 \div 4 = 750 \text{, with a remainder of } 0 \]

Since there's no remainder, the exponent is a perfect multiple of the cycle length four, so we look at the last digit of \(7^4\), which equals 2401. The last digit of \(7^{3000}\) is 1.

Patterns like these show up so often in number theory that once you see them, you can’t unsee them.

Abelian Groups

Commutative groups, those groups in which operand order does not change an equation's result, form Abelian groups that commute: "7 × 3 = 3 × 7". When this condition is not satisfied, we say the expression is non-commutative.

Cyclic groups are a special case of commutative Abelian groups—sets that are monogenous—generated by a single element—and invertible with a single operation.

Consider a set that, if we iterated over every other element with a particular operation, we'd be able to derive all of the elements of the set.

For a finite cyclic group, let G be the group, n be the size of the set, and e be the identity element, such that gⁱ = g^j whenever i ≡ j (mod n); like so.

G = {e, g, g², ... , gⁿ⁻¹}

The commutative property also holds over the additive group of ℤ, or the integers, which are isomorphic to any infinite cyclic group. Similarly, the additive group of ℤ/nℤ, integers modulo n, is isomorphic to the finite cyclic group of order n.

Since all cyclic groups commute, they are all abelian groups, and all finitely produced abelian groups are the direct products of cyclic groups.

For example, the powers of 10 form an infinite subset G = {…, 0.001, 0.01, 0.1, 1, 10, 100, 1000, …} over the rational numbers.

With 10 as a generator, set G is a multiplicative cyclic group. For any element a of the group, one can derive log₁₀ a.

Our set contains 10 and 100. The product \(10^1 \cdot 10^2\) is equivalent to \(10^{1+2} = 1000\). Every cyclic group G is Abelian because if \({\displaystyle x}, {\displaystyle y}\) are in \({\displaystyle G}\), then:

\( {\displaystyle xy=a^{m}a^{n}=a^{m+n}=a^{n}a^{m}=yx}\)

This homomorphic property is relevant in cryptography. It's also useful for computing commitments. For example, we can perform operations to verify information, like so. Let m be a message and r be a random value:

\( {\displaystyle C(m_{1},r_{1})\cdot C(m_{2},r_{2})=C(m_{1}+m_{2},r_{1}+r_{2})}\)

That is to say, with this special property, one could compute and verify the sums of values without knowing the actual values being committed.