Primitive Roots

Let n be a positive integer. A primitive root mod n is an integer g such that every integer relatively prime to n is congruent to a power of g mod n. And in dealing with modular arithmetic, cyclic groups, and primitive roots, some clear patterns emerge. For example, the number 3 is a primitive root modulo 7, and we can see its cycling here:

\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}

We can observe this property with integers in general when dealing with powers. And use a neat trick to deduce the last digit of a number. For example, consider the number 7. As we increment the powers of 7, the last digit begins to repeat: 7, 9, 3, 1, and so on:

7^1 ≡ 7
7^2 ≡ 49
7^3 ≡ 343
7^4 ≡ 2401
7^5 ≡ 16807
7^6 ≡ 117649
7^7 ≡ 823543
7^8 ≡ 5764801
7^9 ≡ 40353607

How can we guess the last digit of an extremely large number, like \(7^{3001}\)? As we demonstrated, the last digit repeats every 4 numbers. First we divide our exponent, 3001, by 4.

3001 / 4 = 750, with a remainder of 1

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

Now, what if our number didn't have a remainder? For example, what if we were calculating \(7^{3000}\)? We would take the same steps and divide the exponent by 4, and have 750 without a remainder, which is equivalent to:

\(7^{4×750}\)

And we would then alternatively calculate \(7^{4}\) which is 2401. Thus, the last digit of \(7^{3000}\) is 1.