Download IITian Academy App for accessing Online Mock Tests and More..
Question
Use the Euclidean Algorithm to show that \(275\) and \(378\) are relatively prime.
Find the general solution to the diophantine equation \(275x + 378y = 1\) .
Answer/Explanation
Markscheme
\(378 = 1 \times 275 + 103\) A1
\(275 = 2 \times 103 + 69\) A1
\(103 = 1 \times 69 + 34\) A1
\(69 = 2 \times 34 + 1\) A1
showing that gcd \( = 1\) , i.e. relatively prime. R1
[5 marks]
Working backwards,
\(1 = 69 – 2 \times (103 – 69)\) (M1)
\( = 3 \times 69 – 2 \times 103\) (A1)
\( = 3 \times (275 – 2 \times 103) – 2 \times 103\)
\( = 3 \times 275 – 8 \times 103\) (A1)
\( = 3 \times 275 – 8 \times (378 – 275)\)
\( = 11 \times 275 – 8 \times 378\) (A1)
A solution is \(x = 11\) , \(y = – 8\) (A1)
The general solution is \(x = 11 + 378n\) , \(y = – 8 – 275n\) where \(n \in \mathbb{Z}\) M1A1 N6
[7 marks]
Question
Prove that \(3k + 2\) and \(5k + 3\) , \(k \in \mathbb{Z}\) are relatively prime.
Answer/Explanation
Markscheme
EITHER
\(3k + 2\) and \(5k + 3\) , \(k \in \mathbb{Z}\) are relatively prime
if, for all \(k\) , there exist \(m,n \in \mathbb{Z}\) such that
\(m(3k + 2) + n(5k + 3) = 1\) R1M1A1
\( \Rightarrow 3m + 5n = 0\) A1
\(2m + 3n = 1\) A1
\(m = 5\) , \(n = – 3\) A1
hence they are relatively prime AG
OR
\(5k + 3 = 1 \times (3k + 2) + 2k + 1\) M1A1
\(3k + 2 = 1 \times (2k + 1) + k + 1\) A1
\(2k + 1 = 1 \times (k + 1) + k\) A1
\(k + 1 = 1 \times (k) + 1\) A1
GDC = 1 A1
so \(5k + 3\) and \(3k + 2\) are relatively prime AG
[6 marks]
Question
Prove that if \({\rm{gcd}}(a,b) = 1\) and \({\rm{gcd}}(a,c) = 1\) , then \({\rm{gcd}}(a,bc) = 1\) .
(i) A simple graph has e edges and v vertices, where \(v > 2\) . Prove that if all the vertices have degree at least k , then \(2e \ge kv\) .
(ii) Hence prove that every planar graph has at least one vertex of degree less than 6.
Answer/Explanation
Markscheme
EITHER
since \({\rm{gcd}}(a,b) = 1\) and \({\rm{gcd}}(a,c) = 1\) then
\(ax + by = 1\) and \(ap + cq = 1\) for \(x\), \(y\) , \(p\), \(q \in \mathbb{Z}\) M1A1
hence
\((ax + by)(ap + cq) = 1\) A1
\(a(xap + xcq + byp) + bc(yq) = 1\) M1
since \((xap + xcq + byp)\) and \((yq)\) are integers R1
then \({\rm{gcd}}(a,bc) = 1\) AG
OR
if \({\rm{gcd}}(a,bc) \ne 1\) , some prime p divides a and bc M1A1
\(p\) divides \(b\) or \(c\) M1
either \({\rm{gcd}}(a,b)\) or \({\rm{gcd}}(a,c) \ne 1\) A1
contradiction \( \Rightarrow {\rm{gcd}}(a,bc) = 1\) R1
[5 marks]
(i) each edge contributes 2 to the degree sum R1
so \(2e = \) degree sum R1
so \(2e \ge kv\) AG
(ii) \(k = 6\) so \(2e \ge 6v\) M1
for a planar graph with \(v\) vertices and e edges, \(e \le 3v – 6\) M1
so \(2e \le 6v – 12\) A1
this is a contradiction so at least one vertex must have degree \( < 6\) R1
Note: Alternative proofs are possible.
[6 marks]
Question
Express the number \(47502\) as a product of its prime factors.
The positive integers \(M\) , \(N\) are such that \(\gcd (M,N) = 63\) and \(lcm(M,N) = 47502\) . Given that \(M\) is even and \(M < N\) , find the two possible pairs of values for \(M\) , \(N\) .
Answer/Explanation
Markscheme
(M1)
therefore \(47502 = 2 \times {3^2} \times 7 \times 13 \times 29\) A1
[2 marks]
noting that \(MN = \gcd \times {\rm{lcm}} = 2 \times {3^4} \times {7^2} \times 13 \times 29\) (M1)
the possibilities are
\((M,N) = (126,23751)\) A1A1
\((M,N) = (1638,1827)\) A1A1
[5 marks]
Examiners report
As expected, the factorization in (a) was successfully completed by most candidates.
Part (b) caused problems for some candidates. The most common mistake was that only one pair of values for \(M\), \(N\) was given.
Question
(i) Use the Euclidean algorithm to find gcd(\(6750\), \(144\)) .
(ii) Express your answer in the form \(6750r + 144s\) where r , \(s \in \mathbb{Z}\) .
Consider the base \(15\) number CBA, where A, B, C represent respectively the digits ten, eleven, twelve.
(i) Write this number in base \(10\).
(ii) Hence express this number as a product of prime factors, writing the factors in base 4.
Answer/Explanation
Markscheme
(i) \(6750 = 46 \times 144 + 126\) M1A1
\(144 = 1 \times 126 + 18\) A1
\(126 = 7 \times 18\)
\(\gcd(6750,144) = 18\) A1 N0
(ii) \(18 = 144 – 1 \times 126\) (M1)
\( = 144 – (6750 – 46 \times 144)\)
\( = 47 \times 144 + ( – 1) \times 6750\) A1
[6 marks]
(i) \(n = 10 + 11 \times 15 + 12 \times {15^2}\) (M1)(A1)
\( = 2875\) A1
(ii) \(2875 = {5^3} \times 23\) A1
\( = 11 \times 11 \times 11 \times 113\) in base \(4\) A1A1
Note: A1 for \(11 \times 11 \times 11\) , A1 for \(113\) .
[6 marks]
Question
Use the Euclidean algorithm to find \(\gcd (162,{\text{ }}5982)\).
The relation \(R\) is defined on \({\mathbb{Z}^ + }\) by \(nRm\) if and only if \(\gcd (n,{\text{ }}m) = 2\).
(i) By finding counterexamples show that \(R\) is neither reflexive nor transitive.
(ii) Write down the set of solutions of \(nR6\).
Answer/Explanation
Markscheme
\(5982 = 162 \times 36 + 150\) M1A1
\(162 = 150 \times 1 + 12\) A1
\(150 = 12 \times 12 + 6\)
\(12 = 6 \times 2 + 0 \Rightarrow \gcd \) is 6 A1
[4 marks]
(i) for example, \(\gcd (4,{\text{ }}4) = 4\) A1
\(4 \ne 2\) R1
so \(R\) is not reflexive AG
for example
\(\gcd (4,{\text{ }}2) = 2\) and \(\gcd (2,{\text{ }}8) = 2\) M1A1
but \(\gcd (4,{\text{ }}8) = 4{\text{ }}( \ne 2)\) R1
so \(R\) is not transitive AG
(ii) EITHER
even numbers A1
not divisible by 6 A1
OR
\(\{ 2 + 6n:n \in \mathbb{N}\} {\text{ }} \cup \{ 4 + 6n:n \in \mathbb{N}\} \) A1A1
OR
\(2,{\text{ }}4,{\text{ }}8,{\text{ }}10,{\text{ }} \ldots \) A2
[7 marks]
Question
Use the Euclidean algorithm to find the greatest common divisor of 74 and 383.
Hence find integers s and t such that 74s + 383t = 1.
Answer/Explanation
Markscheme
383 = 5 × 74 + 13 M1
74 = 5 × 13 + 9 A1
13 = 1 × 9 + 4 (A1)
9 = 2 × 4 + 1
4 = 4 × 1 + 0
⇒ gcd (74, 383) = 1 A1
[4 marks]
EITHER
1 = 9 − 2 × 4 (M1)
= 9 − 2(13 − 1 × 9) = 3 × 9 − 2 × 13 (A1)
= 3(74 − 5 × 13) − 2 × 13 = 3 × 74 − 17 × 13 (A1)
= 3 × 74 − 17 (383 − 5 × 74) = 88 × 74 − 17 × 383
OR
13 = 383 − 5 × 74 (M1)
9 = 74 − 5 × 13
= 74 − 5(383 − 5 × 74)
= 26 × 74 − 5 × 383 (A1)
4 = 13 − 9
= (383 − 5 × 74) − (26 × 74 − 5 × 383)
= 6 × 383 − 31 × 74 (A1)
1 = 9 − 2 × 4
= (26 × 74 − 5 × 383) − 2(6 × 383 − 31 × 74)
= 88 × 74 − 17 × 383
THEN
⇒ s = 88 and t = − 17 A1A1
[5 marks]