Level 2 — RecallNumber Theory (Intermediate)

Number Theory (Intermediate)

40 marksprintable — key stays hidden on paper

Level 2 — Recall & Standard Problems Time: 30 minutes Total Marks: 40

Q1. State the divisibility rule for 11, and use it to check whether $918082$ is divisible by $11$ . (4 marks)

Q2. Prove that $\sqrt{2}$ is irrational. (6 marks)

Q3. Use the Euclidean algorithm to find $\gcd(1071, 462)$ . Show every step. (4 marks)

Q4. Using the Extended Euclidean algorithm, find integers $x, y$ such that $240x + 46y = \gcd(240, 46).$ State Bézout's identity in your answer. (5 marks)

Q5. Evaluate the following in modular arithmetic: (a) $(17 + 25) \bmod 6$ (b) $(23 \times 14) \bmod 5$ (4 marks)

Q6. Write the decimal expansion of each rational number and state whether it terminates or repeats: (a) $\dfrac{7}{8}$ (b) $\dfrac{4}{11}$ (4 marks)

Q7. State Fermat's Little Theorem. Using it, compute $3^{100} \bmod 7$ . (5 marks)

Q8. Fill in with the correct symbol ( $\subset$ ) to describe the real number system, and classify each number below into the smallest set to which it belongs ( $\mathbb{N}, \mathbb{Z}, \mathbb{Q}, \mathbb{R}$ ): $-5, \quad \tfrac{3}{4}, \quad \pi, \quad 7.$ (4 marks)

Q9. Find the smallest positive integer $x$ satisfying the system (Chinese Remainder Theorem): $x \equiv 2 \pmod 3, \qquad x \equiv 3 \pmod 5.$ (4 marks)

End of paper

Answer keyMark scheme & solutions

Q1. (4 marks) Rule: A number is divisible by 11 iff the alternating sum of its digits (from the right) is divisible by 11. (1 mark)

For $918082$ : digits from right $2,8,0,8,1,9$ . Alternating sum $= 2 - 8 + 0 - 8 + 1 - 9 = -22$ . (2 marks) Since $-22 = 11\times(-2)$ is divisible by 11, $918082$ is divisible by 11. (1 mark) (Check: $918082 / 11 = 83462$ .)

Q2. (6 marks) Assume, for contradiction, $\sqrt2 = p/q$ with $p,q\in\mathbb Z$ , $q\neq0$ , and $\gcd(p,q)=1$ (lowest terms). (1) Then $2 = p^2/q^2 \Rightarrow p^2 = 2q^2$ , so $p^2$ is even $\Rightarrow p$ is even. (1) Write $p = 2k$ . Then $4k^2 = 2q^2 \Rightarrow q^2 = 2k^2$ , so $q^2$ is even $\Rightarrow q$ is even. (2) But then $2 \mid p$ and $2 \mid q$ , contradicting $\gcd(p,q)=1$ . (1) Hence $\sqrt2$ cannot be written as a ratio of integers; $\sqrt2$ is irrational. $\blacksquare$ (1)

Q3. (4 marks) $1071 = 2\times462 + 147$ $462 = 3\times147 + 21$ $147 = 7\times21 + 0$ (3 marks, 1 per correct step) Last non-zero remainder $= \mathbf{21}$ , so $\gcd(1071,462)=21$ . (1)

Q4. (5 marks) Euclid: $240 = 5\times46 + 10$ ; $46 = 4\times10 + 6$ ; $10 = 1\times6 + 4$ ; $6 = 1\times4 + 2$ ; $4 = 2\times2$ . So $\gcd = 2$ . (2) Back-substitute: $2 = 6 - 1\times4$ $= 6 - (10-6) = 2\times6 - 10$ $= 2(46-4\times10) - 10 = 2\times46 - 9\times10$ $= 2\times46 - 9(240-5\times46) = 47\times46 - 9\times240$ . (2) Thus $x=-9,\ y=47$ : $240(-9)+46(47)=2$ (Bézout's identity: gcd is expressible as integer combination). (1)

Q5. (4 marks) (a) $17+25 = 42$ , $42 \bmod 6 = \mathbf{0}$ . (2) (b) $23\times14 = 322$ ; $322 = 64\times5 + 2$ , so $\mathbf{2}$ . (Or $23\equiv3,\,14\equiv4,\,3\times4=12\equiv2$ .) (2)

Q6. (4 marks) (a) $7/8 = 0.875$ — terminating (denominator $8=2^3$ ). (2) (b) $4/11 = 0.\overline{36} = 0.363636\ldots$ — repeating, period 2. (2)

Q7. (5 marks) Fermat's Little Theorem: If $p$ is prime and $p\nmid a$ , then $a^{p-1}\equiv 1 \pmod p$ . (2) Here $p=7$ , $a=3$ : $3^{6}\equiv1\pmod7$ . (1) $100 = 6\times16 + 4$ , so $3^{100} = (3^6)^{16}\cdot3^4 \equiv 1\cdot3^4 \pmod7$ . (1) $3^4 = 81 = 11\times7 + 4 \equiv \mathbf{4}\pmod7$ . (1)

Q8. (4 marks) $\mathbb N \subset \mathbb Z \subset \mathbb Q \subset \mathbb R.$ (1 for chain) Classification (smallest set): (3, ¾ each)

$-5 \in \mathbb Z$
$\tfrac34 \in \mathbb Q$
$\pi \in \mathbb R$ (irrational)
$7 \in \mathbb N$

Q9. (4 marks) Numbers $\equiv 2 \pmod3$ : $2,5,8,11,14,\ldots$ (1) Test $\equiv 3\pmod5$ : $8\bmod5=3$ . ✓ (2) Smallest positive solution $x = \mathbf{8}$ (general solution $x\equiv8\pmod{15}$ ). (1)

[
  {"claim":"918082 divisible by 11", "code":"result = (918082 % 11 == 0)"},
  {"claim":"gcd(1071,462)=21", "code":"result = (gcd(1071,462) == 21)"},
  {"claim":"Bezout 240*(-9)+46*47 = gcd = 2", "code":"result = (240*(-9)+46*47 == 2 and gcd(240,46)==2)"},
  {"claim":"3**100 mod 7 = 4", "code":"result = (pow(3,100,7) == 4)"},
  {"claim":"CRT solution x=8 satisfies both congruences", "code":"result = (8 % 3 == 2 and 8 % 5 == 3)"}
]