# How can I prove that a remainder pattern of a modulus operation is infinite?

I have a task that looks like this: "For what $n \geq 0$ is $2^n + 2 \times 3^n$ divisible by $8$?"

I have already solved this and gotten an answer, however there is one thing I can't prove in my solution and its bothering me.

I split up $2^n + 2 \times 3^n$ so that I got the terms separated. $2^n$ and $2\times 3^n$. When I studied what remainders $3^n \pmod 8$ gave I noticed that I got a pattern that goes $3,1,3,1,3,1,3,1..$ and so on. If $n$ was odd I get the remainder $3$ and if $n$ is even I get the remainder $1$.

According to Wolfram Alpha this pattern seems to go on forever. The question is why and how would I prove this? Does it have something to do with the fact that 3 is a prime number? I am quite new to this whole modulus thing...

• If n was odd I get the remainder 3 and if n is even I get the remainder 1 Hint: $3^2 = 9 \equiv 1 \pmod 8$. In the odd case, for example, $3^{2k+1} = 3 \cdot (3^2)^k \equiv 3 \cdot 1 \pmod 8$. – dxiv Oct 20 '16 at 16:28

## 3 Answers

This is quite general, and doesn't depend on $3$ being a prime number. Take any integer $k\ge 2$, and any integer $a$. Then the sequence $$a \bmod k,a^2 \bmod k,a^3 \bmod k,...$$ eventually settles down to a repeating sequence. This is easy to prove:

• There are only a finite number of possible values for $a^n \bmod k$ (namely $0,1,\ldots,k-1$).
• Therefore there must eventually be a repeated value; say $a^m\equiv a^n \bmod k$, with $m>n$.
• After that, we have $a^{m+i}\equiv a^ma^i\equiv a^na^i\equiv a^{n+i} \bmod k$. In other words, the sequence repeats, with period $m-n$.

In your case, we have $3^2\equiv 3^0 \equiv 1\bmod 8$, so the sequence has just the two elements $3$ and $1$.

For a lot more on this topic, see any course on Elementary Number Theory.

For $n \ge 3$ we have $2^n + 2 \cdot 3^n \equiv 2 \cdot 3^n \not\equiv 0\bmod 8$.

It remains to test $n=0,1,2$ and see that $8$ divides $2^n + 2 \cdot 3^n$ iff $n=1$.

• As I said above... I have already solved the task. What I need help with is proving that the $3^n mod8$ remainder pattern is infinite and why. – Schytheron Oct 20 '16 at 16:29

Observe that, $3^2 \equiv 1 \pmod 8 \implies (3^2)^m \equiv 1^m \equiv 1 \pmod8, \forall m\in \Bbb N$

$\implies 3^n \equiv 1 \pmod 8$ if $n$ is even.

From here, it's trivial to show that for odd n,

$3^n \equiv 1 \cdot3 \equiv 3\pmod 8$

So, you get the remainders in the sequence $1,3,1,3...$ and so on.

• I follow your train of thought but isn't $3^2 \equiv 1 mod8$? Because $3^2 = 9$. And if $n$ is even shouldn't the last expression look like this: $3^(n+1) \equiv 1*3 \equiv 3$? – Schytheron Oct 20 '16 at 16:50
• Oops, I screwed up the formatting of the last expression... but you get the idea. – Schytheron Oct 20 '16 at 16:51
• @Schytheron Corrected the typing error. – tatan Oct 20 '16 at 16:51
• What is $m$ is this case? – Schytheron Oct 20 '16 at 17:35
• $m$ is any positive integer. – tatan Oct 21 '16 at 14:22