Induction Proof\ Modular Arthimatic

Question

Getting held up in the inductive step. This is what i have so far.

Let $S(n):$ denote the claim. $$S(n): 4^n ≡ 1 \mod 3 \longleftrightarrow 4^n-1=3m, m \in Z $$

Base Case: $$S(1)=4^1 - 1= 3m$$ $$4^1-1=3(1)$$ Inductive Step: For some $x \in N$, Assume S(x) is true where $$S(x): 4^x ≡ 1 \mod 3 \longleftrightarrow 4^x-1=3j, j \in Z$$

Show that $S(x+1)$ holds.

$$S(x+1): 4^{x+1} ≡ 1 \mod 3 \longleftrightarrow 4^{x+1}-1 = 3y, y \in Z$$

This is where i am stuck. I assume we break up the left hand side of the equation and use some substitution for the value.

Answer 1

Yes, you're on the right lines. $$\begin{align}4^{x+1} &= 4^x \times 4 \\&\equiv 1 \times 4 \\&\equiv 1 \times 1 \\&= 1 \pmod{3}\end{align}$$

Answer 2

You have $4^{x+1}-1=4^{x+1}-4^x+4^x-1=3\times4^x+3j=3(4^x+j).$