Number theory and discrete mathematics – university Year 1 maths test answers to download as PDF

← Back to the test

1. Answer to Question 1 (4 marks)

   \(390=5\times72+30\), \(72=2\times30+12\), \(30=2\times12+6\), \(12=2\times6\), so the gcd is 6 (2). Backwards: \(6=30-2\times12=30-2(72-2\times30)=5\times30-2\times72=5(390-5\times72)-2\times72=5\times390-27\times72\) (2).

   Each step of the Euclidean algorithm writes the larger number as a multiple of the smaller plus a remainder, and the last non-zero remainder is the gcd. For Bezout, work backwards from \(6=30-2\times12\), replacing each remainder by the expression from the line above. The coefficients are \(x=5\) and \(y=-27\). Check: \(5\times390=1950\) and \(27\times72=1944\), and the difference is 6. Prime factorisation confirms it: \(390=2\times3\times5\times13\) and \(72=2^3\times3^2\) share \(2\times3=6\).

2. Answer to Question 2 (4 marks)

   1. \(\gcd(9,15)=3\) divides 6: \(3x\equiv2\pmod5\) so \(x\equiv4\pmod5\) (1), i.e. \(x\equiv4,9,14\pmod{15}\) (1).
   2. \(2^3=8\equiv1\pmod7\) (1). \(50=16\times3+2\), so \(2^{50}\equiv2^2=4\) (1).

   In (a), a linear congruence \(ax\equiv b\pmod m\) has solutions only if \(\gcd(a,m)\) divides \(b\); here 3 divides 6, so there are exactly 3 solutions modulo 15. Dividing everything by 3 gives \(3x\equiv2\pmod5\), and the inverse of 3 modulo 5 is 2, so \(x\equiv4\). Check: \(9\times4=36=2\times15+6\). In (b), the powers of 2 modulo 7 repeat with period 3, so \(2^{50}=(2^3)^{16}\times2^2\equiv1\times4\).

3. Answer to Question 3 (4 marks)

   1. 10 letters with S three times, T three times, I twice: \(\dfrac{10!}{3!\,3!\,2!}=50\,400\) (2).
   2. Total \(\binom{13}5=1287\); with no women \(\binom75=21\); with one woman \(6\binom74=210\) (1). Answer \(1287-21-210=1056\) (1).

   In (a), dividing by \(3!\,3!\,2!\) removes the repeated arrangements of identical letters; the letters A and C appear once each. In (b), counting at least 2 women directly needs four cases, so the complement is quicker: subtract the committees with 0 or 1 woman from the total. Direct check: \(\binom62\binom73+\binom63\binom72+\binom64\binom71+\binom65=525+420+105+6=1056\).

4. Answer to Question 4 (4 marks)

   1. \(\dfrac{18}2=9\) edges (1).
   2. A tree on 7 vertices has 6 edges, so no (1).
   3. There are four vertices of odd degree (\(1,3,3,3\)) (1); an Euler trail needs 0 or 2, so no (1).

   In (a), the handshaking lemma says the sum of the degrees is twice the number of edges, \(1+2+2+3+3+3+4=18\). In (b), every tree with \(n\) vertices has exactly \(n-1\) edges, and 9 edges is too many. In (c), an Euler trail uses every edge exactly once, so it needs exactly 0 or 2 vertices of odd degree.

5. Answer to Question 5 (4 marks)

   1. \(a_2=16-4=12\), \(a_3=48-16=32\) (1).
   2. \(r^2-4r+4=(r-2)^2\): a repeated root 2, so \(a_n=(A+Bn)2^n\) (1). \(A=1\) and \(2(1+B)=4\) so \(B=1\): \(a_n=(n+1)2^n\) (1). \(a_3=4\times8=32\) (1).

   In (a), use the recurrence: \(a_2=4a_1-4a_0=16-4\) and \(a_3=4a_2-4a_1=48-16\). In (b), the characteristic equation comes from trying \(a_n=r^n\). Because 2 is a repeated root, the second solution is \(n2^n\), just as for a differential equation with a repeated root. The initial conditions give \(A=a_0=1\) and \(2(A+B)=a_1=4\). The formula also gives \(a_2=3\times4=12\), matching part (a).

Total : 20 marks