Applying Euclidean Algorithm to find nth value

Question

Stuck on two questions which I am unsure of how to approach.

Use Euclidean Algorithm to find the $n$ value:

1. $\text{gcd}(a,b)$ expressed as $\text{gcd}(a,b) = \text{gcd}(a_{1},b_{1}) = \text{gcd}(a_{2},b2_{2}) = ... = \text{gcd}(a_{n},0)$. Find the value of n for $\text{gcd}(999,9)$
2. $\text{gcd}(a,b)$ expressed as $\text{gcd}(a,b) = \text{gcd}(a_{1},b_{1}) = \text{gcd}(a_{2},b2_{2}) = ... = \text{gcd}(a_{n},0)$. Find the value of n for $\text{gcd}(27,72)$

I understand how to compute the $\text{gcd}$ by applying Euclidean Algorithm. But I am taken aback when I saw this question which I have no idea how to start. I will appreciate if someone can guide me.

Thanks in advance.

Answer 1

There are $111$ pairs where $GCD(n,9)=9, 1\le n \le 999$.

There are $3$ pairs where $GCD(n,72)=9, 1\le n \le 27$.