Znaleźć największy wspólny dzielnik w zależności od k

[Poszukujaca]

Dla liczb całkowitych \(\displaystyle{ 2k-1, 9k+4}\) znaleźć największy wspólny dzielnik w zależności od liczby całkowitej \(\displaystyle{ k}\).

Robię tak z algorytmu Euklidesa:
Mogę bez straty ogólności założyć, że \(\displaystyle{ 9k+4 > 2k-1}\).
\(\displaystyle{ 9k+4 = 4(2k-1)+(k+8)}\)
\(\displaystyle{ 2k-1= 2(k+8)-17}\)

Algorytm Euklidesa skończy się przy pierwszej niezerowej reszcie, więc sprawdzam kiedy \(\displaystyle{ 2(k+8) \equiv_{17} 0}\)

Czy dobrze?

[Kaf]

Nie możesz zakładać, że \(\displaystyle{ 9k+4 > 2k-1}\), i nie jest też to szczególnie potrzebne. Jest dobrze (o ile w zależności od otrzymanego \(\displaystyle{ k}\) potrafisz wskazać szukane NWD, ale z rozwiązania wnioskuję, że tak)

[Poszukujaca]

W przypadku kiedy \(\displaystyle{ k \equiv_{17} 9}\), to \(\displaystyle{ NWD left{ 9k+4, 2k-1
ight} = 17 /tex], bo ostatnią niezerową resztą będzie \(\displaystyle{ 17}\).

Ale jak rozpatrzyć pozostałe przypadki?}\)

[Kaf]

Proste: z obliczeń które zrobiłaś wynika, że szukana liczba jest równa \(\displaystyle{ NWD(k+8, 17)}\), a ponieważ \(\displaystyle{ 17}\) jest liczbą pierwszą, to możliwe są tylko 2 wartości.