Heisei 27 National Center Test for University Admissions: Mathematics 2B (Old Curriculum), Question 6

Let M and N be natural numbers such that M > N and their greatest common divisor is 1. For the fraction M/N,
consider the following steps (i) through (iii).
(i) Let Q be the quotient and R the remainder when M is divided by N.
(ii) If R > 0, substitute the value of N into M, then substitute the value of R into N, and return to (i).
(iii) If R = 0, terminate.
Using this sequence of quotients, we can multiply as follows: