472. For which number and for which natural $a$ are the fractions reducible:
a) $\frac{a^{4}+a^{3}-a^{2}+a+1}{a^{2}-1}$;
b) $\frac{a^{4}+6 a^{3}+15 a^{2}+18 a+8}{a^{4}+6 a^{3}+13 a^{2}+12 a+3}$?

473 $3^{\circ}$. Let $a$ and $b$ be natural numbers, where $a > b$, and the number $a$ is divided by the number $b$ with a remainder:

$$
a = bq + r \quad (0 < r < b).
$$

Prove that

$$
\text{GCD}(a, b) = \text{GCD}(b, r).
$$
$\triangle$ Let's introduce the notation:

$$
\text { GCD }(a, b)=d_{1}, \quad \text { GCD }(b, r)=d_{2} .
$$

Since the numbers $a$ and $b$ are divisible by $d_{1}$, from the initial equation we get that the remainder $r$ is also divisible by $d_{1}$. Therefore, $d_{1}$ is a common divisor of the numbers $b$ and $r$. But $d_{2}$ is the greatest common divisor of the same numbers; hence, $d_{2} \geqslant d_{1}$.

Since the numbers $b$ and $r$ are divisible by $d_{2}$, from the initial equation $a$ is also divisible by $d_{2}$. Therefore, $d_{2}$ is a common divisor of the numbers $a$ and $b$. But $d_{1}$ is the greatest common divisor of these numbers, so $d_{1} \geqslant d_{2}$.

From the inequalities $d_{2} \geqslant d_{1}$ and $d_{1} \geqslant d_{2}$, it follows that $d_{1}=d_{2}$.

The statement of problem 473 is the basis for the following method of finding the greatest common divisor of two natural numbers.

474 $4^{\circ}$. Let $a$ and $b$ be natural numbers, $a>b$. Divide $a$ by $b$ with a remainder; divide the number $b$ by the obtained remainder $r_{1}$ with a remainder; divide the number $r_{1}$ by the new remainder $r_{2}$ with a remainder; divide $r_{2}$ by the new remainder $r_{3}$ with a remainder, and so on. Prove that then the greatest common divisor of the numbers $a$ and $b$ is equal to the last non-zero remainder.

$\triangle$ Write down the equations corresponding to the conditions of the problem:

$$
\begin{aligned}
& a=b q_{1}+r_{1} \quad\left(r_{1}<b\right) \\
& b=r_{1} q_{2}+r_{2} \quad\left(r_{2}<r_{1}\right) \\
& r_{1}=r_{2} q_{3}+r_{3} \quad\left(r_{3}<r_{2}\right) \\
& \cdots \cdots \cdots \cdots \cdots \cdots \cdots \cdots \\
& r_{n-2}=r_{n-1} q_{n}+r_{n} \quad\left(r_{n}<r_{n-1}\right) \\
& r_{n-1}=r_{n} q_{n+1} .
\end{aligned}
$$

Why do we eventually come to a remainder equal to zero? Because the remainders form a decreasing sequence of non-negative integers

$$
r_{1}, r_{2}, r_{3}, \ldots, r_{n}
$$

and therefore, this process must end.

Now we get, using the statement of problem 473:

$$
\text { GCD }(a, b)=\text { GCD }\left(b, r_{1}\right)=\text { GCD }\left(r_{1}, r_{2}\right)=\ldots=\text { GCD }\left(r_{n-1}, r_{n}\right)=r_{n} .
$$

(The equality GCD $\left(r_{n-1}, r_{n}\right)=r_{n}$ is explained by the fact that, as seen from the last initial equation, the number $r_{n-1}$ is divisible by the number $r_{n}$.)

The proven statement gives a method for finding the greatest common divisor of two numbers. It is called the Euclidean algorithm, which Euclid described in his work "Elements." The Euclidean algorithm is used in cases where natural numbers are quite large; if they are small, it is better to use the usual method - by factoring the numbers into prime factors.

Using the Euclidean algorithm, let's find, for example, the greatest common divisor of the numbers 9240 and 8568. We get:

$$
\begin{aligned}
& 9240=8568 \cdot 1+672 \\
& 8568=672 \cdot 12+504 \\
& 672=504 \cdot 1+168 \\
& 504=168 \cdot 3
\end{aligned}
$$

Since the last non-zero remainder here is 168, the greatest common divisor of the numbers 9240 and 8568 is 168.