Number theory Worked Solutions — Further Maths Maths

Fully worked, step-by-step solutions to Further Maths Number theory questions. See exactly how to solve problems on division-algorithm, divisibility, remainders, euclidean-algorithm.

division-algorithmdivisibilityremainderseuclidean-algorithmgcdlcm
Further Maths70 questionsStep-by-step solutions
Question 1
2 markseasy
Apply the division algorithm to a=137a=137 and b=11b=11: find the unique integers qq and rr for which a=bq+ra=bq+r and 0≤r<b0\le r<b.

Worked solution

  1. Find the quotient

    q=⌊13711⌋=12q=\left\lfloor\frac{137}{11}\right\rfloor=12

    The quotient is the floor of ab\frac{a}{b}, so it is rounded downwards.

  2. Find the remainder

    r=137−11×12=5r=137-11\times12=5

    The remainder is what is left when bqbq is taken away from aa.

  3. Check that the remainder is in range

    0≤5<110\le5<11

    The division algorithm insists on a remainder below the divisor, which fixes qq and rr uniquely.

  4. State the quotient and the remainder

    137=11×12+5137=11\times12+5

    This is the unique pair with 0≤r<110\le r<11.

Answer
q=12, r=5q=12,\ r=5
Question 2
2 markseasy
Apply the division algorithm to a=2024a=2024 and b=15b=15: find the unique integers qq and rr for which a=bq+ra=bq+r and 0≤r<b0\le r<b.

Worked solution

  1. Find the quotient

    q=⌊202415⌋=134q=\left\lfloor\frac{2024}{15}\right\rfloor=134

    The quotient is the floor of ab\frac{a}{b}, so it is rounded downwards.

  2. Find the remainder

    r=2024−15×134=14r=2024-15\times134=14

    The remainder is what is left when bqbq is taken away from aa.

  3. Check that the remainder is in range

    0≤14<150\le14<15

    The division algorithm insists on a remainder below the divisor, which fixes qq and rr uniquely.

  4. State the quotient and the remainder

    2024=15×134+142024=15\times134+14

    This is the unique pair with 0≤r<150\le r<15.

Answer
q=134, r=14q=134,\ r=14
Question 3
2 markseasy
Apply the division algorithm to a=−58a=-58 and b=9b=9: find the unique integers qq and rr for which a=bq+ra=bq+r and 0≤r<b0\le r<b.

Worked solution

  1. Find the quotient

    q=⌊−589⌋=−7q=\left\lfloor\frac{-58}{9}\right\rfloor=-7

    The quotient is the floor of ab\frac{a}{b}, so it is rounded downwards, which for a negative aa means away from zero.

  2. Find the remainder

    r=−58−9×(−7)=5r=-58-9\times\left(-7\right)=5

    The remainder is what is left when bqbq is taken away from aa.

  3. Check that the remainder is in range

    0≤5<90\le5<9

    The division algorithm insists on a remainder below the divisor, which fixes qq and rr uniquely.

  4. State the quotient and the remainder

    −58=9×(−7)+5-58=9\times\left(-7\right)+5

    This is the unique pair with 0≤r<90\le r<9.

Answer
q=−7, r=5q=-7,\ r=5
Question 4
2 markseasy
Find the remainder when 43214321 is divided by 99.

Worked solution

  1. Divide 43214321 by 99

    4321=9×480+14321=9\times480+1

    The division algorithm writes aa as bq+rbq+r with 0≤r<b0\le r<b.

  2. Identify the remainder

    r=1r=1

    The remainder is the part of 43214321 that is not a multiple of 99.

  3. Write the result as a congruence

    4321≡1(mod9)4321\equiv1\pmod{9}

    A remainder statement and a congruence say exactly the same thing.

  4. State the remainder

    4321÷9 leaves remainder 14321\div9\ \text{leaves remainder}\ 1

    This is the least residue of 43214321 modulo 99.

Answer
11
Question 5
2 markseasy
Use the Euclidean algorithm to find gcd⁡(84,30)\gcd\left(84,30\right).

Worked solution

  1. Divide 8484 by 3030

    84=2×30+2484=2\times30+24

    The remainder 2424 is smaller than the divisor 3030, so the algorithm continues with the pair (30,24)\left(30,24\right).

  2. Divide 3030 by 2424

    30=1×24+630=1\times24+6

    The remainder 66 is smaller than the divisor 2424, so the algorithm continues with the pair (24,6)\left(24,6\right).

  3. Divide 2424 by 66: the remainder is now zero

    24=4×6+024=4\times6+0

    The last non-zero remainder is 66, so the algorithm stops and gcd⁡(84,30)=6\gcd\left(84,30\right)=6.

  4. State the gcd

    gcd⁡(84,30)=6\gcd\left(84,30\right)=6

    The last non-zero remainder produced by the algorithm is the gcd.

Answer
66

Unlock 65 more Number theory questions

Create a free account to work through every Further Maths Number theory question with instant step-by-step worked solutions, progress tracking and interactive lessons.

  • Full worked solutions for every question
  • Interactive lessons and instant feedback
  • Track your mastery across every topic
Create a Free Account

No card required · Free forever

More Number theory practice

Hard QuestionsPractice Questions

Related Further Pure topics

Conic sections 1Conic sections 2Further complex numbersGroupsInequalitiesFurther integration techniques