Use the Euclidean algorithm to find the greatest common divisor of 74 and 383.

Hence find integers s and t such that 74s + 383t = 1.

383 = 5 × 74 + 13        M1
74 = 5 × 13 + 9       A1
13 = 1 × 9 + 4       (A1)
9 = 2 × 4 + 1
4 = 4 × 1 + 0
⇒ gcd (74, 383) = 1       A1

[4 marks]

EITHER
1 = 9 − 2 × 4       (M1)
= 9 − 2(13 − 1 × 9) = 3 × 9 − 2 × 13        (A1)
= 3(74 − 5 × 13) − 2 × 13 = 3 × 74 − 17 × 13      (A1)
= 3 × 74 − 17 (383 − 5 × 74) = 88 × 74 − 17 × 383

OR
13 = 383 − 5 × 74      (M1)
9 = 74 − 5 × 13
  = 74 − 5(383 − 5 × 74)
  = 26 × 74 − 5 × 383      (A1)
4 = 13 − 9
  = (383 − 5 × 74) − (26 × 74 − 5 × 383)
  = 6 × 383 − 31 × 74      (A1)
1 = 9 − 2 × 4
  = (26 × 74 − 5 × 383) − 2(6 × 383 − 31 × 74)
  = 88 × 74 − 17 × 383

THEN
⇒ s = 88 and t =  − 17      A1A1

[5 marks]