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

8.02e Finite (modular) arithmetic: integers modulo n8.02f Single linear congruences: solve ax = b (mod n)
Sort by: Default | Easiest first | Hardest first
Edexcel FP2 AS 2020 June Q2
6 marks Standard +0.3
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. Without performing any division, explain why 8184 is divisible by 6
  2. Use the Euclidean algorithm to find integers \(a\) and \(b\) such that $$27 a + 31 b = 1$$