Euclidean algorithm with applications

Questions using the Euclidean algorithm and linear combinations to solve further problems such as linear congruences, modular inverses, or Diophantine equations.

5 questions · Standard +0.6

Sort by: Default | Easiest first | Hardest first
Edexcel FP2 AS 2022 June Q4
11 marks Standard +0.8
4. In this question you must show all stages of your working. Solutions relying on calculator technology are not acceptable.
  1. (a) Use the Euclidean algorithm to find the highest common factor \(h\) of 416 and 72
    (b) Hence determine integers \(a\) and \(b\) such that $$416 a + 72 b = h$$ (c) Determine the value \(c\) in the set \(\{ 0,1,2 \ldots , 415 \}\) such that $$23 \times 72 \equiv c ( \bmod 416 )$$
  2. Evaluate \(5 ^ { 10 } ( \bmod 13 )\) giving your answer as the smallest positive integer solution.
Edexcel FP2 2021 June Q3
8 marks Standard +0.3
  1. (a) Use the Euclidean Algorithm to find integers \(a\) and \(b\) such that
$$125 a + 87 b = 1$$ (b) Hence write down a multiplicative inverse of 87 modulo 125
(c) Solve the linear congruence $$87 x \equiv 16 ( \bmod 125 )$$
Edexcel FP2 2022 June Q4
7 marks Standard +0.8
  1. (a) Use the Euclidean algorithm to show that 124 and 17 are relatively prime (coprime).
    (b) Hence solve the equation
$$124 x + 17 y = 10$$ (c) Solve the congruence equation $$124 x \equiv 6 \bmod 17$$
Edexcel FP2 2023 June Q4
9 marks Standard +0.3
  1. (a) Use the Euclidean algorithm to show that the highest common factor of 168 and 66 is 6
    (b) Use back substitution to determine integers \(a\) and \(b\) such that
$$168 a + 66 b = 6$$ (c) Explain why there are no integer solutions to the equation $$168 x + 66 y = 10$$ (d) Solve the congruence equation $$11 v \equiv 8 ( \bmod 28 )$$
Edexcel FP2 2024 June Q3
11 marks Standard +0.8
  1. In this question you must show all stages of your working. Solutions relying on calculator technology are not acceptable.
    1. Use the Euclidean Algorithm to determine the highest common factor \(h\) of 234 and 96
    2. Hence determine integers \(a\) and \(b\) such that
    $$234 a + 96 b = h$$
  2. Solve the congruence equation $$96 x \equiv 36 ( \bmod 234 )$$