Further Mathematics · OCR H245 · Option A · Topic 8.02

Number theory

Number bases, divisibility tests, the division algorithm, finite (modular) arithmetics, prime numbers, Euclid's lemma, Fermat's little theorem and more.

  • 9 sub-topics
  • Taught in Year 13
  • 140 practice questions
  • 9 animated lessons
Practice questions (140) Lessons Worksheets coming soon All OCR Further Mathematics topics

What the specification says

Every sub-topic OCR 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. 8.02aNumber basesY13
  2. 8.02b-cDivisibility testsY13
  3. 8.02dThe division algorithmY13
  4. 8.02e-hFinite (modular) arithmeticsY13
  5. 8.02i-jPrime numbersY13
  6. 8.02kEuclid's lemmaY13
  7. 8.02lFermat's little theoremY13
  8. 8.02m-nThe order of a modulo pY13
  9. 8.02oBinomial theoremY13

Try 3 questions

Easy, medium and hard questions from this topic, each with a worked solutions and the mark for every step. All 140 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