Question

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

Answer 1

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.