Determining a rule for the remainder when $3^n$ is divided by $13$

Question

After some direct calculations, it appears that the powers of $3$ form a cycle of $1$, $3$, and $9$ when divided by consecutive powers of $n$. For example $$3^0 \equiv 1 \pmod{13}, 3^1 \equiv 3 \pmod{13}, 3^2 \equiv 9 \pmod{13}, 3^3 \equiv 1 \pmod{13}, \dots$$

I am tasked with proving my claim by induction. The base case is given above. I am confused as to what the "induction step" actually is. In general, we assume the statement holds for $n$ and try to deduce that the statement is true for $n+1$. But to me it's not clear what $n$ is in this problem.

I am not looking for a solution, but rather an explanation of what I am trying to prove in the inductive step.

Answer 1

As a hint, note that induction doesn't have to hold for a base case n. It can hold for a number of base cases and then induct. In other words, induction is a logical statement that takes an input and gives an output of all integers, but you could start from case n=10, n=30, etc and go up or down. Also, you could prove multiple cases and then induct separately, ie Case 1 is $n \equiv 1 $ (mod 3), Case 2 is $ n \equiv 2 $ (mod 3), etc.

I'm not sure why you would prove this with induction, simply use the fact that the exponent eventually becomes one and the exponent addition rule to substitute out any multiple of three from the order.

Also, check out online what an order is in modular arithmetic.

EDIT:

You said you are not looking for a solution but let us use it as an example.

We can divide the theorem into three parts for the three congruence classes modulo 3 that the exponents can fall under, the obligatory "the other cases are similar" will suffice here such that I won't go through every case. Simply work through for $ 3^{3q + r} $.

In the case $ 3^{3q + 1} \equiv 3 $ (modulo 3), observe this:

The base case is $ q = 0: 3^{1} \equiv 3 $ (modulo 13).

The induction case applies to q. Here we have

$ 3^{3q + 1} \equiv 3 $ (modulo 13) implies $ 3^{3(q + 1) + 1} \equiv 3 $ (modulo 13)

Proving that requires we know that $ 3^{3} \equiv 1 $ and the exponent of a sum law.

Answer 2

Prove the following three propositions. The first two are easy, the last is only a little harder:

$$13\mid k-1 \implies 13\mid 3k-3\\ 13\mid k-3\implies 13\mid 3k-9\\ 13\mid k-9\implies 13\mid 3k-1$$

Then apply induction on $n$ with $k=3^n$.