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

Question

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...

Answer 1

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.

Answer 2

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$.

Answer 3

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.