Given that a , $b \in \mathbb{N}$ and $c \in {\mathbb{Z}^ + }$, show that if $a \equiv 1(\bmod c)$ , then $ab \equiv b(\bmod c)$ .

Using mathematical induction, show that ${9^n} \equiv 1(\bmod 4)$ , for $n \in \mathbb{N}$ .

The positive integer M is expressed in base 9. Show that M is divisible by 4 if the sum of its digits is divisible by 4.

$a = \lambda c + 1$     M1

so $ab = \lambda bc + b \Rightarrow ab \equiv b(\bmod c)$     A1AG

[2 marks]

the result is true for n = 0 since ${9^0} = 1 \equiv 1(\bmod 4)$     A1

assume the result is true for n = k , i.e. ${9^k} \equiv 1(\bmod 4)$     M1

consider ${9^{k + 1}} = 9 \times {9^k}$     M1

$\equiv 9 \times 1(\bmod 4)$ or $1 \times {9^k}(\bmod 4)$     A1

$\equiv 1(\bmod 4)$     A1

so true for $n = k \Rightarrow$ true for n = k + 1 and since true for n = 0 result follows by induction     R1

Note: Do not award the final R1 unless both M1 marks have been awarded.

Note: Award the final R1 if candidates state n = 1 rather than n = 0

[6 marks]

let $M = {({a_n}{a_{n - 1}}…{a_0})_9}$     (M1)

$= {a_n} \times {9^n} + {a_{n - 1}} \times {9^{n - 1}} + ... + {a_0} \times {9^0}$     A1

EITHER

$\equiv {a_n}(\bmod 4) + {a_{n - 1}}(\bmod 4) + ... + {a_0}(\bmod 4)$     A1

$\equiv \sum {{a_i}(\bmod 4)}$     A1

so M is divisible by 4 if $\sum {{a_i}}$ is divisible by 4     AG

OR

$= {a_n}({9^n} - 1) + {a_{n - 1}}({9^{n - 1}} - 1) + ... + {a_1}({9^1} - 1)$

$+ {a_n} + {a_{n - 1}} + ... + {a_1} + {a_0}$     A1

Since ${9^n} \equiv 1(\bmod 4)$ , it follows that ${9^n} - 1$ is divisible by 4,     R1

so M is divisible by 4 if $\sum {{a_i}}$ is divisible by 4     AG

[4 marks]

Part (a) was generally well answered. In (b), many candidates tested the result for n = 1 instead of n = 0. It has been suggested that the reason for this was a misunderstanding of the symbol N with some candidates believing it to denote the positive integers. It is important for candidates to be familiar with IB notation in which N denotes the positive integers and zero. In some scripts the presentation of the proof by induction was poor.

Part (a) was generally well answered. In (b), many candidates tested the result for n = 1 instead of n = 0. It has been suggested that the reason for this was a misunderstanding of the symbol N with some candidates believing it to denote the positive integers. It is important for candidates to be familiar with IB notation in which N denotes the positive integers and zero. In some scripts the presentation of the proof by induction was poor.

Part (a) was generally well answered. In (b), many candidates tested the result for n = 1 instead of n = 0. It has been suggested that the reason for this was a misunderstanding of the symbol N with some candidates believing it to denote the positive integers. It is important for candidates to be familiar with IB notation in which N denotes the positive integers and zero. In some scripts the presentation of the proof by induction was poor.