Fermat's little theorem and congruence equations

Fermat's little theorem and congruence equations Test

Spec 5.4 · Edexcel A-Level Further Maths: Subtopic test

Studying this course? Keep your progress in one place.

Two ways to do this test

Question by question

One question at a time. Each answer is marked the moment you hand it in, so you learn as you go. Drago helps if you get stuck. All 10 questions, or just 5.

Exam mode

The whole paper in one go, timed like the real exam. Nothing is marked until you hand it in, then you get every mark explained.

10 questions, 27 marks

Edexcel A-Level Further Maths

Fermat's little theorem and congruence equations

Total 27 marks

Name

Class

Date

  1. 1
    Work modulo 77, which is prime.
    (a)
    Use Fermat's little theorem to find the least non-negative residue of 4204^{20} modulo 77.
    [1 mark]
    • A11
    • B22
    • C44
    • D66
    (b)
    Find the least non-negative residue of 31003^{100} modulo 77.
    [1 mark]
    • A11
    • B33
    • C44
    • D22
    (c)
    Find the remainder when 125012^{50} is divided by 77.
    [2 marks]

    Total for question 1: 4 marks

  2. 2
    Linear congruences of the form ax≡b(modn)ax\equiv b\pmod n are to be solved for integers xx.
    (a)
    Which one of the following congruences has no solutions?
    [1 mark]
    • A3x≡4(mod7)3x\equiv4\pmod7
    • B4x≡6(mod10)4x\equiv6\pmod{10}
    • C5x≡2(mod12)5x\equiv2\pmod{12}
    • D6x≡4(mod9)6x\equiv4\pmod9
    (b)
    How many solutions, modulo 1515, does 6x≡9(mod15)6x\equiv9\pmod{15} have?
    [1 mark]
    • A33
    • B11
    • C66
    • D00
    (c)
    Solve 7x≡3(mod11)7x\equiv3\pmod{11}.
    [2 marks]

    Total for question 2: 4 marks

  3. 3
    Consider the numbers 1717 and 4040.
    (a)
    Use the Euclidean algorithm to show that 1717 and 4040 are coprime.
    [3 marks]
    (b)
    Hence find the multiplicative inverse of 1717 modulo 4040, and solve 17x≡9(mod40)17x\equiv9\pmod{40}.
    [4 marks]

    Total for question 3: 7 marks

  4. 4
    Questions on powers modulo a prime and on linear congruences.
    (a)
    Use Fermat's little theorem with the prime 1313 to show that 3200+2100+13^{200}+2^{100}+1 is divisible by 1313.
    [6 marks]
    (b)
    Determine whether 15x≡9(mod21)15x\equiv9\pmod{21} has solutions. If it does, find all solutions with 0≤x<210\leq x<21.
    [6 marks]

    Total for question 4: 12 marks

End of questions

Subtopic tests