Наибольший общий делитель

Примем b > a и заметим, что

НОД(a + b; b) = НОД(a + b; a) = НОД(a; b) = НОД(a; b - a) = 1

Из соотношения Безу следует, что

∃ u, v: (u ∈ Z, v ∈ Z), ua + vb = 1

(положительные значения этой линейной комбинации ограничивают НОД сверху, а её минимальное положительное значение - и есть сам НОД).

Также заметим, что

2023(2023b + a) - (2023a + b) = (2023² - 1)b
2023(2023a + b) - (2023b + a) = (2023² - 1)a

(2023² - 1)(ua + vb) = 2023² - 1 = 2024 * 2022
(2023² - 1)(ua + vb) = (2023u(2023a + b) - u(2023b + a)) + (2023v(2023b + a) - v(2023a + b)) =
= (2023u - v)(2023a + b) + (2023v - u)(2023b + a)

Таким образом, существуют коэффициенты линейной комбинации (2023a + b) и (2023b + a), при которых её значение равно 2024 * 2022, значит, ни при каких a и b НОД(2023a + b; 2023b + a) не может превышать этого значения.
Существуют ли другие коэффициенты, при которых значение линейной комбинации меньше?
Думаю, можно доказать математически, что таких коэффициентов не существует. Но мне показалось проще решить этот вопрос перебором. При следующих (взаимно простых) a и b мы достигаем максимального НОД:

a = 4120177; b = 836237177
2023a + b = 9171355248
2023b + a = 1691711929248
НОД(2023a + b; 2023b + a) = 4092528 = 2024 * 2022

Принцип перебора следующий:

1. В качестве a выбираем простое число, превышающее 2024 * 2022.
2. В качестве b выбираем 2022 * p - a, где p - простое число, значительно превышающее 2024 (и разумеется, отличное от a; оно может быть значительно меньше a для уменьшения вычислительной нагрузки). В моём примере p = 415607. Именно число p и подлежит перебору. Я наугад взял первые 400 простых чисел после 412000, и в этом диапазоне нашлось одно подходящее.
3. Рассчитываем величины, получаем НОД, смотрим, совпадает ли он с нашим идеалом (2024 * 2022). Если нет, то пробуем следующее p.

Расчёты можно сделать формулами в Excel, сразу подавая на вход диапазон простых множителей p, а эти множители генерировать любым онлайн-генератором простых чисел, которых в сети полно (я использовал onlinemathtools). Затем при помощи функции MAX по диапазону ячеек быстро узнаём, получился ли нужный НОД. Если нет, то скармливаем Экселю следующий диапазон.