Further Mathematics · Pearson Edexcel 9FM0 · Option FP2 · Topic 5

Number theory

Divisibility, the Euclidean algorithm, modular arithmetic, Fermat's little theorem and counting problems.

  • 7 sub-topics
  • Taught in Year 13
  • 125 practice questions
  • 7 animated lessons
Practice questions (125) Lessons Worksheets All Edexcel Further Mathematics topics

What the specification says

Every sub-topic Pearson Edexcel can examine in this topic, with its reference number from the official specification. The Y12 and Y13 tags show when each sub-topic is usually taught.

  1. 5.1Division algorithm and Euclidean algorithmY13
  2. 5.2Bézout's identityY13
  3. 5.3Modular arithmeticY13
  4. 5.4Fermat's little theoremY13
  5. 5.5Divisibility testsY13
  6. 5.6Solving congruence equationsY13
  7. 5.7CombinatoricsY13

Try 3 questions

Easy, medium and hard questions from this topic, each with a worked solutions and the mark for every step. All 125 questions in this topic, free, no account needed.

Number theory

Not needed for Year 12Easy

Euclidean algorithm · Year 13 · 2 marks

  1. Use the Euclidean algorithm to find gcd(210, 98).
    (2)

Check your answer before you look at the solution

Show worked solutionHide worked solution
  1. Repeated division: divisor becomes dividend.
  2. 1414

Total2

  • M
  • A
  • B
How did it go?

Report a problem with this question

Number theory

Not needed for Year 12Medium

The Euclidean algorithm · Year 13 · 4 marks

  1. (a)
    Use the Euclidean algorithm to find the highest common factor of 1037 and 391.
    (3)
  2. (b)
    Hence find the lowest common multiple of 1037 and 391.
    (1)
Show worked solutionHide worked solution

Part (a)3 marks

  1. Divide, then divide the divisor by the remainder.10371037=2×391+255,{}= 2 \times 391 + 255,391\quad 391=1×255+136{}= 1 \times 255 + 136
  2. Continue until the remainder is zero.255255=1×136+119,{}= 1 \times 136 + 119,136\quad 136=1×119+17,{}= 1 \times 119 + 17,119\quad 119=7×17+0{}= 7 \times 17 + 0
  3. The last non-zero remainder.hcf(1037,391)=17\text{hcf}(1037, 391) = 17

Part (b)1 mark

  1. 1037×39117=23851\frac{1037 \times 391}{17} = 23851

Total4

  • M
  • A
  • B
How did it go?

Report a problem with this question

Number theory

Not needed for Year 12Hard

Bézout's identity · Year 13 · 6 marks

  1. (a)
    Use the Euclidean algorithm to find integers xx and yy such that 51x+16y=151x + 16y = 1.
    (4)
  2. (b)
    Hence find the general solution, in integers, of 51x+16y=251x + 16y = 2.
    (2)
Show worked solutionHide worked solution

Part (a)4 marks

  1. Run the algorithm first.5151=3×16+3,{}= 3 \times 16 + 3,16\quad 16=5×3+1,{}= 5 \times 3 + 1,3\quad 3=3×1+0{}= 3 \times 1 + 0
  2. Express each remainder in terms of 51 and 16.work back through the steps\text{work back through the steps}
  3. Check: 51×(−5)51 \times (-5)+16×(16){}+ 16 \times (16)=1{}= 1.x=−5, y=16x = -5, \ y = 16

Part (b)2 marks

  1. Scale by 2, then add any multiple of (16, −51), k ∈ ℤ.x=−10+16k, y=32−51kx = -10 + 16k, \ y = 32 - 51k

Total6

  • M
  • A
  • B
How did it go?

Report a problem with this question