Старогодняя задача на ноды и ноки Назовем старогодней четверку чисел (a, b, c, d), если для нее существует бесконечное количество m, таких что gcd(am + b, cm + d) = 2019. Найдите всевозможные значения |ad - bc| для старогодних четверок.

Предыдущий
вопрос Следующий
вопрос

Чтобы решить задачу, начнем с определения условия, при котором существует бесконечное количество целых ( m ), для которых выполняется равенство:

[
\gcd(am + b, cm + d) = 2019.
]

По определению, для того чтобы ( \gcd(am + b, cm + d) = k ) для бесконечно многих ( m ) необходимо, чтобы ( a ) и ( c ) были кратны ( k ).

Определим необходимое условие:
Обозначим ( A = a/k ), ( B = b/k ), ( C = c/k ), ( D = d/k ). Тогда требование (\gcd(am + b, cm + d) = k) можно переписать в следующем виде:

[
\gcd(k(Am + B), k(Cm + D)) = k \cdot \gcd(Am + B, Cm + D).
]

Таким образом, чтобы ( \gcd(am + b, cm + d) = 2019 ), необходимо, чтобы ( a ) и ( c ) были кратны ( 2019 ).

Перепишем уравнение:
Пусть ( a = 2019x ) и ( c = 2019y ), где ( x ) и ( y ) — целые числа. Тогда:

[
\gcd(2019xm + b, 2019ym + d) = 2019 \cdot \gcd(xm + b/2019, ym + d/2019).
]

Нам нужно, чтобы ( \gcd(xm + B, ym + D) ) принимало значение 1 для бесконечно многих ( m ).

Условие для бесконечного количества решений:
Это эквивалентно тому, что ( x ) и ( y ) должны быть взаимно простыми (то есть (\gcd(x, y) = 1)).

Рассмотрим выражение (|ad - bc|):
Подставляя ( a = 2019x ) и ( c = 2019y ), получаем:

[
|ad - bc| = |(2019x)d - (2019y)b| = 2019 |xd - yb|.
]

Для того чтобы (|xd - yb|) могло принимать любые значения, ( d ) и ( b ) могут быть выбраны произвольно. Если рассмотреть ( d = 0 ) и ( b = 1 ), то получится:

[
|xd| = |x| \text{ и } |yd| = |y|.
]

Таким образом, (|ad - bc| = 2019 \cdot |xd - yb| = 2019k), где ( k ) — целое число.

Условия для возможных значений ( |ad - bc| ):
В итоге, возможные значения для (|ad - bc|) равны ( 2019k ) для любого целого ( k ). Поскольку ( |xd - yb| ) может принимать любое значение, которому соответствует любое целое ( k ).

Ответ: Все целые кратные ( 2019 ), то есть ( |ad - bc| = 2019k ) для любых целых ( k ).