НОД и коэффициенты Безу
Расширенный алгоритм Евклида находит d = НОД(a, b) и целые x, y с a x + b y = d. Раздел: теория чисел.
Обычный НОД без коэффициентов. Обратный по модулю — частный случай d = 1 и ответ по модулю m. Взаимная простота — только признак d = 1.
Тест: 3·2 + 5·(−1) = 1. Второй тест: НОД(240, 46) = 2. Пара (0, 0) запрещена.
ax + by = НОД(a, b)
a x + b y = НОД(a, b)
Те же деления, что в Евклиде, но запоминают коэффициенты. Подстановка в шагах показывает равенство с найденными x, y. Знаки a и b учитываются.
Как пользоваться
Введите два целых. Проверка: умножьте и сложите. Должен получиться выданный НОД. Совпадение с НОД той же пары обязательно.
Примеры
Безу для 1. 3 и 5 → 2 и −1.
НОД = 2. 240 и 46.
Нули. Ошибка.
Ещё пары
a = 0, b = 5: НОД = 5, x = 0, y = 1, потому что 0·x + 5·1 = 5. Не ошибка «a = 0».
12 и 18: НОД = 6. Одна пара: 12·(−1) + 18·1 = 6. Проверка обязательна: не все пары «маленьких» коэффициентов страница обязана выбрать, но равенство должно держаться.
Если d не делит c, уравнение ax + by = c неразрешимо. Эта страница решает только правую часть = НОД. Общее c = k·d масштабирует x, y в тетради.
Связь с неполным частным: шаги Евклида — те же деления с остатком. Остаток как отдельный ответ — арифметика.
Для обратного 3x ≡ 1 (mod 11) расширенный Евклид на 3 и 11 даёт 3·4 + 11·(−1) = 1, x ≡ 4. Дублирует обратный, но здесь виден и коэффициент при 11.
Отрицательные: a = −3, b = 5. НОД всё ещё 1, знаки x, y подстроятся. Проверьте подстановкой, не знаком «на глаз».
Не путайте с линейным уравнением ax + b = c в действительных: там одно неизвестное и деление, здесь два неизвестных в целых и бесконечно много решений.
Два сравнения используют обратный и Безу внутри. Если задача уже в виде остатков, откройте КТО.
Пара взаимно простых всегда даёт d = 1 и какие-то x, y. Это сильнее, чем ответ «1» на странице взаимной простоты: вы ещё видите комбинацию.
Большие числа: алгоритм быстрый, как Евклид. Не перебирайте x циклом.
Проверка альтернативной парой: если (x, y) работает, (x + b/d, y − a/d) тоже. Калькулятор одну не заменяет другой при повторном нажатии — одна и та же.
Итог: три числа g, x, y. Обычный НОД — без x, y. Обратный — g = 1 и модуль. Нули вместе нельзя.
Ещё: 17 и 13. Оба простые, НОД = 1. 17·(−3) + 13·4 = −51 + 52 = 1. Пара (−3, 4) или другая из семейства. Калькулятор покажет одну, проверка сложением обязательна.
99 и 78. Евклид: 99 = 1·78+21, 78 = 3·21+15, 21 = 1·15+6, 15 = 2·6+3, 6 = 2·3. НОД = 3. Без обратного хода в тетради легко ошибить знаки; страница считает знаки сама.
Уравнение 6x + 9y = 3 разрешимо: делим на 3, это 2x + 3y = 1. Сначала НОД(6,9)=3, 3 делит 3. Масштаб x, y после Безу для (6,9) или для сокращённой пары — два пути.
Не вызывайте НОК вместо Безу. НОК(3,5)=15 ничего не говорит про 2 и −1.
Если a = b, НОД = |a|, одна из простых пар: x = 1, y = 0 или наоборот со знаками. 7·1 + 7·0 = 7.
Школьные формулировки
«Представьте НОД как комбинацию 240 и 46» — эта страница. «Найдите только НОД» — достаточно обычного НОД, коэффициенты не требуют.
«Подберите x, y для 7x + 11y = 1» — Безу при взаимной простоте. Калькулятор даст одну пару; остальные выпишите сдвигом в тетради, если просят общее решение.
Не решайте 7x + 11 = 1 как линейное с одним x: там y нет, деление в действительных.
Проверка на 99 и 78: НОД должен быть 3, и 99x + 78y = 3. Разделите равенство на 3: 33x + 26y = 1. Тогда пара Безу для (33, 26) связана масштабом. Если подстановка даёт 6 вместо 3, вы взяли НОД(99,78) как 6 — ошибка, 6 не делит? Стоп: 99 и 78 делятся на 3, не на 6. 78/6=13, 99/6 не целое. Значит g=3.
Задача «выразить 1 как комбинацию 8 и 15» — взаимно просты, признак 1. Безу: 8·2 + 15·(−1) = 1. Калькулятор может выдать другую пару той же ценности, например отрицательный коэффициент у 8.
Связка с дробями: сокращение 48/18 на НОД=6 даёт 8/3. Безу для 48 и 18 даёт 6 = 48x+18y, не саму сокращённую дробь. Не подставляйте x, y в числитель.
Ещё якорь: 101 и 13. Оба простые. 101·(−5)+13·39 = −505+507=2? Нет, НОД=1, значит комбинация даст 1, не 2. Если подстановка дала 2, коэффициенты не от этой пары или не от этой страницы.
Типичные ошибки
- Считать только НОД и забыть проверить ax + by.
- Подавать (0, 0).
- Ждать единственную пару x, y.
- Решать ax + by = 1, когда НОД > 1.
- Путать с линейным уравнением в действительных.
Частые вопросы
- Что даёт расширенный алгоритм Евклида?
- НОД(a, b) и целые x, y, для которых a x + b y равно этому НОД. Для 3 и 5: НОД = 1, 3·2 + 5·(−1) = 1.
- Чем отличается обычный НОД?
- Калькулятор НОД выдаёт только делитель, без x и y. Здесь нужны коэффициенты Безу.
- Как получить обратный по модулю?
- Если НОД(a, m) = 1, коэффициент x и есть обратный по модулю m после приведения. Удобнее страница обратного.
- Что с парой (0, 0)?
- Калькулятор отказывается: НОД(0, 0) не определяют.
- Единственны ли x и y?
- Нет. Если одна пара найдена, другие отличаются сдвигом на b/g и −a/g. Калькулятор даёт одну пару.
- Нужна ли китайская теорема?
- Система двух сравнений — КТО. Безу — одно линейное уравнение в целых.