Расширенный алгоритм Евклида с использованием усеченных остатков (или сокращенных остатков) позволяет находить не только наибольший общий делитель (НОД) двух чисел, но и коэффициенты Беккера \(x\) и \(y\), такие что \( ax + by = \text{НОД}(a, b) \). В этой модификации алгоритма осуществляется использование комбинации целочисленного деления и остатков для упрощения вычислений.
### Алгоритм
1. **Инициализация**:
Начинаем с двух чисел \(a\) и \(b\) и задаем начальные значения для коэффициентов, которые будут хранить результаты (такие как \(x_0, y_0\) и текущие \(x_1, y_1\)). Например:
- \(x_0 = 1, y_0 = 0\) (коэффициенты для \(a\)).
- \(x_1 = 0, y_1 = 1\) (коэффициенты для \(b\)).
2. **Основной цикл**:
Пока \(b \neq 0\):
- Вычисляем частное \(q = \lfloor a / b \rfloor\) и остаток \(r = a \mod b\).
- Обновляем \(a\) и \(b\) в соответствии с:
- \(a \leftarrow b\)
- \(b \leftarrow r\)
- Обновляем коэффициенты для \(x\) и \(y\):
- \(x_{\text{temp}} = x_0 - q \cdot x_1\)
- \(y_{\text{temp}} = y_0 - q \cdot y_1\)
- \(x_0 \leftarrow x_1\)
- \(y_0 \leftarrow y_1\)
- \(x_1 \leftarrow x_{\text{temp}}\)
- \(y_1 \leftarrow y_{\text{temp}}\)
3. **Заключение**:
Когда \(b = 0\), НОД равен \(a\) (т.е. текущему значению \(a\)), и коэффициенты \(x_0\) и \(y_0\) — это решения уравнения \(ax + by = \text{НОД}(a, b)\).
### Пример реализации на Python
```python
def extended_euclidean(a, b):
x0, x1 = 1, 0 # Начальные коэффициенты для a
y0, y1 = 0, 1 # Начальные коэффициенты для b
while b != 0:
q, r = divmod(a, b) # Частное и остаток
a, b = b, r # Обновляем a и b
x0, x1 = x1, x0 - q * x1 # Обновляем коэффициенты x
y0, y1 = y1, y0 - q * y1 # Обновляем коэффициенты y
return a, x0, y0 # Возвращаем НОД и коэффициенты
# Пример использования
a, b = 252, 105
gcd, x, y = extended_euclidean(a, b)
print(f"НОД({a}, {b}) = {gcd} (x = {x}, y = {y})")
```
### Заключение
using *усеченные остатки* в расширенном алгоритме Евклида помогает более эффективно находить НОД и соответствующие коэффициенты. Это полезный алгоритм в теории чисел и криптографии, а также в решении уравнений вида \(ax + by = c\).