# Расширенный алгоритм Евклида (ax + by = НОД(a, b))

Решает тождество Безу a·x + b·y = НОД(a, b) для целых чисел любого знака: выдаёт полную таблицу шагов деления (каждая строка удовлетворяет r = a·s + b·t), НОД и НОК. С необязательной правой частью c превращается в решатель линейных диофантовых уравнений: при НОД | c даёт частное и общее решение x = x₀ + (b/g)t, иначе ясно сообщает об отсутствии целых решений. Классика: 240 × (−9) + 46 × 47 = 2.

> Каноническая страница: https://elysiatools.com/ru/tools/extended-euclidean-algorithm

- **Категория:** Math & Numbers

- **Ключевые слова:** расширенный евклид, тождество безу, коэффициенты безу, нод, диофантово уравнение, линейное диофантово, теория чисел

## Обзор

Онлайн-калькулятор расширенного алгоритма Евклида находит наибольший общий делитель (НОД), наименьшее общее кратное (НОК) и коэффициенты тождества Безу для любых целых чисел. Инструмент также решает линейные диофантовы уравнения вида ax + by = c, предоставляя пошаговую таблицу деления, частное решение и формулу общего решения.

## Входные данные

- **Значение a** (text): First integer; negative values are supported.
- **Значение b** (text): Second integer; negative values are supported.
- **Правая часть c (необязательно, решает ax + by = c)** (text): Optional target: solves ax + by = c when gcd(a, b) divides c.
- **Стиль вывода** (select)

## Когда использовать

- Для нахождения коэффициентов Безу x и y в тождестве ax + by = НОД(a, b).
- Для решения линейных диофантовых уравнений с проверкой делимости c на НОД(a, b).
- Для пошаговой демонстрации вычислений и проверки промежуточных остатков в задачах по теории чисел и криптографии.

## Как это работает

- Введите целые числа a и b (поддерживаются как положительные, так и отрицательные значения).
- При необходимости укажите свободный член c для решения уравнения ax + by = c.
- Выберите формат вывода: только итоговый результат с проверкой или подробная пошаговая таблица деления.
- Получите значения НОД, НОК, коэффициенты Безу, а также частное и общее решения диофантова уравнения.

## Сценарии использования

- Поиск мультипликативного обратного элемента в модульной арифметике и криптографических алгоритмах (например, RSA).
- Решение практических задач дискретной математики на нахождение целочисленных решений линейных уравнений.
- Самопроверка учебных заданий по теории чисел с детальным разбором каждого шага деления с остатком.

## Частые вопросы

### Что такое тождество Безу?

Это представление наибольшего общего делителя двух целых чисел a и b в виде их линейной комбинации: ax + by = НОД(a, b), где x и y — целые числа (коэффициенты Безу).

### Всегда ли существует решение у уравнения ax + by = c?

Целочисленные решения существуют тогда и только тогда, когда свободный член c делится на НОД(a, b) без остатка.

### Поддерживаются ли отрицательные числа?

Да, алгоритм корректно обрабатывает отрицательные значения для a, b и c, сохраняя математическую строгость знаков.

### Как вычисляется НОК чисел?

Наименьшее общее кратное вычисляется через произведение модулей чисел, деленное на их НОД: НОК(a, b) = |a · b| / НОД(a, b).

### Что отображается в режиме пошагового вывода?

Выводится полная таблица деления с остатками, неполными частными и представлением каждого остатка в виде r = a·s + b·t.

## Связанные инструменты

- [Упрощатель булевых выражений (карта Карно)](https://elysiatools.com/ru/tools/boolean-algebra-simplifier): Упрощает булевы функции до минимальной ДНФ: введите выражение (A–D, + ИЛИ, · И, ' НЕ, ≤ 4 переменных) или список минтермов Σm; алгоритм Куайна-Мак-Класки находит простые импликанты, берёт существенные и достраивает точное минимальное покрытие; выводятся минимальная ДНФ, карта Карно в коде Грея (2–4 переменных), каноническая форма Σm и проверка на всех наборах. Классика: AB + A'B → B; Σm(0,1,2,4,5,6) (3 переменные) → B' + C'.
- [Конвертер разведения (1:X ↔ 1/X ↔ %)](https://elysiatools.com/ru/tools/dilution-ratio-converter): Переводит между лабораторными формами записи разведения: пропорцией 1:X, дробью 1/X и процентами, а также рассчитывает фактор разведения и части растворённого вещества/разбавителя. Поддерживает оба соглашения 1:X (X — всего частей или 1 часть вещества + X частей разбавителя); при заданном конечном объёме выводит объёмы для смешивания. Классика: 1:5 = 1/5 = 20 %; на 100 мл — 20 мл концентрата + 80 мл разбавителя.
- [Калькулятор обратного по модулю (расширенный Евклид)](https://elysiatools.com/ru/tools/modular-inverse-calculator): Вычисляет a⁻¹ mod m расширенным алгоритмом Евклида: выдаёт коэффициенты Безу a·x + m·y = gcd(a, m), полную таблицу прямых коэффициентов (каждая строка удовлетворяет r = a·s + m·t) и проверку a × a⁻¹ ≡ 1 (mod m). Принимает числа масштаба RSA (до 10⁵¹²); при gcd(a, m) ≠ 1 ясно сообщает, что обратного элемента нет. Классика: в RSA 17⁻¹ mod 3120 = 2753.
- [Калькулятор модулярной арифметики (сложение / вычитание / умножение / обратное / степень)](https://elysiatools.com/ru/tools/modulo-arithmetic-converter): Выполняет сложение, вычитание, умножение, обращение и быстрое возведение в степень по модулю m на точной BigInt-арифметике (до 10¹⁸). Базовые операции показывают пошаговое приведение и дают канонического представителя из \[0, m−1\]; обратный элемент ищется расширенным алгоритмом Евклида, а при gcd(a, m) ≠ 1 сообщается об отсутствии; быстрое возведение показывает таблицу «возводи-и-умножай» по битам показателя. Примеры: 17⁵ mod 13 = 10; 5⁻¹ mod 18 = 11.
- [Генератор таблиц истинности](https://elysiatools.com/ru/tools/truth-table-generator): Строит полную таблицу истинности булева выражения (до 6 переменных, 64 строки): поддерживаются + ИЛИ, ^ XOR, ·/*/& или умножение И, !/~/' НЕ, скобки; переменные перечислены по алфавиту, каждая строка показывает набор и значение F, а также канонические формы Σm (минтермы) и ΠM (макстермы). Классика: AB + A'C имеет Σm(1,3,6,7); A ^ B ^ C — функция нечётности Σm(1,2,4,7).
- [Конвертер угловой скорости (rad/s / rpm / deg/s / Hz)](https://elysiatools.com/ru/tools/angular-velocity-converter): Пересчёт угловой скорости: рад/с (база СИ) ↔ об/мин (1=2π/60 рад/с) ↔ град/с (1=π/180 рад/с) ↔ Гц (1 оборот/с=2π рад/с). Гц здесь = оборот в секунду. Пересчёт через рад/с с четырьмя эквивалентами. Эталон: винил 33⅓ об/мин≈3,49 рад/с, холостой ход ~800 об/мин≈83,8 рад/с.
- [Калькулятор размера воздуховода (расход и скорость)](https://elysiatools.com/ru/tools/duct-size-calculator): Размер воздуховода по расходу Q и расчётной скорости v: площадь A=Q/v. Круглый: диаметр D=√(4A/π). Прямоугольный с соотношением r=a/b: b=√(A/r), a=r·b, эквивалентный диаметр ASHRAE D_экв=1,30·(a·b)^0,625/(a+b)^0,25. Расход в м³/с/м³/ч/CFM; результат в мм и дюймах.
- [Калькулятор предела выносливости (Гудмен/Гербер/Содерберг)](https://elysiatools.com/ru/tools/fatigue-limit-calculator): Коэффициент запаса по выносливости с поправкой на среднее напряжение. По σ_a, σ_m и σ_uts, σ_-1, σ_y — три классических критерия: модифицированный Гудмен (линейный, консервативный), Гербер (параболический, ближе к данным для вязких материалов), Содерберг (через σ_y, самый консервативный). Управляющий — минимум; показано, лежит ли точка внутри линии Гудмена.

## Примеры

- [Примеры Обработки Изображений Web Python](https://elysiatools.com/ru/samples/web-image-processing-python): Примеры обработки изображений Web Python используя PIL/Pillow включая чтение, сохранение, изменение размера и преобразование формата
- [Примеры Обработки Изображений Android Java](https://elysiatools.com/ru/samples/android-image-processing-java): Примеры обработки изображений Android Java включая чтение/сохранение, масштабирование и преобразование формата
- [Примеры Обработки Изображений Android Kotlin](https://elysiatools.com/ru/samples/android-image-processing-kotlin): Примеры обработки изображений Android Kotlin включая чтение/сохранение, масштабирование и преобразование формата
- [Примеры Обработки Изображений Web Rust](https://elysiatools.com/ru/samples/web-image-processing-rust): Примеры обработки изображений Web Rust включая чтение/запись, масштабирование и преобразование форматов