Euclidean algorithm - HCF only

Questions requiring use of the Euclidean algorithm to find HCF/GCD only, without back-substitution to express as linear combination.

2 questions · Moderate -0.7

Sort by: Default | Easiest first | Hardest first
Edexcel FP2 AS 2018 June Q1
5 marks Moderate -0.8
  1. (i) Using a suitable algorithm and without performing any division, determine whether 23738 is divisible by 11
    (ii) Use the Euclidean algorithm to find the highest common factor of 2322 and 654
Edexcel FP2 Specimen Q1
7 marks Moderate -0.5
  1. (i) Use the Euclidean algorithm to find the highest common factor of 602 and 161.
Show each step of the algorithm.
(ii) The digits which can be used in a security code are the numbers \(1,2,3,4,5,6,7,8\) and 9. Originally the code used consisted of two distinct odd digits, followed by three distinct even digits. To enable more codes to be generated, a new system is devised. This uses two distinct even digits, followed by any three other distinct digits. No digits are repeated. Find the increase in the number of possible codes which results from using the new system.