2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – dxiv Oct 20 '16 at 16:28
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Schytheron Oct 20 '16 at 16:29
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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$? $\endgroup$ – Schytheron Oct 20 '16 at 16:50
  • $\begingroup$ Oops, I screwed up the formatting of the last expression... but you get the idea. $\endgroup$ – Schytheron Oct 20 '16 at 16:51
  • $\begingroup$ @Schytheron Corrected the typing error. $\endgroup$ – tatan Oct 20 '16 at 16:51
  • $\begingroup$ What is $m$ is this case? $\endgroup$ – Schytheron Oct 20 '16 at 17:35
  • $\begingroup$ $m$ is any positive integer. $\endgroup$ – tatan Oct 21 '16 at 14:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.