A friend of mine recently got me interested in

problem 188 in Project Euler. I had given it a cursory glance before, but I didn't realize that I already possessed all the tools needed to solve it. In fact, all that's needed is some elementary number theory. I'll get started on a method to solve the problem, but I won't finish it, so the reader may enjoy the experience of solving the problem himself/herself.

To begin with this problem, the concept of

order must be defined for two integers a and m where $$gcd(a, m) = 1$$.

$$ord_{m}a$$ is the least positive integer $$e$$ such that $$a^e \equiv 1 \pmod{m}$$.

But just because we have defined $$e$$ like so, it does not mean $$e$$ always exists. That must be proven.

# Proposition 1

If $$gcd(a, m) = 1$$, then $$ord_{m}a$$ always exists.

# Proof

Let $$a$$, $$k$$, $$m$$ be positive integers with $$gcd(a, m) = 1$$. Now let $$E_{m}=\{k\ |\ a^k \equiv 1 \pmod{m}\ \}$$. Since $$gcd(a, m) = 1$$, we have by

Euler's theorem that $$a^{\phi(m)} \equiv 1\pmod{m}$$, where $$\phi(m)$$ is Euler's

totient function. Since $$\phi(m) \in E_{m}$$, the set is non-empty, and therefore contains a least element by the

well ordering principle. This least element is $$ord_{m}a$$.

# Proposition 2

$$a^k \equiv 1 \pmod{m}$$ if and only if $$e|k$$ where $$e = ord_{m}a$$.

# Proof

For the forward direction first suppose $$a^k \equiv 1 \pmod{m}$$. Then $$k=eq+r$$ with $$e > 0$$ and $$0 \le r < e$$ by

Euclid's division lemma.

Therefore:

$$a^k \equiv a^{eq+r} \equiv a^{eq}a^r \equiv a^{r}a^{eq} \equiv a^{r}(1)^q \equiv a^r \equiv 1 \pmod{m}$$

Now, since $$e$$ is, by definition, the least positive integer such that $$a^e \equiv 1 \pmod{m}$$, if $$r < e$$ and $$a^r \equiv 1 \pmod{m}$$ as well, it must be the case that $$r = 0$$. Therefore, $$k = eq+r = eq+0 = eq$$, implying $$e|k$$.
For the opposite direction, suppose that $$k=eq$$. Then:
$$a^k \equiv a^{eq} \equiv (a^e)^q \equiv 1^q \equiv 1 \pmod{m}$$.

Proposition 3

$$a^i \equiv a^j \pmod{m}$$ if and only if $$i \equiv j \pmod{e}$$, where $$e = ord_{m}a$$.

# Proof

Since $$gcd(a, m) = 1$$, $$gcd(a^k, m) = 1$$ as well. Therefore, $$a^k$$ must have a modular inverse; and in particular, so does $$a^j$$:

$$a^i \equiv a^j \pmod{m}$$

$$a^{i}a^{-j} \equiv a^{j}a^{-j} \pmod{m}$$

$$a^{i-j} \equiv a^0 \pmod{m}$$

$$a^{i-j} \equiv 1 \pmod{m}$$

Since $$a^{i-j} \equiv 1 \pmod{m}$$, it must be the case that $$e|i-j$$ by the proposition #2. Therefore $$i-j = eq$$, or $$i = eq + j$$. It follows that $$i \equiv j \pmod{e}$$.

For the other direction, assume that $$i \equiv j \pmod{e}$$, or that $$e|i-j$$. Then $$eq=i-j$$ and $$a^{eq} \equiv a^{i-j} \equiv 1 \pmod{m}$$. This implies that $$a^i \equiv a^j \pmod{m}$$.

Armed with this information it is much easier to solve #188.

# What is 3 ↑↑ 4 (mod 1000)?

This problem is asking for the last three digits of $$3 \uparrow\uparrow 4$$, and as expected, we don't need to explicitly calculate $$3 \uparrow\uparrow 4$$. Instead, we would rather find some $$j$$ such that $$3 \uparrow\uparrow 4 \equiv 3^j \pmod{1000}$$, where $$j$$ is some much smaller number. Luckily, the last proposition tells us that this $$j$$ satisfies $$j \equiv 3 \uparrow\uparrow 3 \pmod{ord_{1000}3}$$.

But now the problem remains to calculate $$3 \uparrow\uparrow 3 \pmod{ord_{1000}3}$$. But instead of calculating this directly, we would rather find some $$k$$ such that $$3 \uparrow\uparrow 3 \equiv 3^k \pmod{1000}$$, where $$k$$ is some much smaller number. Happily enough, we can apply the last proposition yet again, and discover that $$k$$ satisfies $$k \equiv 3 \uparrow\uparrow 2 \pmod{ord_{1000}3}$$.

But now $$3 \uparrow\uparrow 2 = 3^3$$, and this is rather easy to calculate (actual calculation left to the reader).

# Moving forward

The only thing that stands between the reader and solving

problem 188 are the actual implementation. Some questions that remain to be asked include: "how does one calculate the $$ord_{m}a$$?", and "what is a good method for modular exponentiation?", etc. Although, the lazy reader may

view this solution in Ruby.