Further Maths Number theory Practice Questions

Free Further Maths Number theory practice questions with full step-by-step worked solutions. Covers division-algorithm, divisibility, remainders, euclidean-algorithm. Practise exam-style problems and check your method.

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.
Show worked solution

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
The Euclidean algorithm is applied to 322322 and 7070. Which of the following is the correct first line?
Show worked solution

Worked solution

  1. Take the floor to get the quotient

    q=⌊32270⌋=4q=\left\lfloor\frac{322}{70}\right\rfloor=4

    The division algorithm demands the largest multiple of 7070 that does not exceed 322322.

  2. Compute the remainder

    r=322−4×70=42r=322-4\times70=42

    What is left after removing 4×704\times70 is the remainder.

  3. Check the range condition

    0≤42<700\le42<70

    A line of the Euclidean algorithm is only correct if the remainder is non-negative and smaller than the divisor.

  4. Select the correct first line

    322=4×70+42322=4\times70+42

    This is the unique line with 0≤r<700\le r<70.

Answer
322=4×70+42322=4\times70+42
Question 3
4 marksintermediate
Let f(n)=8n−1f(n)=8^{n}-1. In a proof by induction that f(n)f(n) is divisible by 77 for all positive integers nn, which of the following is the correct simplified form of f(k+1)−f(k)f(k+1)-f(k)?
Show worked solution

Worked solution

  1. State the inductive hypothesis

    f(k)=7M for some integer Mf\left(k\right)=7M\ \text{for some integer}\ M

    Assume the result holds for some n=kn=k; this is what the inductive step is allowed to use.

  2. Write down f(k+1)f\left(k+1\right)

    f(k+1)=8×8k−1f\left(k+1\right)=8\times8^{k}-1

    Replacing nn by k+1k+1 is the whole of the inductive step's raw material.

  3. Subtract f(k)f\left(k\right)

    f(k+1)−f(k)=8×8k−1−(8k−1)=7×8kf\left(k+1\right)-f\left(k\right)=8\times8^{k}-1-\left(8^{k}-1\right)=7\times8^{k}

    This particular multiple of f(k)f\left(k\right) is subtracted because it cancels the dominant term and leaves something visibly divisible by 77.

  4. Rearrange to isolate f(k+1)f\left(k+1\right)

    f(k+1)=f(k)+7×8kf\left(k+1\right)=f\left(k\right)+7\times8^{k}

    Everything now depends on f(k)f\left(k\right), which the hypothesis controls.

  5. Substitute the inductive hypothesis

    f(k+1)=1×7M+7×8kf\left(k+1\right)=1\times7M+7\times8^{k}

    The first term is a multiple of 77 by the hypothesis, and the second is 77 times the integer 8k8^{k}.

  6. Factorise out 77

    f(k+1)=7(M+8k)f\left(k+1\right)=7\left(M+8^{k}\right)

    The bracket is an integer, so 77 divides f(k+1)f\left(k+1\right).

  7. Select the correct simplified form

    f(k+1)−f(k)=7×8kf\left(k+1\right)-f\left(k\right)=7\times8^{k}

    This is the expression the inductive step produces.

Answer
7×8k7\times8^{k}
Question 4
6 markshard
Which of the following is the least residue of 210002^{1000} modulo 1313?
Show worked solution

Worked solution

  1. Check that Fermat's little theorem applies

    13 is prime and 13∤213\ \text{is prime and}\ 13\nmid2

    The theorem needs a prime modulus and a base that the prime does not divide.

  2. Apply Fermat's little theorem

    212≡1(mod13)2^{12}\equiv1\pmod{13}

    Raising 22 to the power 1212 returns 11, so blocks of 1212 in the exponent cost nothing.

  3. Divide the exponent by 1212 using the division algorithm

    1000=12×83+41000=12\times83+4

    The quotient counts the whole blocks of 1212 and the remainder is what is left over.

  4. Split the power at that division

    21000=(212)83×242^{1000}=\left(2^{12}\right)^{83}\times2^{4}

    The index laws separate the part that Fermat's little theorem kills from the part that has to be evaluated.

  5. Replace the Fermat block by 11

    21000≡183×24≡24(mod13)2^{1000}\equiv1^{83}\times2^{4}\equiv2^{4}\pmod{13}

    The whole computation has collapsed to a power with exponent 44.

  6. Square to reach the exponent 22

    22≡22=4≡4(mod13)2^{2}\equiv2^{2}=4\equiv4\pmod{13}

    Reducing modulo 1313 after every squaring keeps the arithmetic small.

  7. Square to reach the exponent 44

    24≡42=16≡3(mod13)2^{4}\equiv4^{2}=16\equiv3\pmod{13}

    Reducing modulo 1313 after every squaring keeps the arithmetic small.

  8. Compare with the options

    21000≡3(mod13)2^{1000}\equiv3\pmod{13}

    Only one of the five options is this least residue.

  9. Check the order of 22 modulo 1313

    ord⁡13(2)=12\operatorname{ord}_{13}\left(2\right)=12

    The exponent may be reduced modulo the order, which gives the same answer.

  10. Note that the residue must lie in the correct range

    0≤3<130\le3<13

    Any option outside this range could be rejected immediately.

  11. Select the least residue

    21000≡3(mod13)2^{1000}\equiv3\pmod{13}

    This is the remainder when the power is divided by 1313.

Answer
33
Question 5
9 markschallenging
Which of the following is the least residue of 720247^{2024} modulo 10001000?
Show worked solution

Worked solution

  1. Write the exponent as a sum of powers of 22

    2024=1024+512+256+128+64+32+82024=1024+512+256+128+64+32+8

    Repeated squaring produces exactly these powers of 77.

  2. Square to reach the exponent 22

    72≡72=49≡49(mod1000)7^{2}\equiv7^{2}=49\equiv49\pmod{1000}

    Reducing modulo 10001000 after every squaring keeps the arithmetic small.

  3. Square to reach the exponent 44

    74≡492=2401≡401(mod1000)7^{4}\equiv49^{2}=2401\equiv401\pmod{1000}

    Reducing modulo 10001000 after every squaring keeps the arithmetic small.

  4. Square to reach the exponent 88

    78≡4012=160801≡801(mod1000)7^{8}\equiv401^{2}=160801\equiv801\pmod{1000}

    Reducing modulo 10001000 after every squaring keeps the arithmetic small.

  5. Square to reach the exponent 1616

    716≡8012=641601≡601(mod1000)7^{16}\equiv801^{2}=641601\equiv601\pmod{1000}

    Reducing modulo 10001000 after every squaring keeps the arithmetic small.

  6. Square to reach the exponent 3232

    732≡6012=361201≡201(mod1000)7^{32}\equiv601^{2}=361201\equiv201\pmod{1000}

    Reducing modulo 10001000 after every squaring keeps the arithmetic small.

  7. Square to reach the exponent 6464

    764≡2012=40401≡401(mod1000)7^{64}\equiv201^{2}=40401\equiv401\pmod{1000}

    Reducing modulo 10001000 after every squaring keeps the arithmetic small.

  8. Square to reach the exponent 128128

    7128≡4012=160801≡801(mod1000)7^{128}\equiv401^{2}=160801\equiv801\pmod{1000}

    Reducing modulo 10001000 after every squaring keeps the arithmetic small.

  9. Square to reach the exponent 256256

    7256≡8012=641601≡601(mod1000)7^{256}\equiv801^{2}=641601\equiv601\pmod{1000}

    Reducing modulo 10001000 after every squaring keeps the arithmetic small.

  10. Square to reach the exponent 512512

    7512≡6012=361201≡201(mod1000)7^{512}\equiv601^{2}=361201\equiv201\pmod{1000}

    Reducing modulo 10001000 after every squaring keeps the arithmetic small.

  11. Square to reach the exponent 10241024

    71024≡2012=40401≡401(mod1000)7^{1024}\equiv201^{2}=40401\equiv401\pmod{1000}

    Reducing modulo 10001000 after every squaring keeps the arithmetic small.

  12. Multiply in the factor 7327^{32}

    801×201=161001≡1(mod1000)801\times201=161001\equiv1\pmod{1000}

    The exponent 20242024 is the sum 8+328+32, so these are exactly the powers that must be multiplied together.

  13. Multiply in the factor 7647^{64}

    1×401=401≡401(mod1000)1\times401=401\equiv401\pmod{1000}

    The exponent 20242024 is the sum 8+32+648+32+64, so these are exactly the powers that must be multiplied together.

  14. Multiply in the factor 71287^{128}

    401×801=321201≡201(mod1000)401\times801=321201\equiv201\pmod{1000}

    The exponent 20242024 is the sum 8+32+64+1288+32+64+128, so these are exactly the powers that must be multiplied together.

  15. Multiply in the factor 72567^{256}

    201×601=120801≡801(mod1000)201\times601=120801\equiv801\pmod{1000}

    The exponent 20242024 is the sum 8+32+64+128+2568+32+64+128+256, so these are exactly the powers that must be multiplied together.

  16. Multiply in the factor 75127^{512}

    801×201=161001≡1(mod1000)801\times201=161001\equiv1\pmod{1000}

    The exponent 20242024 is the sum 8+32+64+128+256+5128+32+64+128+256+512, so these are exactly the powers that must be multiplied together.

  17. Select the least residue

    72024≡401(mod1000)7^{2024}\equiv401\pmod{1000}

    This is the remainder when the power is divided by 10001000.

Answer
401401

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 QuestionsWorked Solutions

Related Further Pure topics

Conic sections 1Conic sections 2Further complex numbersGroupsInequalitiesFurther integration techniques