59.0k views
4 votes
Use mathematical induction to show that 4^n ≡ 3n+1 (mod 9) for all n equal to or greater than 0

User Sammers
by
7.3k points

1 Answer

3 votes
When
n=0, you have


4^0=1\equiv3(0)+1=1\mod9

Now assume this is true for
n=k, i.e.


4^k\equiv3k+1\mod9

and under this hypothesis show that it's also true for
n=k+1. You have


4^k\equiv3k+1\mod9

4\equiv4\mod9

\implies 4*4^k\equiv4(3k+1)\mod9

\implies 4^(k+1)\equiv12k+4\mod9

In other words, there exists
M such that


4^(k+1)=9M+12k+4

Rewriting, you have


4^(k+1)=9M+9k+3k+4

4^(k+1)=9(M+k)+3k+3+1

4^(k+1)=9(M+k)+3(k+1)+1

and this is equivalent to
3(k+1)+1 modulo 9, as desired.

User Shonali
by
8.0k points
Welcome to QAmmunity.org, where you can ask questions and receive answers from other members of our community.

9.4m questions

12.2m answers

Categories