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

← Back to the worksheet

1. Answer to Question 1

   1. \(1071=2\times462+147\), then \(462=3\times147+21\), then \(147=7\times21+0\). The last non-zero remainder is \(\gcd=\) 21.
   2. \(21=462-3\times147=462-3(1071-2\times462)=7\times462-3\times1071\). So \(x=-3\), \(y=7\): indeed \(7\times462-3\times1071=3234-3213=21\).
   3. \(\operatorname{lcm}=\dfrac{1071\times462}{21}=\dfrac{494\,802}{21}=\) 23 562.

2. Answer to Question 2

   1. Euclid: \(26=2\times11+4\), \(11=2\times4+3\), \(4=3+1\). Backwards: \(1=4-3=4-(11-2\times4)=3\times4-11=3(26-2\times11)-11=3\times26-7\times11\). So \(-7\times11\equiv1\) and the inverse is \(-7\equiv\) 19. Check: \(11\times19=209=8\times26+1\).
   2. Multiply both sides by 19: \(x\equiv5\times19=95\equiv95-78=\) 17 \(\pmod{26}\). Check: \(11\times17=187=7\times26+5\).
   3. \(\gcd(6,10)=2\) divides 4, so there are 2 solutions modulo 10. Divide by 2: \(3x\equiv2\pmod5\). The inverse of 3 mod 5 is 2, so \(x\equiv4\pmod5\). Modulo 10: \(x\equiv4\) or \(x\equiv9\).

3. Answer to Question 3

   1. 13 is prime and does not divide 5, so \(5^{12}\equiv1\pmod{13}\). Since \(100=8\times12+4\), \(5^{100}\equiv5^4=625\). And \(625=48\times13+1\), so \(5^{100}\equiv\) 1 \(\pmod{13}\).
   2. \(360=2^3\times3^2\times5\), so \(\varphi(360)=360\left(1-\tfrac12\right)\left(1-\tfrac13\right)\left(1-\tfrac15\right)=360\times\tfrac12\times\tfrac23\times\tfrac45=\) 96.
   3. \(\gcd(7,10)=1\) and \(\varphi(10)=4\), so \(7^4\equiv1\pmod{10}\). \(222=55\times4+2\), so \(7^{222}\equiv7^2=49\equiv9\). The last digit is 9.

4. Answer to Question 4

   1. The moduli are pairwise coprime, so there is one solution modulo \(105\). From \(x\equiv2\pmod 3\) and \(x\equiv2\pmod7\) we get \(x\equiv2\pmod{21}\): \(x=2,23,44,65,86\). Of these, \(23\equiv3\pmod5\). So \(x\equiv23\pmod{105}\).
   2. \(x=4+9k\) must satisfy \(4+9k\equiv1\pmod4\), i.e. \(k\equiv-3\equiv1\pmod4\) (since \(9\equiv1\)). So \(k=1\) and \(x=13\). Answer: \(x\equiv13\pmod{36}\). Check: \(13=3\times4+1\) and \(13=9+4\).

5. Answer to Question 5

   1. 6 letters with A repeated 3 times and N twice: \(\dfrac{6!}{3!\,2!}=\dfrac{720}{12}=\) 60.
   2. Order does not matter: \(\dbinom{12}4=\dfrac{12\times11\times10\times9}{24}=\) 495.
   3. Inclusion-exclusion with \(\lfloor1000/3\rfloor=333\), \(\lfloor1000/5\rfloor=200\), \(\lfloor1000/7\rfloor=142\), \(\lfloor1000/15\rfloor=66\), \(\lfloor1000/21\rfloor=47\), \(\lfloor1000/35\rfloor=28\), \(\lfloor1000/105\rfloor=9\): \(333+200+142-66-47-28+9=\) 543.

6. Answer to Question 6

   1. By the handshaking lemma, the number of edges is \(\dfrac{4+4+3+3+2+2}2=\) 9. There are exactly two vertices of odd degree, so there is an Euler trail (starting and ending at the odd vertices) but no Euler circuit.
   2. A tree with \(n\) vertices has \(n-1\) edges: 14.
   3. Every vertex of \(K_n\) has degree \(n-1\), which must be even: \(n\) odd (and \(n\ge3\)). \(K_6\) has \(\dbinom62=\) 15 edges.

7. Answer to Question 7

   1. A whole number of tiles must fit along each side, so the side length divides both 336 cm and 252 cm.
   2. \(336=1\times252+84\) and \(252=3\times84\). So \(\gcd(336,252)=\) 84 cm.
   3. \(\dfrac{336}{84}\times\dfrac{252}{84}=4\times3=\) 12 tiles.
   4. \(12\times7.50=\) £90. With 28 cm tiles: \(12\times9=108\) tiles costing \(108\times1.20=\) £129.60. The large tiles are cheaper.

8. Answer to Question 8

   1. \(\gcd(5,8)=1\) divides 79, so by Bezout there are integer solutions.
   2. Multiply by 79: \(x_0=-237\), \(y_0=158\) is a solution.
   3. General solution: \(x=-237+8t\), \(y=158-5t\). We need \(t\ge30\) (so \(x\ge3\)) and \(t\le31\) (so \(y\ge3\)). \(t=30\) gives \((3,8)\) and \(t=31\) gives \((11,3)\). So 3 five-pence and 8 eight-pence stamps, or 11 five-pence and 3 eight-pence stamps.
   4. For 27: \(y=0,1,2,3\) gives \(27,19,11,3\) remaining, none a multiple of 5. From 28 to 32 we have \(28=4\times5+8\), \(29=5+3\times8\), \(30=6\times5\), \(31=3\times5+2\times8\), \(32=4\times8\). Five consecutive amounts work, and adding 5p stamps reaches every larger amount. \(5\times8-5-8=27\).

9. Answer to Question 9

   1. \(365=52\times7+1\), so the day moves on by 1: Saturday.
   2. \(100=14\times7+2\), so two days after Friday: Sunday (11 April 2027).
   3. \(366\equiv2\pmod7\), so two days after Saturday: Monday.
   4. Each ordinary year shifts the weekday by 1 and each leap year by 2. A calendar can be reused only when the total shift is a multiple of 7 and the year has the same leap status; this usually takes 6 or 11 years.

10. Answer to Question 10

    1. \(0+27+0+42+24+0+24+3+10=\) 130.
    2. We need \(130+d_{10}\equiv0\pmod{11}\). \(130=11\times11+9\), so \(d_{10}=\) 2. The ISBN is 0-306-40615-2.
    3. The sum changes by \(6\times(7-4)=18\), and \(18\not\equiv0\pmod{11}\), so the total is no longer a multiple of 11.
    4. A wrong digit in position with weight \(w\) changes the sum by \(w\times e\) where \(1\le w\le10\) and \(1\le|e|\le10\). Since 11 is prime and divides neither \(w\) nor \(e\), it does not divide \(we\).

11. Answer to Question 11

    1. \(\varphi(55)=(5-1)(11-1)=\) 40.
    2. \(3d\equiv1\pmod{40}\): \(3\times27=81=2\times40+1\), so \(d=\) 27.
    3. \(8^3=512=9\times55+17\), so \(c=\) 17.
    4. \(c^d=m^{3\times27}=m^{81}=m^{2\times40+1}\equiv m\) by Euler's theorem (as \(\gcd(8,55)=1\)), so \(17^{27}\equiv8\pmod{55}\). Anyone who can factorise \(n\) can find \(d\); with large primes factorising is far too slow, which keeps the key secret.

12. Answer to Question 12

    1. \(36^8=\) 2 821 109 907 456 (about \(2.8\times10^{12}\)).
    2. Complement: subtract the passwords with letters only. \(36^8-26^8=2\,821\,109\,907\,456-208\,827\,064\,576=\) 2 612 282 842 880.
    3. \(\dfrac{2.82\times10^{12}}{10^9}\approx2821\) s, about 47 minutes: far too weak.
    4. \(62^8\approx2.18\times10^{14}\), so \(\left(\dfrac{62}{36}\right)^8\approx\) 77 times more.

13. Answer to Question 13

    1. The complete graph \(K_8\), with \(\dbinom82=\) 28 matches.
    2. Each vertex has degree 7: every team plays 7 matches. Check: \(\dfrac{8\times7}2=28\).
    3. Each team needs 7 evenings for its 7 matches. With 8 teams, 4 matches can be played each evening, and \(28\div4=7\) evenings is enough with a good timetable.
    4. \(\dbinom92=\) 36 matches. With 9 teams (an odd number) one team must rest each evening, so at most 4 matches are played per evening and 9 evenings are needed.

14. Answer to Question 14

    1. Handshaking lemma: \(\dfrac{2+3+4+2+3+2}2=\) 8 streets.
    2. No: an Euler circuit needs every degree even, but \(B\) and \(E\) have odd degree.
    3. Exactly two vertices have odd degree, so an Euler trail exists: it must start at \(B\) and finish at \(E\) (or the reverse).
    4. A new street between \(B\) and \(E\) makes both degrees even (4), and then an Euler circuit exists, so the lorry can start and end at \(A\).

15. Answer to Question 15

    1. The left end is covered either by one domino across (leaving a \(2\times(n-1)\) strip: \(t_{n-1}\) ways) or by two dominoes along, one above the other (leaving \(2\times(n-2)\): \(t_{n-2}\) ways).
    2. \(t_6=13\), \(t_7=21\), \(t_8=34\), \(t_9=55\), \(t_{10}=\) 89.
    3. \(r^2-r-1=0\) gives \(r=\dfrac{1\pm\sqrt{1+4}}2\).
    4. True for \(n=1,2\) (\(1\le1\), \(2\le2\)). If true for \(n-1\) and \(n-2\), then \(t_n\le2^{n-2}+2^{n-3}=3\times2^{n-3}<4\times2^{n-3}=2^{n-1}\). By strong induction the bound holds for all \(n\).
    5. The ratio of consecutive terms tends to \(\phi\approx\) 1.618, since \(t_n\approx\dfrac{\phi^{n+1}}{\sqrt5}\) and \(|\psi|<1\) makes the other term negligible.

16. Answer to Question 16

    1. \(a_2=8+6=14\), \(a_3=14+48=62\), \(a_4=62+84=\) 146.
    2. \(r^2=r+6\), i.e. \((r-3)(r+2)=0\): \(r=3\) and \(r=-2\).
    3. \(A+B=1\) and \(3A-2B=8\). Adding twice the first: \(5A=10\), so \(A=2\) and \(B=-1\): \(a_n=2\times3^n-(-2)^n\).
    4. \(a_4=2\times81-16=146\), as in the table. \(a_{10}=2\times59\,049-1024=\) 117 074.
    5. The \(3^n\) term dominates: the population roughly triples every season, with the \((-2)^n\) term causing a small alternating correction.

17. Answer to Question 17

    1. \(x\equiv3\pmod4\), \(x\equiv2\pmod5\), \(x\equiv1\pmod7\).
    2. The moduli 4, 5, 7 are pairwise coprime and \(4\times5\times7=140\).
    3. From \(x\equiv1\pmod7\): \(x=1,8,15,22,29,\dots\). Those \(\equiv2\pmod5\): \(22,57,92,127,\dots\) (step 35). Of \(22,57,92,127\), only \(127\equiv3\pmod4\). So \(x\equiv127\pmod{140}\).
    4. Between 100 and 300: 127 or 267.
    5. 267 members. Check: \(267=66\times4+3=53\times5+2=38\times7+1\).

18. Answer to Question 18

    1. The degrees are \(3,3,3,2,3,2\), with sum 16, so there are 8 edges: \(MP\), \(MC\), \(MH\), \(PC\), \(PE\), \(CB\), \(BE\), \(EH\).
    2. \(M\), \(P\) and \(C\) all clash with each other (a triangle), so they need three different sessions.
    3. Session 1: M, B. Session 2: P, H. Session 3: C, E. No pair inside a session clashes.
    4. Three sessions are necessary and sufficient: the chromatic number is 3.
    5. Adding the edge \(BH\): the colouring above puts \(B\) in 1 and \(H\) in 2, so it still works. Yes, 3 sessions are enough.

19. Answer to Question 19

    1. \(6,48,342,2400\) are multiples of 6 (\(1,8,57,400\) times) and \(8,80,728,6560\) are multiples of 8 (\(1,10,91,820\) times).
    2. Base: \(7-1=6\). Step: if \(7^k-1=6m\), then \(7^{k+1}-1=7(7^k-1)+6=42m+6=6(7m+1)\).
    3. Base: \(9-1=8\). Step: if \(3^{2k}-1=8m\), then \(3^{2k+2}-1=9(3^{2k}-1)+8=8(9m+1)\).
    4. Base: \(1\cdot1!=1=2!-1\). Step: if the sum up to \(k\) is \((k+1)!-1\), adding \((k+1)(k+1)!\) gives \((k+1)!(1+k+1)-1=(k+2)!-1\).

20. Answer to Question 20

    1. \(25+12+6+3+1=\) 47, so \(2^{47}\) divides \(50!\).
    2. Zeros come from factors \(10=2\times5\), and fives are rarer. For \(100!\): \(20+4=\) 24 zeros. For \(1000!\): \(200+40+8+1=\) 249 zeros.
    3. \(6!=720=102\times7+6\equiv-1\pmod7\). \(10!=3\,628\,800=329\,890\times11+10\equiv-1\pmod{11}\).
    4. Both \(a\) and \(b\) are distinct factors of \((n-1)!\), so \(ab=n\) divides it and \((n-1)!\equiv0\not\equiv-1\). (If \(n=p^2\) with \(p>2\), then \(p\) and \(2p\) both appear, giving the same conclusion; \(n=4\) gives \(3!\equiv2\).)