# Help with multiple statement induction proof

I am learning proof by induction in my math class and I am having trouble with this problem:

Prove that for $k \in N, 3^{4k-3}\equiv 3 \pmod{10}, 3^{4k-2} \equiv 9 \pmod{10}, 3^{4k-1} \equiv 7 \pmod{10}, 3^{4k} \equiv 1 \pmod{10}$.

Attempt: Normally, I know how to prove one of these. But this problem is pretty overwhelming since there are so many statements and I do not know how to structure my proof. Also, I am thinking that once I prove one of them, the others should be easier to prove by building on top of the previous proof. But again, I do not really know how to structure my proof in a professional way.

-
You are right, once you have proved one of them (any) you can prove the rest without induction. And we barely need induction. Note that $3^{4k}=81^k\equiv 1^k\equiv 1\pmod{10}$. (In principle we need induction to show that if $a\equiv b$, then $a^n\equiv b^n$.) –  André Nicolas Mar 20 at 1:47

Hint $\$ Note that if $\,f(k) = 3^{\large 4k+j}$ then $\,f(k\!+\!1) = 3^4 f(k) = 81 f(k)\equiv f(k)\pmod{10},\,$ which yields the inductive step in all cases.

Remark $\$ You can unify all cases to $\, 3^{4(k-1)}\equiv 1\,$ by cancelling $3$'s from both sides, which is valid since $3$ is coprime to $10\,$ (or, equivalently multiply by $\,3^{-1}\equiv 7\,$ to cancel the $3^j$'s on the RHS).

The induction boils down to $\,{\rm mod}\ 10\!:\ 81\equiv 1\,\Rightarrow\, 81^n\equiv 1^n\equiv 1\,$ which is a special case of the general Congruence Power Rule below.

Congruence Sum Rule $\rm\qquad\quad A\equiv a,\quad B\equiv b\ \Rightarrow\ \color{#c0f}{A+B\,\equiv\, a+b}\ \ \ (mod\ m)$

Proof $\rm\ \ m\: |\: A\!-\!a,\ B\!-\!b\ \Rightarrow\ m\ |\ (A\!-\!a) + (B\!-\!b)\ =\ \color{#c0f}{A+B - (a+b)}$

Congruence Product Rule $\rm\quad\ A\equiv a,\ \ and \ \ B\equiv b\ \Rightarrow\ \color{blue}{AB\equiv ab}\ \ \ (mod\ m)$

Proof $\rm\ \ m\: |\: A\!-\!a,\ B\!-\!b\ \Rightarrow\ m\ |\ (A\!-\!a)\ B + a\ (B\!-\!b)\ =\ \color{blue}{AB - ab}$

Congruence Power Rule $\rm\qquad \color{}{A\equiv a}\ \Rightarrow\ \color{#c00}{A^n\equiv a^n}\ \ (mod\ m)$

Proof $\$ It is true for $\rm\,n=1\,$ and $\rm\,A\equiv a,\ A^n\equiv a^n \Rightarrow\, \color{#c00}{A^{n+1}\equiv a^{n+1}},\,$ by the Product Rule, so the result follows by induction on $\,n.$

Polynomial Congruence Rule $\$ If $\,f(x)\,$ is polynomial with integer coefficients then $\ A\equiv a\ \Rightarrow\ f(A)\equiv f(a)\,\pmod m.$

Proof $\$ By induction on $\, n =$ degree $f.\,$ Clear if $\, n = 0.\,$ Else $\,f(x) = f(0) + x\,g(x)\,$ for $\,g(x)\,$ a polynomial with integer coefficients of degree $< n.\,$ By induction $\,g(A)\equiv g(a)\,$ so $\, A g(A)\equiv a g(a)\,$ by the Product Rule. Hence $\,f(A) = f(0)+Ag(A)\equiv f(0)+ag(a) = f(a)\,$ by the Sum Rule.

Beware  that such rules need not hold true for other operations, e.g. the exponential analog of above $\rm A^B\equiv a^b$ is not generally true (unless $\rm B = b,\,$ so it reduces to the Power Rule, so follows by inductively applying $\,\rm b\,$ times the Product Rule).

-
@Anant Right, typo fixed. Thanks! –  Bill Dubuque Mar 20 at 18:34