# IB DP Maths Topic 10.2 Prime numbers; relatively prime numbers and the fundamental theorem of arithmeticHL Paper 3

## Question

Write 57128 as a product of primes.


a.

Prove that $$\left. {22} \right|{5^{11}} + {17^{11}}$$.


c.

## Markscheme

$$457\,128 = 2 \times 228\,564$$

$$228\,564 = 2 \times 114\,282$$

$$114\,282 = 2 \times 57\,141$$

$$57\,141 = 3 \times 19\,047$$

$$19\,047 = 3 \times 6349$$

$$6349 = 7 \times 907$$     M1A1

trial division by 11, 13, 17, 19, 23 and 29 shows that 907 is prime     R1

therefore $$457\,128 = {2^3} \times {3^2} \times 7 \times 907$$     A1

[4 marks]

a.

by a corollary to Fermat’s Last Theorem

$${5^{11}} \equiv 5(\bmod 11){\text{ and }}{17^{11}} \equiv 17(\bmod 11)$$     M1A1

$${5^{11}} + {17^{11}} \equiv 5 + 17 \equiv 0(\bmod 11)$$     A1

this combined with the evenness of LHS implies $$\left. {25} \right|{5^{11}} + {17^{11}}$$     R1AG

[4 marks]

c.

## Examiners report

Some candidates were obviously not sure what was meant by ‘product of primes’ which surprised the examiner.

a.

There were some reasonable attempts at part (c) using powers rather than Fermat’s little theorem.

c.

## Question

Explaining your method fully, determine whether or not 1189 is a prime number.


a.

(i)     State the fundamental theorem of arithmetic.

(ii)     The positive integers M and N have greatest common divisor G and least common multiple L . Show that GL = MN .


b.

## Markscheme

any clearly indicated method of dividing 1189 by successive numbers     M1

find that 1189 has factors 29 and/or 41     A2

it follows that 1189 is not a prime number     A1

Note: If no method is indicated, award A1 for the factors and A1 for the conclusion.

[4 marks]

a.

(i)     every positive integer, greater than 1, is either prime or can be expressed uniquely as a product of primes     A1A1

Note: Award A1 for “product of primes” and A1 for “uniquely”.

(ii)     METHOD 1

let M and N be expressed as a product of primes as follows

M = AB and N = AC     M1A1

where A denotes the factors which are common and B, C the disjoint factors which are not common

it follows that G = A     A1

and L = GBC     A1

from these equations, it follows that

$$GL = A \times ABC = MN$$     AG

METHOD 2

Let $$M = {2^{{x_1}}} \times {3^{{x_2}}} \times …p_n^{{x_n}}$$ and $$N = {2^{{y_1}}} \times {3^{{y_2}}} \times …p_n^{{y_n}}$$ where $${p_n}$$ denotes the $${n^{{\text{th}}}}$$ prime     M1

Then $$G = {2^{\min ({x_1},{y_1})}} \times {3^{\min ({x_2},{y_2})}} \times …p_n^{\min ({x_n},{y_n})}$$     A1

and $$L = {2^{\max ({x_1},{y_1})}} \times {3^{\max ({x_2},{y_2})}} \times …p_n^{\max ({x_n},{y_n})}$$     A1

It follows that $$GL = {2^{{x_1}}} \times {2^{{y_1}}} \times {3^{{x_2}}} \times {3^{{y_2}}} \times … \times p_n^{{x_n}} \times p_n^{{y_n}}$$     A1

= MN     AG

[6 marks]

b.

## Examiners report

In (a), some candidates tried to use Fermat’s little theorem to determine whether or not 1189 is prime but this method will not always work and in any case the amount of computation involved can be excessive. For this reason, it is strongly recommended that this method should not be used in examinations. In (b), it was clear from the scripts that candidates who had covered this material were generally successful and those who had not previously seen the result were usually unable to proceed.

a.

In (a), some candidates tried to use Fermat’s little theorem to determine whether or not 1189 is prime but this method will not always work and in any case the amount of computation involved can be excessive. For this reason, it is strongly recommended that this method should not be used in examinations. In (b), it was clear from the scripts that candidates who had covered this material were generally successful and those who had not previously seen the result were usually unable to proceed.

b.

## Question

Show that $$30$$ is a factor of $${n^5} – n$$ for all $$n \in \mathbb{N}$$.


a.

(i)     Show that $${3^{{3^m}}} \equiv 3({\text{mod}}4)$$ for all $$m \in \mathbb{N}$$.

(ii)     Hence show that there is exactly one pair $$(m,{\text{ }}n)$$ where $$m,{\text{ }}n \in \mathbb{N}$$, satisfying the equation $${3^{{3^m}}} = {2^{{2^n}}} + {5^2}$$.


b.

## Markscheme

METHOD 1

$${n^5} – n = \underbrace {n(n – 1)(n + 1)}_{{\text{3 consecutive integers}}}({n^2} + 1) \equiv 0({\text{mod}}6)$$     M1

at least a factor is multiple of 3 and at least a factor is multiple of 2     R1

$${n^5} – n = n({n^4} – 1) \equiv 0({\text{mod}}5)$$ as $${n^4} \equiv 1({\text{mod}}5)$$ by FLT     R1

therefore, as $${\text{(5, 6)}} = 1$$,     R1

$${n^5} – n \equiv 0\left( {\bmod \underbrace {5 \times 6}_{30}} \right)$$     A1

ie 30 is a factor of $${n^5} – n$$     AG

METHOD 2

let $${\text{P}}(n)$$ be the proposition: $${n^5} – n = 30\alpha$$ for some $$\alpha \in \mathbb{Z}$$

$${0^5} – 0 = 30 \times 0$$, so $${\text{P}}(0)$$ is true     A1

assume $${\text{P}}(k)$$ is true for some $$k$$ and consider $${\text{P}}(k + 1)$$

$${(k + 1)^5} – (k + 1) = {k^5} + 5{k^4} + 10{k^3} + 10{k^2} + 5k + 1 – k – 1$$     M1

$$= ({k^5} – k) + 5k\left( {\underbrace {{k^3} + 3{k^2} + 3k + 1}_{{{(k + 1)}^3}} – ({k^2} + k)} \right)$$

$$= ({k^5} – k) + 5k\left( {{{(k + 1)}^3} – k(k + 1)} \right)$$

$$= 30\alpha + \underbrace {5k(k + 1)\left( {\underbrace {{k^2} + k + 1}_{k(k + 1) + 1}} \right)}_{{\text{multiple of 6}}}$$     M1

$$= 30\alpha + 30\beta$$     A1

as $${\text{P}}(0)$$ is true and $${\text{P}}(k)$$ true implies $${\text{P}}(k + 1)$$ true, by PMI $${\text{P}}(n)$$ is true for all values $$n \in \mathbb{N}$$     R1

Note: Award the first M1 only if the correct induction procedure is followed and the correct first line is seen.

Note: Award R1 only if both M marks have been awarded.

METHOD 3

$${n^5} – n = n({n^4} – 1)$$     M1

$$= n({n^2} – 1)({n^2} + 1)$$     A1

$$= (n – 1)n(n + 1)({n^2} – 4 + 5)$$     R1

$$= (n – 2)(n – 1)n(n + 1)(n + 2) + 5(n – 1)n(n + 1)$$     A1

each term is multiple of 2, 3 and 5     R1

therefore is divisible by 30     AG

[5 marks]

a.

(i)     METHOD 1

case 1: $$m = 0$$ and $${3^{{3^0}}} \equiv 3{\text{mod}}4$$ is true     A1

case 2: $$m > 0$$

let $$N = {3^m} \geqslant 3$$ and consider the binomial expansion     M1

$${3^N} = {(1 + 2)^N} = \sum\limits_{k = 0}^N {}$$ $$\left( \begin{array}{c}N\\k\end{array} \right){2^k} = 1 + 2N + \underbrace {\sum\limits_{k = 2}^N {\left( \begin{array}{c}N\\k\end{array} \right){2^k}} }_{ \equiv ({\text{mod}}4)} \equiv 1 + 2N({\text{mod}}4)$$     A1

as $$\underbrace {{3^m}}_N \equiv {( – 1)^m}({\text{mod}}4) \Rightarrow 1 + 2N \equiv 1 + 2{( – 1)^m}({\text{mod}}4)$$     R1

therefore $$\underbrace {{3^{{3^m}}}}_{{3^N}} \equiv 1 + 2{( – 1)^m}({\text{mod}}4) \Rightarrow$$ $$\left\{ \begin{array}{l}\underbrace {{3^{{3^m}}}}_{{3^N}} \equiv \underbrace {1 + 2}_3({\text{mod}}4){\rm{for\,}} m {\rm{\,even}}\\\underbrace {{3^{{3^m}}}}_{{3^N}} \equiv \underbrace {1 – 2}_{ – 1 \equiv 3({\text{mod}}4)}({\text{mod}}4){\rm{for\,}} m {\rm{\,odd}}\end{array} \right.$$     R1

which proves that $${3^{{3^m}}} \equiv 3({\text{mod}}4)$$ for any $$m \in \mathbb{N}$$     AG

METHOD 2

let $${\text{P}}(n)$$ be the proposition: $${3^{{3^n}}} – 3 \equiv 0({\text{mod }}4,{\text{ or }}24)$$

$${3^{{3^0}}} – 3 = 3 – 3 \equiv 0({\text{mod }}4{\text{ or }}24)$$, so $${\text{P}}(0)$$ is true     A1

assume $${\text{P}}(k)$$ is true for some $$k$$     M1

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

$$= {(3 + 24r)^3} – 3$$

$$\equiv 27 + 24t – 3$$     R1

$$\equiv 0({\text{mod }}4{\text{ or }}24)$$

as $${\text{P}}(0)$$ is true and $${\text{P}}(k)$$ true implies $${\text{P}}(k + 1)$$ true, by PMI $${\text{P}}(n)$$ is true for all values $$n \in \mathbb{N}$$     R1

METHOD 3

$${3^{{3^m}}} – 3 = 3({3^{{3^m} – 1}} – 1)$$     M1A1

$$= 3({3^{2k}} – 1)$$     R1

$$= 3({9^k} – 1)$$

$$= 3\underbrace {\left( {{{(8 + 1)}^k} – 1} \right)}_{{\text{multiple of 8}}}$$     R1

$$\equiv 0({\text{mod}}24)$$     A1

which proves that $${3^{{3^m}}} \equiv 3({\text{mod}}4)$$ for any $$m \in \mathbb{N}$$     AG

(ii)     for $$m \in \mathbb{N},{\text{ }}{3^{{3^m}}} \equiv 3({\text{mod}}4)$$ and, as $${2^{{2^n}}} \equiv 0({\text{mod}}4)$$ and $${5^2} \equiv 1({\text{mod}}4)$$ then $${2^{{2^n}}} + {5^2} \equiv 1({\text{mod}}4)$$ for $$n \in {\mathbb{Z}^ + }$$

there is no solution to $${3^{{3^m}}} = {2^{{2^n}}} + {5^2}$$ for pairs $$(m,{\text{ }}n) \in \mathbb{N} \times {\mathbb{Z}^ + }$$     R1

when $$n = 0$$, we have $${3^{{3^m}}} = {2^{{2^0}}} + {5^2} \Rightarrow {3^{{3^m}}} = 27 \Rightarrow m = 1$$     M1

therefore $$(m,{\text{ }}n) = (1,{\text{ }}0)$$     A1

is the only pair of non-negative integers that satisfies the equation     AG

[8 marks]

b.

## Examiners report

Many students were able to get partial credit for part (a), although few managed to gain full marks.

a.

There seemed to be very few good attempts at part (b), many failing at the outset to understand what was meant by $${3^{{3^m}}}$$.

b.

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


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


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.


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.


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

State the Fundamental theorem of arithmetic for positive whole numbers greater than $$1$$.


a.

Use the Fundamental theorem of arithmetic, applied to $$5577$$ and $$99\,099$$, to calculate $$\gcd (5577,{\text{ }}99\,099)$$ and $${\text{lcm}}(5577,{\text{ }}99\,099)$$, expressing each of your answers as a product of prime numbers.


b.

Prove that $$\gcd (n,{\text{ }}m) \times {\text{lcm}}(n,{\text{ }}m) = n \times m$$ for all $$n,{\text{ }}m \in {\mathbb{Z}^ + }$$.


c.

## Markscheme

every positive integer, greater than $$1$$, is either prime or can be expressed uniquely as a product of primes     A1A1

Note:     Award A1 for “product of primes” and A1 for “uniquely”.

[2 marks]

a.

$$5577 = 3 \times 11 \times {13^2}{\text{ and }}99099 = {3^2} \times 7 \times {11^2} \times 13$$     M1

$$\gcd (5577,{\text{ }}99099) = 3 \times 11 \times 13,{\text{ lcm}}(5577,{\text{ }}99099) = {3^2} \times 7 \times {11^2} \times {13^2}$$     A1A1

[3 marks]

b.

METHOD 1

$$n = p_1^{{k_1}}p_2^{{k_2}} \ldots p_r^{{k_r}}$$ and $$m = p_1^{{j_1}}p_2^{{j_2}} \ldots p_r^{{j_r}}$$     M1

employing all the prime factors of $$n$$ and $$m$$, and inserting zero exponents if necessary     R1

define $${g_i} = \min ({k_i},{\text{ }}{j_i})$$ and $${h_i} = \max ({k_i},{\text{ }}{j_i})$$ for $$i = 1 \ldots r$$     (M1)

$$\gcd (n,{\text{ }}m) = p_1^{{g_1}}p_2^{{g_2}} \ldots p_r^{{g_r}}$$ and $${\text{lcm}}(n,{\text{ }}m) = p_1^{{h_1}}p_2^{{h_2}} \ldots p_r^{{h_r}}$$     A1A1

noting that $${g_i} + {h_i} = {k_i} + {j_i}$$ for $$i = 1 \ldots r$$     R1

$$\gcd (n,{\text{ }}m) \times {\text{lcm}}(n,{\text{ }}m) = n \times m$$ for all $$n,{\text{ }}m \in {\mathbb{Z}^ + }$$AG

METHOD 2

let $$m$$ and $$n$$ be expressed as a product of primes where $$m = ab$$ and $$n = ac$$     M1

$$a$$ denotes the factors that are common and $$b,{\text{ }}c$$ are the disjoint factors that are not common     R1

$$\gcd (n,{\text{ }}m) = a$$     A1

$${\text{lcm}}(n,{\text{ }}m) = \gcd (n,{\text{ }}m)bc$$     A1

$$\gcd (n,{\text{ }}m) \times {\text{lcm}}(n,{\text{ }}m) = a \times (abc)$$     M1

$$= ab \times ac$$ and $$m = ab$$ and $$n = ac$$ so     R1

$$\gcd (n,{\text{ }}m) \times 1{\text{ cm}}(n,{\text{ }}m) = n \times m$$ for all $$n,{\text{ }}m \in {\mathbb{Z}^ + }$$     AG

[6 marks]

Total [11 marks]

c.

## Examiners report

In part (a), most candidates omitted the ‘uniquely’ in their definition of the fundamental theorem of arithmetic. A few candidates defined what a prime number is.

a.

In part (b), a substantial number of candidates used the Euclidean algorithm rather than the fundamental theorem of arithmetic to calculate $$\gcd (5577,{\text{ }}99099)$$ and $${\text{lcm}}(5577,{\text{ }}99099)$$.

b.

In part (c), a standard proof that has appeared in previous examination papers, was answered successfully by candidates who were well prepared.

c.

## Question

Show that $${\text{gcd}}\left( {4k + 2,\,3k + 1} \right) = {\text{gcd}}\left( {k – 1,\,2} \right)$$, where $$k \in {\mathbb{Z}^ + },\,k > 1$$.


a.

State the value of $${\text{gcd}}\left( {4k + 2,\,3k + 1} \right)$$ for odd positive integers $$k$$.


b.i.

State the value of $${\text{gcd}}\left( {4k + 2,\,3k + 1} \right)$$ for even positive integers $$k$$.


b.ii.

## Markscheme

METHOD 1

attempting to use the Euclidean algorithm       M1

$$4k + 2 = 1\left( {3k + 1} \right) + \left( {k + 1} \right)$$      A1

$$3k + 1 = 2\left( {k + 1} \right) + \left( {k – 1} \right)$$      A1

$$K + 1 = \left( {k – 1} \right) + 2$$      A1

$$= {\text{gcd}}\left( {k – 1,\,2} \right)$$     AG

METHOD 2

$${\text{gcd}}\left( {4k + 2,\,3k + 1} \right)$$

$$= {\text{gcd}}\left( {4k + 2 – \left( {3k + 1} \right),\,3k + 1} \right)$$     M1

$$= {\text{gcd}}\left( {3k + 1,\,k + 1} \right)\,\,\left( { = {\text{gcd}}\left( {{\text{k + 1,}}\,{\text{3k + 1}}} \right)} \right)$$     A1

$$= {\text{gcd}}\left( {3k + 1 – 2\left( {k + 1} \right),\,k + 1} \right)\,\,\left( { = {\text{gcd}}\left( {k – 1{\text{,}}\,k + {\text{1}}} \right)} \right)$$     A1

$$= {\text{gcd}}\left( {k + 1 – \left( {k – 1} \right),\,k – 1} \right)\,\,\left( { = {\text{gcd}}\left( {{\text{2,}}\,k – {\text{1}}} \right)} \right)$$     A1

$$= {\text{gcd}}\left( {k – 1,\,2} \right)$$     AG

[4 marks]

a.

(for $$k$$ odd), $${\text{gcd}}\left( {4k + 2,\,3k + 1} \right) = 2$$     A1

[1 mark]

b.i.

(for $$k$$ even), $${\text{gcd}}\left( {4k + 2,\,3k + 1} \right) = 1$$     A1

[1 mark]

b.ii.

[N/A]

a.

[N/A]

b.i.

[N/A]

b.ii.