# IB DP Maths Topic 10.5 Representation of integers in different bases HL Paper 3

## Question

The positive integer N is expressed in base p as $${({a_n}{a_{n – 1}}…{a_1}{a_0})_p}$$ .

Show that when p = 2 , N is even if and only if its least significant digit, $${a_0}$$ , is 0.

[5]
a.

Show that when p = 3 , N is even if and only if the sum of its digits is even.

[6]
b.

## Markscheme

$$N = {a_n} \times {2^n} + {a_{n – 1}} \times {2^{n – 1}} + … + {a_1} \times 2 + {a_0}$$     M1

If $${a_0} = 0$$ , then N is even because all the terms are even.     R1

Now consider

$${a_0} = N – \sum\limits_{r = 1}^n {{a_r} \times {2^r}}$$     M1

If N is even, then $${a_0}$$ is the difference of two even numbers and is therefore even.     R1

It must be zero since that is the only even digit in binary arithmetic.     R1

[5 marks]

a.

$$N = {a_n} \times {3^n} + {a_{n – 1}} \times {3^{n – 1}} + … + {a_1} \times 3 + {a_0}$$

$$= {a_n} \times ({3^n} – 1) + {a_{n – 1}} \times ({3^{n – 1}} – 1) + … + {a_1} \times (3 – 1) + {a_n} + {a_{n – 1}} + … + {a_1} + {a_0}$$     M1A1

Since $${3^n}$$ is odd for all $$n \in {\mathbb{Z}^ + }$$ , it follows that $${3^n} – 1$$ is even.     R1

Therefore if the sum of the digits is even, N is the sum of even numbers and is even.     R1

Now consider

$${a_n} + {a_{n – 1}} + … + {a_1} + {a_0} = N – \sum\limits_{r = 1}^n {{a_r}({3^r} – 1)}$$     M1

If N is even, then the sum of the digits is the difference of even numbers and is therefore even.     R1

[6 marks]

b.

## Examiners report

The response to this question was disappointing. Many candidates were successful in showing the ‘if’ parts of (a) and (b) but failed even to realise that they had to continue to prove the ‘only if’ parts.

a.

The response to this question was disappointing. Many candidates were successful in showing the ‘if’ parts of (a) and (b) but failed even to realise that they had to continue to prove the ‘only if’ parts.

b.

## Question

Convert the decimal number 51966 to base 16.

[4]
a.

(i)     Using the Euclidean algorithm, find the greatest common divisor, d , of 901 and 612.

(ii)     Find integers p and q such that 901p + 612q = d .

(iii)     Find the least possible positive integers s and t such that 901s − 612t = 85.

[10]
b.

In each of the following cases find the solutions, if any, of the given linear congruence.

(i)     $$9x \equiv 3(\bmod 18)$$

(ii)     $$9x \equiv 3(\bmod 15)$$

[5]
c.

## Markscheme

the relevant powers of 16 are 16, 256 and 4096

then

$$51966 = 12 \times 4096{\text{ remainder }}2814$$     M1A1

$$2814 = 10 \times 256{\text{ remainder }}254$$

$$254 = 15 \times 16{\text{ remainder }}14$$     A1

the hexadecimal number is CAFE     A1

Note: CAFE is produced using a standard notation, accept explained alternative notations.

[4 marks]

a.

(i)     using the Euclidean Algorithm     (M1)

$$901 = 612 + 289$$     (A1)

$$612 = 2 \times 289 + 34$$

$$289 = 8 \times 34 + 17$$

$$\gcd (901,{\text{ }}612) = 17$$     A1

(ii)     working backwards     (M1)

$$17 = 289 – 8 \times 34$$

$$= 289 – 8 \times (612 – 2 \times 289)$$

$$= 17 \times (901 – 612) – 8 \times 612$$

$$= 27 \times 901 – 25 \times 612$$

$${\text{so }}p = 17,{\text{ }}q = – 25$$     A1A1

(iii)     a particular solution is

$$s = 5p = 85,{\text{ }}t = – 5q = 125$$     (A1)

the general solution is

$$s = 85 + 36\lambda ,{\text{ }}t = 125 + 53\lambda$$     M1A1

by inspection the solution satisfying all conditions is

$$(\lambda = – 2),{\text{ }}s = 13,{\text{ }}t = 19$$     A1

[10 marks]

b.

(i)     the congruence is equivalent to $$9x = 3 + 18\lambda$$     (A1)

this has no solutions as 9 does not divide the RHS     R1

(ii)     the congruence is equivalent to $$3x = 1 + 5\lambda ,{\text{ }}\left( {3x \equiv 1(\bmod 5)} \right)$$     A1

one solution is $$x = 2$$ , so the general solution is $$x = 2 + 5n\,\,\,\,\,\left( {x \equiv 2(\bmod 5)} \right)$$     M1A1

[5 marks]

c.

## Examiners report

Many did not seem familiar with hexadecimal notation and often left their answer as 12101514 instead of CAFE.

a.

The Euclidean algorithm was generally found to be easy to deal with but getting a general solution in part (iii) eluded many candidates.

b.

Rewriting the congruence in the form $$9x = 3 + 18\lambda$$ for example was not often seen but should have been the first thing thought of.

c.

## Question

Show that a positive integer, written in base 10, is divisible by 9 if the sum of its digits is divisible by 9.

[7]
a.

The representation of the positive integer N in base p is denoted by $${(N)_p}$$ .

If $${({5^{{{(126)}_7}}})_7} = {({a_n}{a_{n – 1}} \ldots {a_1}{a_0})_7}$$ , find $${a_0}$$ .

[9]
b.

## Markscheme

consider the decimal number $$A = {a_n}{a_{n – 1}} \ldots {a_0}$$     M1

$$A = {A_n} \times {10^n} + {a_{n – 1}} \times {10^{n – 1}} + \ldots + {a_1} \times 10 + {a_0}$$     M1

$$= {a_n} \times ({10^n} – 1) + {a_{n – 1}} \times ({10^{n – 1}} – 1) + \ldots + {a_1} \times (10 – 1) + {a_n} + {a_{n – 1}} + \ldots + {a_0}$$     M1A1

$$= {a_n} \times 99 \ldots 9(n{\text{ digits}}) + {a_{n – 1}} \times 99 \ldots 9(n – 1{\text{ digits}}) + \ldots + 9{a_1} + {a_n} + {a_{n – 1}} + \ldots + {a_0}$$     A1

all the numbers of the form 99…9 are divisible by 9 (to give 11…1),     R1

hence A is divisible by 9 if $$\sum\limits_{i = 0}^n {{a_i}}$$ is divisible by 9     R1

Note: A method that uses the fact that $${10^t} \equiv 1(\bmod 9)$$ is equally valid.

[7 marks]

a.

by Fermat’s Little Theorem $${5^6} \equiv 1(\bmod 7)$$     M1A1

$${(126)_7} = {(49 + 14 + 6)_{10}} = {(69)_{10}}$$     M1A1

$${5^{{{(126)}_7}}} \equiv {5^{{{(11 \times 6 + 3)}_{10}}}} \equiv {5^{{{(3)}_{10}}}}(\bmod 7)$$     M1A1

$${5^{{{(3)}_{10}}}} = {(125)_{10}} = {(17 \times 7 + 6)_{10}} \equiv 6(\bmod 7)$$     M1A1

hence $${a_0} = 6$$     A1

[9 marks]

b.

## Examiners report

Questions similar to (a) have been asked in the past so it was surprising to see that solutions this time were generally disappointing.

a.

In (b), most candidates changed the base 7 number 126 to the base 10 number 69. After that the expectation was that Fermats little theorem would be used to complete the solution but few candidates actually did that. Many were unable to proceed any further and others used a variety of methods, for example working modulo 7,

$${5^{69}} = {({5^2})^{34}}.5 = {4^{34}}.5 = {({4^2})^{17}}.5 = {2^{17}}.5$$ etc

This is of course a valid method, but somewhat laborious.

b.

## Question

The positive integer N is expressed in base 9 as $${({a_n}{a_{n – 1}} \ldots {a_0})_9}$$.

(a)     Show that N is divisible by 3 if the least significant digit, $${a_0}$$, is divisible by 3.

(b)     Show that N is divisible by 2 if the sum of its digits is even.

(c)     Without using a conversion to base 10, determine whether or not $${(464860583)_9}$$ is divisible by 12.

## Markscheme

(a)     let $$N = {a_n}{a_{n – 1}} \ldots {a_1}{a_0} = {a_n} \times {9^n} + {a_{n – 1}} \times {9^{n – 1}} + \ldots + {a_1} \times 9 + {a_0}$$     M1A1

all terms except the last are divisible by 3 and so therefore is their sum     R1

it follows that N is divisible by 3 if $${a_0}$$ is divisible by 3     AG

[3 marks]

(b)     EITHER

consider N in the form

$$N = {a_n} \times ({9^n} – 1) + {a_{n – 1}} \times ({9^{n – 1}} – 1) + \ldots + {a_1}(9 – 1) + \sum\limits_{i = 1}^n {{a_i}}$$     M1A1

all terms except the last are even so therefore is their sum     R1

it follows that N is even if $$\sum\limits_{i = 0}^n {{a_i}}$$ is even     AG

OR

working modulo 2, $${9^k} \equiv 1(\bmod 2)$$     M1A1

hence $$N = {a_n}{a_{n – 1}} \ldots {a_1}{a_0} = {a_n} \times {9^n} + {a_{n – 1}} \times {9^{n – 1}} + \ldots + {a_1} \times 9 + {a_0} = \sum\limits_{i = 0}^n {{a_i}(\bmod 2)}$$     R1

it follows that N is even if $$\sum\limits_{i = 0}^n {{a_i}}$$ is even     AG

[3 marks]

(c)     the number is divisible by 3 because the least significant digit is 3     R1

it is divisible by 2 because the sum of the digits is 44 which is even     R1

dividing the number by 2 gives $${(232430286)_9}$$     M1A1

which is even because the sum of the digits is 30 which is even     R1

N is therefore divisible by a further 2 and is therefore divisible by 12     R1

Note: Accept alternative valid solutions.

[6 marks]

Total [12 marks]

## Examiners report

Parts (a) and (b) were generally well answered. Part (c), however, caused problems for many candidates with some candidates even believing that showing divisibility by 2 and 3 was sufficient to prove divisibility by 12. Some candidates stated that the fact that the sum of the digits was 44 (which itself is divisible by 4) indicated divisibility by 4 but this was only accepted if the candidates extended their proof in (b) to cover divisibility by 4.

## Question

(a)     Write down Fermat’s little theorem.

(b)     In base 5 the representation of a natural number X is $${\left( {k00013(5 – k)} \right)_5}$$.

This means that $$X = k \times {5^6} + 1 \times {5^2} + 3 \times 5 + (5 – k)$$.

In base 7 the representation of X is $${({a_n}{a_{n – 1}} \ldots {a_2}{a_1}{a_0})_7}$$.

Find $${a_0}$$.

(c)     Given that k = 2, find X in base 7.

## Markscheme

(a)     EITHER

if p is a prime $${a^p} \equiv a(\bmod p)$$     A1A1

OR

if p is a prime and $$a$$ $$0(\bmod p)$$ then $${a^{p – 1}} \equiv 1(\bmod p)$$     A1A1

Note: Award A1 for p being prime and A1 for the congruence.

[2 marks]

(b)     $${a_0} \equiv X(\bmod 7)$$     M1

$$X = k \times {5^6} + 25 + 15 + 5 – k$$

by Fermat $${5^6} \equiv 1(\bmod 7)$$     R1

$$X = k + 45 – k(\bmod 7)$$     (M1)

$$X = 3(\bmod 7)$$     A1

$${a_0} = 3$$     A1

[5 marks]

(c)     $$X = 2 \times {5^6} + 25 + 15 + 3 = 31\,293$$     A1

EITHER

$$X – {7^5} = 14\,486$$     (M1)

$$X – {7^5} – 6 \times {7^4} = 80$$

$$X – {7^5} – 6 \times {7^4} – {7^2} = 31$$

$$X – {7^5} – 6 \times {7^4} – {7^2} – 4 \times 7 = 3$$

$$X = {7^5} + 6 \times {7^4} + {7^2} + 4 \times 7 + 3$$     (A1)

$$X = {(160\,143)_7}$$     A1

OR

$$31\,293 = 7 \times 4470 + 3$$     (M1)

$$4470 = 7 \times 638 + 4$$

$$638 = 7 \times 91 + 1$$

$$91 = 7 \times 13 + 0$$

$$13 = 7 \times 1 + 6$$     (A1)

$$X = {(160\,143)_7}$$     A1

[4 marks]

Total [11 marks]

## Examiners report

Fermat’s little theorem was reasonably well known. Not all candidates took the hint to use this in the next part and this part was not done well. Part (c) could and was done even if part (b) was not.

## Question

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

[2]
a.

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

[6]
b.

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.

[4]
c.

## Markscheme

$$a = \lambda c + 1$$     M1

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

[2 marks]

a.

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]

b.

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]

c.

## Examiners report

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.

a.

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.

b.

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.

c.

## Question

When numbers are written in base n, $${33^2} = 1331$$.

By writing down an appropriate polynomial equation, determine the value of n.

[4]
a.

Rewrite the above equation with numbers in base 7.

[6]
b.

## Markscheme

the equation can be written as

$${(3n + 3)^2} = {n^3} + 3{n^2} + 3n + 1$$     M1A1

any valid method of solution giving n = 8     (M1)A1

Note: Attempt to change at least one side into an equation in n gains the M1.

[4 marks]

a.

METHOD 1

as decimal numbers,

$${(33)_8} = 27,{\text{ }}{(1331)_8} = 729$$     A1A1

converting to base 7 numbers,

$$27 = {(36)_7}$$     A1

7)729     M1
7)104(1
7) 14(6
7)   2(0
7)   0(2

therefore $$729 = {(2061)_7}$$     A1

the required equation is

$${36^2} = 2061$$     A1

METHOD 2

as a decimal number, $${(33)_8} = 27$$     A1

converting to base 7,

$$27 = {(36)_7}$$     A1

multiplying base 7 numbers

36
× 36
1440     M1
321     A1
2061     A1

the required equation is

$${36^2} = 2061$$     A1

Note: Allow M1 for showing the method of converting a number to base 7 regardless of what number they convert.

[6 marks]

b.

## Examiners report

Part (a) was a good indicator of overall ability. Many candidates did not write both sides of the equation in terms of n and thus had an impossible equation, which should have made them realise that they had a mistake. The answers that were given in (a) and (b) could have been checked, so that the candidate knew they had done it correctly.

a.

Part (b) was not well answered and of those candidates that did, some only gave one side of the equation in base 7. The answers that were given in (a) and (b) could have been checked, so that the candidate knew they had done it correctly.

b.

## Question

Consider an integer $$a$$ with $$(n + 1)$$ digits written as $$a = {10^n}{a_n} + {10^{n – 1}}{a_{n – 1}} + \ldots + 10{a_1} + {a_0}$$, where $$0 \leqslant {a_i} \leqslant 9$$ for $$0 \leqslant i \leqslant n$$, and $${a_n} \ne 0$$.

(a)     Show that $$a \equiv ({a_n} + {a_{n – 1}} + \ldots + {a_0}) ({\text{mod9}})$$.

(b)     Hence find all pairs of values of the single digits $$x$$ and $$y$$ such that the number $$a = 476x212y$$ is a multiple of $$45$$.

(c)     (i)     If $$b = 34\,390$$ in base 10, show that $$b$$ is $$52\,151$$ written in base 9.

(ii)     Hence find $${b^2}$$ in base 9, by performing all the calculations without changing base.

## Markscheme

(a)     $$10 \equiv 1(\bmod 9) \Rightarrow {10^i} \equiv 1({\text{mod9}}),{\text{ }}i = 1,{\text{ }} … ,{\text{ }}n$$     M1A1

$$\Rightarrow {10^i}{a_i} \equiv {a_i}({\text{mod9}}),{\text{ }}i = 1,{\text{ }}n$$     M1

Note: Allow $$i = 0$$ but do not penalize its omission.

$$\Rightarrow ({10^n}{a_n} + {10^{n – 1}}{a_{n – 1}} + \ldots + {a_0}) \equiv ({a_n} + {a_{n – 1}} + \ldots + {a_0})({\text{mod9}})$$     AG

[3 marks]

(b)     $$4 + 7 + 6 + x + 2 + 1 + 2 + y = 9k,{\text{ }}k \in \mathbb{Z}$$     (M1)

$$\Rightarrow (22 + x + y) \equiv 0(\bmod 9),{\text{ }} \Rightarrow (x + y) \equiv 5({\text{mod9}})$$

$$\Rightarrow x + y = 5$$ or $$14$$     A1

if $$5$$ divides $$a$$, then $$y = 0$$ or $$5$$     M1

so $$y = 0 \Rightarrow x = 5,{\text{ }}\left( {ie{\text{ }}(x,{\text{ }}y) = (5,{\text{ }}0)} \right)$$     A1

$$y = 5 \Rightarrow x = 0$$ or $$x = 9,{\text{ }}\left( {ie{\text{ }}(x,{\text{ }}y) = (0,{\text{ }}5){\text{ or }}(x,{\text{ }}y) = (9,{\text{ }}5)} \right)$$     A1A1

[6 marks]

(c)     (i)
(M1)A1

$$b = {(52\,151)_9}$$     AG

(ii)
M1A3

Note: M1 for attempt, A1 for two correct lines of multiplication, A2 for two correct lines of multiplication and a correct addition, A3 for all correct.

[6 marks]

## Examiners report

Surprisingly few good answers. Part (a) had a number of correct solutions, but there were also many that seemed to be a memorised solution, not properly expressed – and consequently wrong. In part (b) many failed to understand the question, not registering that x and y were digits rather than numbers. Part (c)(i) was generally well answered, although there were a number of longer methods applied, and few managed to do (c)(ii).

## Question

Consider the integers $$a = 871$$ and $$b= 1157$$, given in base $$10$$.

(i)     Express $$a$$ and $$b$$ in base $$13$$.

(ii)     Hence show that $${\text{gcd}}(a,{\text{ }}b) = 13$$.

[7]
a.

A list $$L$$ contains $$n+ 1$$ distinct positive integers. Prove that at least two members of $$L$$leave the same remainder on division by $$n$$.

[4]
b.

Consider the simultaneous equations

$$4x + y + 5z = a$$

$$2x + z = b$$

$$3x + 2y + 4z = c$$

where $$x,{\text{ }}y,{\text{ }}z \in \mathbb{Z}$$.

(i)     Show that 7 divides $$2a + b – c$$.

(ii)     Given that a = 3, b = 0 and c = −1, find the solution to the system of equations modulo 2.

[6]
c.

Consider the set $$P$$ of numbers of the form $${n^2} – n + 41,{\text{ }}n \in \mathbb{N}$$.

(i)     Prove that all elements of P are odd.

(ii)     List the first six elements of P for n = 0, 1, 2, 3, 4, 5.

(iii)     Show that not all elements of P are prime.

[6]
d.

## Markscheme

(i)     METHOD 1

using a relevant list of powers of 13: (1), 13, 169, (2197)     M1

$$871 = 5 \times {13^2} + 2 \times 13$$     A1

$$871 = {520_{13}}$$     A1

$$1157 = 6 \times {13^2} + 11 \times 13$$     A1

$$1157 = 6{\text{B}}{{\text{0}}_{13}}$$     A1

METHOD 2

attempted repeated division by 13     M1

$$871 \div 13 = 67;{\text{ }}67 \div 13 = 5{\text{rem}}2$$     A1

$$871 = {520_{13}}$$     A1

$$1157 \div 13 = 89;{\text{ }}89 \div 13 = 6{\text{rem11}}$$     A1

$$1157 = 6{\text{B}}{{\text{0}}_{13}}$$     A1

Note:     Allow (11) for B only if brackets or equivalent are present.

(ii)     $$871 = 13 \times 67;{\text{ }}1157 = 13 \times 89$$     (M1)

67 and 89 are primes (base 10) or they are co-prime     A1

So $$\gcd (871,{\text{ }}1157) = 13$$     AG

Note:     Must be done by hence not Euclid’s algorithm on 871 and 1157.

[7 marks]

a.

let K be the set of possible remainders on division by n     (M1)

then $$K = \{ {\text{0, 1, 2, }} \ldots n – 1\}$$ has n members     A1

because $$n < n + 1{\text{ }}\left( { = n(L)} \right)$$     A1

by the pigeon-hole principle (appearing anywhere and not necessarily mentioned by name as long as is explained)     R1

at least two members of L correspond to one member of K     AG

[4 marks]

b.

(i)     form the appropriate linear combination of the equations:     (M1)

$$2a + b – c = 7x + 7z$$     A1

$$= 7(x + z)$$     R1

so 7 divides $$2a + b – c$$     AG

(ii)     modulo 2, the equations become     M1

$$y + z = 1$$

$$z = 0$$     A1

$$x = 1$$

solution: (1, 1, 0)     A1

Note:     Award full mark to use of GDC (or done manually) to solve the system giving $$x = – 1,{\text{ }}y = – 3,{\text{ }}z = 2$$ and then converting mod 2.

[6 marks]

c.

(i)     separate consideration of even and odd n     M1

$${\text{eve}}{{\text{n}}^2} – {\text{even}} + {\text{odd is odd}}$$     A1

$${\text{od}}{{\text{d}}^2} – {\text{odd}} + {\text{odd is odd}}$$     A1

all elements of P are odd     AG

Note:     Allow other methods eg, $${n^2} – n = n(n – 1)$$ which must be even.

(ii)     the list is [41, 41, 43, 47, 53, 61]     A1

(iii)     $${41^2} – 41 + 41 = {41^2}$$ divisible by 41     A1

but is not a prime     R1

the statement is disproved (by counterexample)  AG

[6 marks]

d.

[N/A]

a.

[N/A]

b.

[N/A]

c.

[N/A]

d.

## Question

Given a sequence of non negative integers $$\{ {a_r}\}$$ show that

(i)     $$\sum\limits_{r = 0}^n {{a_r}{{(x + 1)}^r}(\bmod x) = \sum\limits_{r = 0}^n {{a_r}(\bmod x)} }$$ where $$x \in \{ 2,{\text{ }}3,{\text{ }}4 \ldots \}$$.

(ii)     $$\sum\limits_{r = 0}^n {(3{a_{2r + 1}} + {a_{2r}}){9^r} = \sum\limits_{r = 0}^{2n + 1} {{a_r}{3^r}} }$$.

[5]
a.

Hence determine whether the base $$3$$ number $$22010112200201$$ is divisible by $$8$$.

[5]
b.

## Markscheme

(i)     $$(x + 1)(\bmod x) \equiv 1(\bmod x)$$     (M1)

$${(x + 1)^r}(\bmod x)\left( { \equiv {1^r}(\bmod x)} \right) = 1(\bmod x)$$     A1

$$\sum\limits_{r – 0}^n {{a_r}{{(x + 1)}^r}(\bmod x) \equiv \sum\limits_{r = 0}^n {{a_r}(\bmod x)} }$$     AG

(ii)     METHOD 1

$$\sum\limits_{r = 0}^n {(3{a_{2r + 1}} + {a_{2r}}){9^r} = \sum\limits_{r = 0}^n {(3{a_{2r + 1}} + {a_{2r}}){3^{2r}}} }$$     M1

$$= \sum\limits_{r = 0}^n {({3^{2r + 1}}{a_{2r + 1}} + {3^{2r}}{a_{2r}})}$$     M1A1

$$= \sum\limits_{r = 0}^{2n + 1} {{a_r}{3^r}}$$     AG

METHOD 2

$$\sum\limits_{r = 0}^n {(3{a_{2r + 1}} + {a_{2r}}){9^r} = 3{a_1} + {a_0} + 9(3{a_3} + {a_2}) + \ldots + {9^n}(3{a_{2n + 1}} + {a_{2n}})}$$     A1

$$= {a_0} + 3{a_1} + {3^2}{a_2} + {3^3}{a_3} + \ldots + {3^{2n + 1}}{a_{2n + 1}}$$     M1A1

$$= \sum\limits_{r = 0}^{2n + 1} {{a_r}{3^r}}$$     AG

[5 marks]

a.

METHOD 1

using part (a) (ii) to separate the number into pairs of digits     (M1)

$$22010112200201{\text{ }}({\text{base }}3) \equiv 8115621{\text{ }}({\text{base }}9)$$     A1

using the sum of digits identity from part (a) (i)     (M1)

Note:     Award M1 if result from a(i) is used to show that the number is divisible by $$2$$, even if no other valid working given.

$${\text{sum}} = 24$$     A1

which is divisible by $$8$$     A1

hence $$22010112200201$$ (base $$3$$) is divisible by $$8$$

METHOD 2

$$\sum\limits_{r = 0}^{13} {{a_r}{3^r}\sum\limits_{r = 0}^6 {(3{a_{2r + 1}} + {a_{2r}}){9^r}} }$$     (M1)

$$\equiv \sum\limits_{r = 0}^6 {(3{a_{2r + 1}} + {a_{2r}})(\bmod 8)}$$     A1

$$= {a_0} + 3{a_1} + {a_2} + 3{a_3} + \ldots + {a_{12}} + 3{a_{13}}(\bmod 8)$$     M1

$$= (1 + 3 \times 0 + 2 + 3 \times 0 + \ldots + 3 \times 2)(\bmod 8) \equiv 24(\bmod 8)$$     A1

$$\equiv 0$$ OR divisible by $$8$$     A1

hence $$22010112200201$$ (base $$3$$) is divisible by $$8$$

[5 marks]

Total [10 marks]

b.

[N/A]

a.

[N/A]

b.

## Question

Throughout this question, $${(abc \ldots )_n}$$ denotes the number $$abc \ldots$$ written with number base $$n$$. For example $${(359)_n} = 3{n^2} + 5n + 9$$.

(i)     Given that $${(43)_n} \times {(56)_n} = {(3112)_n}$$, show that $$3{n^3} – 19{n^2} – 38n – 16 = 0$$.

(ii)     Hence determine the value of $$n$$.

[3]
a.

Determine the set of values of $$n$$ satisfying $${(13)_n} \times {(21)_n} = {(273)_n}$$.

[3]
b.

Show that there are no possible values of $$n$$ satisfying $${(32)_n} \times {(61)_n} = {(1839)_n}$$.

[4]
c.

## Markscheme

(i)     $$n$$ satisfies the equation $$(4n + 3)(5n + 6) = 3{n^3} + {n^2} + n + 2$$     M1A1

$$3{n^3} – 19{n^2} – 38n – 16 = 0$$    (AG)

(ii)     $$n = 8$$     A1

Note:     If extra solutions $$( – 1,{\text{ }} – 2/3)$$ are not rejected (them just not appearing is fine) do not award the final A1.

[3 marks]

a.

$$n$$ satisfies the equation $$(n + 3)(2n + 1) = 2{n^2} + 7n + 3$$     A1

this is an identity satisfied by all $$n$$     (A1)

$$n > 7$$ or $$n \geqslant 8$$     A1

[3 marks]

b.

$$n$$ satisfies the equation $$(3n + 2)(6n + 1) = {n^3} + 8{n^2} + 3n + 9$$     A1

$${n^3} – 10{n^2} – 12n + 7 = 0$$    A1

roots are 11.03, 0.434 and –1.46     A1

since there are no integer roots therefore the product is not true in any number base     R1AG

Note:     Accept an argument by contradiction that considers the equation modulo $$n$$, with $$n > 10$$.

[4 marks]

c.

## Examiners report

a.

The fact that this gave an identity was managed by most. Then some showed their misunderstanding by saying any real number. Few noticed that the digit 7 means that the base must be greater than 7.

b.

The cubic equation was generally reached but many candidates then forgot what type of number $$n$$ had to be. To justify that there are no positive integer roots you need to write down what the roots are. There were a couple of really neat solutions that obtained a contradiction by working modulo $$n$$.

c.

## Question

In this question the notation $${({a_n}{a_{n – 1}} \ldots {a_2}{a_1}{a_0})_b}$$ is used to represent a number in base $$b$$, that has unit digit of $${a_0}$$. For example $${(2234)_5}$$ represents $$2 \times {5^3} + 2 \times {5^2} + 3 \times 5 + 4 = 319$$ and it has a unit digit of 4.

Let $$x$$ be the cube root of the base 7 number $${(503231)_7}$$.

(i)     By converting the base 7 number to base 10, find the value of $$x$$, in base 10.

(ii)     Express $$x$$ as a base 5 number.

[7]
a.

Let $$y$$ be the base 9 number $${({a_n}{a_{n – 1}} \ldots {a_1}{a_0})_9}$$. Show that $$y$$ is exactly divisible by 8 if and only if the sum of its digits, $$\sum\limits_{i = 0}^n {{a_i}}$$, is also exactly divisible by 8.

[7]
b.

Using the method from part (b), find the unit digit when the base 9 number $${(321321321)_9}$$ is written as a base 8 number.

[3]
c.

## Markscheme

(i)     converting to base 10

$${(503231)_7} = 5 \times {7^5} + 3 \times {7^3} + 2 \times {7^2} + 3 \times 7 + 1 = 85184$$    M1A1A1

so $$x = 44$$     A1

(ii)     repeated division by 5 gives     (M1)

so base 5 value for $$x$$ is $${(134)_5}$$     A1

Notes: Alternative method is to successively subtract the largest multiple of 25 and then 5.

Follow through if they forget to take the cube root and obtain $${(10211214)_5}$$ then award (M1)(A1)A1.

[7 marks]

a.

$$9 \equiv 1(\bmod 8)$$    A1

$${9^i} \equiv {1^i} \equiv 1(\bmod 8)$$    $$i \in \mathbb{N}$$     (M1)(A1)

$$y = {a_n}{9^n} + {a_{n – 1}}{9^{n – 1}} + \ldots + {a_1}9 + {a_0} \equiv {a_n}{1^n} + {a_{n – 1}}{1^{n – 1}} + \ldots + {a_1}1 + {a_0} \equiv$$

$${a_n} + {a_{n – 1}} + \ldots + {a_1} + {a_0} \equiv \sum\limits_{i = 0}^n {{a_i}(\bmod 8)}$$    M1A1A1

so $$y = 0(\bmod 8)$$ and hence divisible by 8 if and only if $$\sum\limits_{i = 0}^n {{a_i} \equiv 0(\bmod 8)}$$ and hence divisible by 8     R1AG

Note: Accept alternative valid methods eg binomial expansion of $${(8 + 1)^i}$$, factorization of $$({a^i} – 1)$$ if they have sufficient explanation.

[7 marks]

b.

using part (b), $${(321321321)_9} \equiv 3 + 2 + 1 + 3 + 2 + 1 + 3 + 2 + 1 = 18 \equiv 2(\bmod 8)$$     M1A1

so the unit digit is 2     A1

[3 marks]

c.

[N/A]

a.

[N/A]

b.

[N/A]

c.

## Question

The decimal number 1071 is equal to $$a$$060 in base $$b$$, where $$a > 0$$.

Convert the decimal number 1071 to base 12.

[3]
a.

Write the decimal number 1071 as a product of its prime factors.

[1]
b.

Using your answers to part (a) and (b), prove that there is only one possible value for $$b$$ and state this value.

[4]
c.i.

Hence state the value of $$a$$.

[1]
c.ii.

## Markscheme

EITHER

using a list of relevant powers of 12: 1, 12, 144     (M1)

$$1071 = 7 \times {12^2} + 5 \times {12^1} + 3 \times {12^0}$$     (A1)

OR

attempted repeated division by 12     (M1)

$$1071 \div 12 = 89{\text{rem}}3;{\text{ }}89 \div 12 = 7{\text{rem}}5$$     (A1)

THEN

$$1071 = {753_{12}}$$     A1

[3 marks]

a.

$$1071 = 3 \times 3 \times 7 \times 17$$     A1

[1 mark]

b.

in base $$b$$ $$a060$$ ends in a zero and so $$b$$ is a factor of 1071     R1

from part (a) $$b < 12$$ as $$a060$$ has four digits and so the possibilities are

$$b = 3,{\text{ }}b = 7$$ or $$b = 9$$     R1

stating valid reasons to exclude both $$b = 3$$ eg, there is a digit of 6

and $$b = 9$$ eg, $$1071 = {(1420)_9}$$     R1

$$b = 7$$     A1

Note:     The A mark is independent of the R marks.

[4 marks]

c.i.

$$1071 = {(3060)_7} \Rightarrow a = 3$$     A1

[1 mark]

c.ii.

[N/A]

a.

[N/A]

b.

[N/A]

c.i.

[N/A]

c.ii.