Наибольший общий делитель двух линейных функций

[Noct]

Нужно найти $\gcd(2k-1,9k+4)$, для всех целых $k$
Запускаю алгоритм Евклида

$$9k+4 = 4 \cdot (2k-1) + (k+8) \qquad k \geqslant 10$$

$$2k-1 = 1 \cdot (k+8) + (k-9) \qquad \text{при } k=9 \text{ алгоритм заканчивается и} \gcd= 17$$

$$k+8 = 1 \cdot (k-9) + 17 \qquad \qquad k \geqslant 27 $$

А вот дальше не совсем понятно как действовать,
например

$$k-9 = 1 \cdot 17 + (k-26) \qquad \qquad 27 \leqslant k \leqslant 42 $$

и если что делать если $k>42$, мне не понятно. Сделать

$$k-9 = 2 \cdot 17 + (k-43) \qquad \qquad 43 \leqslant k \leqslant 43+16 $$

и возникает точно, такая же проблема.
В принципе, отсюда можно сделать вывод, что при $k=17t + 9$, $t = 0,1,\dots$
$\gcd(2k-1,9k+4) = 17$ и чисто численно, вроде-бы для остальных $\gcd(2k-1,9k+4) = 1$
но как это строго показать?

[mihaild]

Алгоритм Евклида основан на том, что $gcd(a, b) = gcd(a + kb, b)$. Так как общий делитель вполне определяется и для отрицательных чисел - попробуйте такими преобразованиями (вычитанием одного аргумента из другого) придти к паре, один из элементов которой не содержит $k$, и проанализировать уже ее.

Noct в сообщении #1229092 писал(а):

Наибольший общий делитель двух линейных функций

Так самих функций, или значений при каждом $k$? Это разные вещи.

[Someone]

Вы не так рассуждаете. Используйте алгоритм Евклида, чтобы исключить $k$ и получить число, не зависящее от $k$. Тогда $\gcd(2k-1,9k+4)$ будет одним из делителей этого числа. И надо только разобраться, при каких $k$ что получится.

[Noct]

$$\gcd(9k+1, 2k-1) = \gcd(2k-1, k+8) = \gcd(k+8, 17)$$

Далее, если $k = -8 \mod 17$, то есть $k = 17t + 9$, $t = 0,1 \dots$
то $\gcd(9k+1, 2k-1) = 17$.
Осталось показать что если $k \ne 9 \mod 17$, то $\gcd(k+8, 17) = 1$

[Sonic86]

Noct в сообщении #1229107 писал(а):

Осталось показать что если $k \ne 9 \mod 17$, то $\gcd(k+8, 17) = 1$

Ну сделайте подстановку для $k$, упростите и все.

[Noct]

Да спасибо разобрался, 17 простое и по определению $\gcd(k+8,17) = 1$, если $17|(k+8)$ или в противном случаи $\gcd(k+8,17) = 1$