Friday, August 14, 2009

Project Euler #188: The hyperexponentiation of a number

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.