Euclidean algorithm with linear combination

Questions requiring use of the Euclidean algorithm followed by back-substitution to express the HCF as a linear combination (ax + by = gcd).

2 questions · Standard +0.0

Sort by: Default | Easiest first | Hardest first
Edexcel FP2 AS 2020 June Q2
6 marks Standard +0.3
  1. The highest common factor of 963 and 657 is \(c\).
    1. Use the Euclidean algorithm to find the value of \(c\).
    2. Hence find integers \(a\) and \(b\) such that
    $$963 a + 657 b = c$$
Edexcel FP2 AS Specimen Q2
6 marks Moderate -0.3
  1. (i) Without performing any division, explain why 8184 is divisible by 6
    (ii) Use the Euclidean algorithm to find integers \(a\) and \(b\) such that
$$27 a + 31 b = 1$$