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

Let \(a=1071\) and \(b=462\).

1. Use the Euclidean algorithm to find \(\gcd(1071,462)\). [3 marks]
2. Work backwards to write the gcd in the form \(1071x+462y\) with integers \(x,y\). [3 marks]
3. Find \(\operatorname{lcm}(1071,462)\). [2 marks]

Work modulo the number given in each part.

1. Find the inverse of 11 modulo 26. [3 marks]
2. Solve \(11x\equiv5\pmod{26}\). [2 marks]
3. Solve \(6x\equiv4\pmod{10}\), giving all solutions modulo 10. [3 marks]

Use Fermat's little theorem or Euler's theorem; do not use a calculator for the powers.

1. Find \(5^{100}\bmod13\). [3 marks]
2. Compute \(\varphi(360)\). [2 marks]
3. Find the last digit of \(7^{222}\). [3 marks]

Solve each system of congruences.

1. \(x\equiv2\pmod3\), \(x\equiv3\pmod5\), \(x\equiv2\pmod7\). [4 marks]
2. \(x\equiv1\pmod4\), \(x\equiv4\pmod9\). [3 marks]

Answer each counting question, showing the principle used.

1. How many different arrangements are there of the letters of BANANA? [2 marks]
2. In how many ways can a committee of 4 be chosen from 12 people? [2 marks]
3. How many integers from 1 to 1000 are divisible by 3, 5 or 7? [4 marks]

Answer each part about simple graphs.

1. A graph has degree sequence \(4,4,3,3,2,2\). How many edges does it have? Does it have an Euler circuit or an Euler trail? [3 marks]
2. A tree has 15 vertices. How many edges does it have? [1 mark]
3. For which \(n\) does the complete graph \(K_n\) have an Euler circuit? How many edges does \(K_6\) have? [3 marks]

A kitchen floor is a rectangle 3.36 m by 2.52 m. A builder wants to cover it exactly with identical square tiles, as large as possible, without cutting any tile.

1. Explain why the side of the tile (in cm) must be a common divisor of 336 and 252.
2. Use the Euclidean algorithm to find the largest possible tile.
3. How many tiles are needed?
4. Tiles of that size cost £7.50 each. Find the total cost, and compare with 28 cm tiles at £1.20 each.

A post office only has 5p and 8p stamps left. A parcel needs exactly 79p of postage.

1. Explain why the equation \(5x+8y=79\) has integer solutions.
2. Find one solution using \(5\times(-3)+8\times2=1\).
3. Write the general solution and list all solutions with \(x,y\ge0\).
4. Show that 27p cannot be made, and explain why every amount from 28p upwards can (the Frobenius number is \(5\times8-5-8\)).

1 January 2027 is a Friday. Days of the week repeat every 7 days, so we work modulo 7 (Friday \(=0\), Saturday \(=1\), …).

1. 2027 is not a leap year. Use \(365\equiv1\pmod7\) to find the day of the week of 1 January 2028.
2. What day of the week is 100 days after 1 January 2027?
3. 2028 is a leap year. On what day of the week does 1 January 2029 fall?
4. Explain why the same calendar can be reused only after several years.

An ISBN-10 \(d_1d_2\dots d_{10}\) is valid when \(10d_1+9d_2+8d_3+\dots+2d_9+1\cdot d_{10}\equiv0\pmod{11}\) (the symbol X stands for 10).

1. Find the weighted sum of the first nine digits.
2. Find the check digit.
3. A librarian types the 4 in position 5 as a 7. Show that the error is detected.
4. Explain why any single wrong digit is always detected (use that 11 is prime).

Two friends use a small RSA code. The public key is \(n=55=5\times11\) and \(e=3\).

1. Find \(\varphi(55)\).
2. Find the private key \(d\) with \(3d\equiv1\pmod{\varphi(n)}\).
3. Encrypt the message \(m=8\) by computing \(c=m^3\bmod55\).
4. Decryption computes \(c^d\bmod55\). Explain why this returns 8 and why real RSA uses primes with hundreds of digits.

A website requires passwords of exactly 8 characters, each a lower-case letter (26 choices) or a digit (10 choices).

1. How many passwords are possible?
2. How many contain at least one digit?
3. An attacker can test \(10^9\) passwords per second. How long does it take to try them all?
4. How many times more passwords are there if upper-case letters are also allowed?

Eight five-a-side football teams play a league where every team plays every other team exactly once. Model the teams as vertices and the matches as edges.

1. Which graph is this? How many matches are played?
2. What is the degree of each vertex, and what does it mean?
3. Each team plays at most one match per evening. Explain why at least 7 evenings are needed.
4. The league adds a ninth team. How many matches now, and why can no evening have all teams playing?

A gritting lorry must treat every street of a village exactly once. The junctions \(A\) to \(F\) and the number of streets meeting at each are shown.

1. How many streets are there?
2. Can the lorry start and finish at the depot at \(A\) without repeating a street? Explain.
3. Where must the lorry start and finish to treat each street exactly once?
4. The council adds one street to make an Euler circuit possible. Between which junctions should it go?

A garden path is a \(2\times n\) strip made of square slabs. It is covered by \(1\times2\) paving stones (dominoes), each placed either across or along the path. Let \(t_n\) be the number of tilings.

1. Explain why \(t_n=t_{n-1}+t_{n-2}\) for \(n\ge3\) by looking at the left end of the strip.
2. Compute \(t_{10}\).
3. Show that the characteristic equation \(r^2=r+1\) has roots \(\phi=\dfrac{1+\sqrt5}2\) and \(\psi=\dfrac{1-\sqrt5}2\).
4. Prove by strong induction that \(t_n\le2^{n-1}\) for all \(n\ge1\).
5. Estimate \(\dfrac{t_{20}}{t_{19}}\) and explain.

Ecologists model a population of beetles (in hundreds) by \(a_n=a_{n-1}+6a_{n-2}\) with \(a_0=1\) and \(a_1=8\), where \(n\) counts seasons.

1. Complete the table.
2. Find the roots of the characteristic equation.
3. Find the closed form \(a_n=A\cdot3^n+B(-2)^n\).
4. Check your formula for \(n=4\) and find \(a_{10}\).
5. Describe the long-term growth.

A marching band has between 100 and 300 members. When they march in rows of 4, three are left over; in rows of 5, two are left over; in rows of 7, one is left over.

1. Write the information as three congruences.
2. Explain why the Chinese remainder theorem gives exactly one solution modulo 140.
3. Solve the system step by step.
4. Find all possible sizes of the band.
5. The band leader says there are more than 200. How many members are there?

A sixth-form college must timetable six exams: Maths (M), Physics (P), Chemistry (C), Biology (B), Economics (E) and History (H). Two exams that share a student cannot be in the same session. The clashes are listed below.

1. Draw the clash graph and count its edges using the handshaking lemma.
2. Explain why at least 3 sessions are needed.
3. Give a timetable with 3 sessions.
4. What is the chromatic number of the graph?
5. A new student takes both Biology and History. Can 3 sessions still be used?

Mathematical induction is the main tool for proving statements about all natural numbers. Prove each statement for all integers \(n\ge1\) and test it numerically first.

1. Check that every entry in the table has the divisibility claimed below.
2. Prove that \(6\) divides \(7^n-1\).
3. Prove that \(8\) divides \(3^{2n}-1\).
4. Prove that \(1\cdot1!+2\cdot2!+\dots+n\cdot n!=(n+1)!-1\).

Factorials contain many prime factors. Legendre's formula says that the power of a prime \(p\) in \(n!\) is \(\left\lfloor\frac np\right\rfloor+\left\lfloor\frac n{p^2}\right\rfloor+\left\lfloor\frac n{p^3}\right\rfloor+\cdots\).

1. Find the highest power of 2 dividing \(50!\).
2. How many zeros does \(100!\) end with? And \(1000!\)?
3. Check Wilson's theorem \((p-1)!\equiv-1\pmod p\) for \(p=7\) and \(p=11\).
4. Show that \((n-1)!\equiv0\pmod n\) when \(n=ab\) with \(1\lt a\lt b\lt n\), so Wilson's congruence characterises primes (apart from \(n=4\)).