Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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

1 Answer 1

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

share|improve this answer
    
@Anant Right, typo fixed. Thanks! –  Bill Dubuque Mar 20 at 18:34

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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