10.5 Order and period finding

Consider the function a^k on whole numbers k for a fixed a in N greater than 1. For example, if a = 3 then the first 12 values are

As we look at larger exponents k, the values of 3^k will just get larger and larger. If we instead use modular arithmetic as we saw in section 3.7 ^k cannot get arbitrarily large. For example, modulo M = 13, the values we get are

Working modulo M = 16 yields

Finally, for modulo M = 22 we get

In each case, the sequence starts repeating. That is, the sequences, and hence the functions, are periodic. If we define f_a(x) = a^x mod M for a coprime to M, then the smallest positive integer r such that f_a(x) = f_a(x + r) for all x is called the period of f_a.

Question 10.5.1

What happens when we work modulo M = 23, 24, and 25?

For M = 13 in the first example, the period r = 3. For M = 16, r = 4. In the final example...