 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-oxford/2021/prelims/mathematics-iv-resit/7/b/i/solution

6573064536 = 2 \cdot 306 + 45, = 6 \cdot 45 + 36, = 1 \cdot 36 + 9, = 4 \cdot 9 + 0.

Each step preserves the greatest common divisor by part (a). The final nonzero remainder is

9

, so

g cd (306, 657) = 9.

 New to topics? Read the docs here!