Further Pure 2: Number theoryEdexcel A-Level Further Maths: Topic test

1. 1
   The Euclidean algorithm is applied to the integers $1001$ and $364$.

   (a)

   What is the remainder in the first step of the algorithm?

   [1 mark]

   • A$273$
   • B$637$
   • C$2$
   • D$91$

   (b)

   What is the highest common factor of $1001$ and $364$?

   [1 mark]

   • A$7$
   • B$13$
   • C$91$
   • D$273$

   (c)

   Use back substitution to express the highest common factor in the form $364p+1001q$, where $p$ and $q$ are integers.

   [2 marks]

   Total for question 1: 4 marks

2. 2
   The integers $x$ and $y$ satisfy $x\equiv5\pmod 8$ and $y\equiv3\pmod 8$.

   (a)

   What is the least non-negative residue of $x+y$ modulo $8$?

   [1 mark]

   • A$8$
   • B$2$
   • C$0$
   • D$7$

   (b)

   What is the least non-negative residue of $x^2y$ modulo $8$?

   [1 mark]

   • A$1$
   • B$3$
   • C$5$
   • D$7$

   (c)

   Show that $x^2+y^2\equiv2\pmod 8$.

   [2 marks]

   Total for question 2: 4 marks

3. 3
   Work modulo $13$, which is prime.

   (a)

   Use Fermat's little theorem to find the least positive residue of $2^{100}$ modulo $13$.

   [3 marks]

   (b)

   Use the Euclidean algorithm and back substitution to find the multiplicative inverse of $5$ modulo $13$, and hence solve $5x\equiv4\pmod{13}$.

   [4 marks]

   Total for question 3: 7 marks

4. 4
   The positive integer $N$ satisfies $N\equiv3\pmod5$ and $N\equiv4\pmod7$.

   (a)

   Show that $N\equiv18\pmod{35}$.

   [6 marks]

   (b)

   (i) Find the number of integers $N$ with $100\le N\le999$ that satisfy both congruences.
   (ii) The three-digit solutions are written on cards, one per card. Four cards are chosen from all of these cards. Find the number of different choices of four cards that include both the smallest and the largest of the numbers.

   [6 marks]

   Total for question 4: 12 marks

5. 5
   A running club has 15 members. A relay team of 4 runners is to be chosen.

   (a)

   How many different relay teams are possible if the order in which the four run matters?

   [1 mark]

   • A$1365$
   • B$3003$
   • C$50\,625$
   • D$32\,760$

   (b)

   The club also picks a training group of 4 members, where the order is irrelevant. How many different groups are possible?

   [1 mark]

   • A$1365$
   • B$32\,760$
   • C$60$
   • D$3003$

   (c)

   Sam is a member of the club. In how many ways can a relay team be chosen if Sam must run the final leg?

   [2 marks]

   Total for question 5: 4 marks

6. 6
   The six-digit number $N=704\,935$ is written in base ten.

   (a)

   What is the remainder when $N$ is divided by $9$?

   [1 mark]

   • A$0$
   • B$1$
   • C$7$
   • D$28$

   (b)

   Which one of these integers is a factor of $N$?

   [1 mark]

   • A$2$
   • B$3$
   • C$4$
   • D$11$

   (c)

   The final digit $5$ is replaced by a digit $d$ to give a new number $\overline{70493d}$. Find the value of $d$ for which the new number is divisible by $9$.

   [2 marks]

   Total for question 6: 4 marks

7. 7
   Let $a=1105$ and $b=425$.

   (a)

   Use the Euclidean algorithm to find the highest common factor of $a$ and $b$.

   [3 marks]

   (b)

   Hence find integers $m$ and $n$ such that $1105m+425n=85$, and deduce integers $p$ and $q$ such that $1105p+425q=170$.

   [4 marks]

   Total for question 7: 7 marks

8. 8
   $S$ is the set of positive integers less than $500$.

   (a)

   Find the number of integers in $S$ that are divisible by neither $3$ nor $5$.

   [6 marks]

   (b)

   Use Fermat's little theorem to prove that $n^5-n$ is divisible by $30$ for every integer $n$ in $S$.

   [6 marks]

   Total for question 8: 12 marks

End of questions