Have a doubt with this?

Let us begin by simplifying the problem. Ignoring our final addition, we seek positive coprime integers p, q such that the fractional remainder of $p/q$ equals $3^{2n}/8, n \; \in \mathbb{Z}^+$ .

In other words, we want to find $p/q = \frac{3^{2n}\ (mod\ 8)}{8}$ . "mod" stands for modulus, or the remainder when divided by. 5 (mod 2) is 1, 6 (mod 7) is 6, and 9 (mod 8) is 1. In general, $a = b\ (mod\ c), a,b,c \in \mathbb{Z}^+, b < c$ if $\exists n\ \in \mathbb{Z}^+: a = cn + b.$

Since $p$ and $q$ are coprime, we know that $p = 3^{2n}\ (mod\ 8)$ and $q = 8$ .

Simplifying, $p = 9^n\ (mod\ 8)$ , or the remainder of $9^n$ when divided by $8$ . This suggests that $9^n\ (mod\ 8)$ is some constant; in fact, $9^n\ (mod\ 8) = 1$ . This is proven below.

$p = 1, q = 8 \Rightarrow p + q = 9.$ QED.

$\\ \\$

Proof that $9^n\ (mod\ 8) = 1$ :

We will define the following notation, for an arbitrary $n$ , let $\{\bar{a}\} = \{ b\ \in \mathbb{Z}^+ : b\ (mod\ x) = a\ (mod\ x) \}$ , and let $\bar{a}$ an arbitrary element of $\{\bar{a}\}$ . Note that any two numbers, $r, s$ in $\{\bar{a}\}$ will have the same remainder, or $\bar{r}\ (mod\ x) = \bar{s}\ (mod\ x)$ .

Thus, in mod 8, $\bar{9}$ is in the same set as $\bar{1}$ , and because 1 is the simplest value of that set, $9\ (mod\ 8) = 1$ .

Lemma 1: $\bar{a} \cdot \bar{b}$ is in the same set as $\overline{ab}$ .

We know that $\bar{a} = nx + a$ , and that $\bar{b} = mx + b$ , with $n,m\ \in \mathbb{Z}^+$ .

Thus $\bar{a} \cdot \bar{b} = (nx + a)(mx + b) \\ = nmx^2 + nbx + max + ab \\ = (nmx + nb + ma)x + (ab).$

If we know that $\bar{r} = sx + r$ , then we also know that given some $sx + r$ , it will be in the same set as $\bar{r}$ . Let $s = (nmx + nb + ma), r = (ab)$ .

$\bar{a} + \bar{b} = sx + r = \bar{r} = \overline{ab}$ . Lemma proved.

Thus, given $\overline{ab}\ (mod\ x)$ , we may reduce it to $\bar{a}\cdot\bar{b}\ (mod\ x)$ .

Extending this logic, $p = \overline{9^n} (mod\ 8) = \overline{9 \cdot 9\ ... n\ times} \\ = \bar{9}\ (mod\ 8)\cdot\bar{9}\ (mod\ 8)\ ... n\ times \\ = 1 \cdot 1 \cdot 1 \ ... n\ times = 1.$

$p = 1, q = 8 \Rightarrow p + q = 9.$ QED.