Obliczanie NWD z silnią i zmiennymi

[Szymon1993]

Tym razem mam problem z takimi zadaniami:

Wyznaczyć \(\displaystyle{ NWD(n! + 1, (n + 1)! + 1)}\)

Rozwiązywanie tego zadania próbuję zacząć tak jak bym liczył NWD stałych liczb algorytmem Euklidesa. Jednak po napisaniu:\(\displaystyle{ n! \cdot (n + 1) + 1 = (n + 1) \cdot (n! + 1) + (-n)}\) nie wiem co robić dalej. W ogóle nie wiem czy można to tak zapisać ponieważ reszta jest ujemna.

Jakie wartości może przyjmować liczba \(\displaystyle{ NWD(n, n + 7)}\)

NWD maksymalnie może być równe \(\displaystyle{ n}\). Wykonuję więc dzielenie: \(\displaystyle{ \frac{n + 7}{n} = 1 + \frac{7}{n}}\). NWD musi być liczbą całkowitą więc z tego wynika, że \(\displaystyle{ n}\) musi dzielić \(\displaystyle{ 7}\). Czyli \(\displaystyle{ n = 1}\) lub \(\displaystyle{ n = 7}\). Czy takie rozumowanie jest poprawne?

Liczby naturalne \(\displaystyle{ a}\) i \(\displaystyle{ b}\) są względnie pierwsze. Wiadomo, że liczby \(\displaystyle{ m = 4a + 7b}\) i \(\displaystyle{ n = 5a + 3b}\) nie są względnie pierwsze. Znajdź największy wspólny dzielnik liczb \(\displaystyle{ m}\) i \(\displaystyle{ n}\).

Tutaj jedynie potrafię zapisać warunki:

\(\displaystyle{ NWD(a, b) = 1}\)
\(\displaystyle{ NWD(m, n) \neq 1}\)
\(\displaystyle{ NWD(m, n) = ?}\)
Nie mam pomysłu co robić dalej.

Proszę o pomoc w rozwiązaniu tych zadań.

[bakala12]

Niech \(\displaystyle{ d=NWD\left( n!+1,\left( n+1\right)!+1 \right)}\)
Skoro \(\displaystyle{ d}\) dzieli obie liczby to dzieli też liczbę równą:
\(\displaystyle{ \left( n+1\right)!+1-\left( n+1\right)\left( n!+1\right) =-n}\)
Zatem \(\displaystyle{ d|n \Rightarrow d|n!}\) oraz \(\displaystyle{ d|n!+1}\), a więc \(\displaystyle{ d=1}\).
To drugie właściwie dobrze.
Trzecie. Niech \(\displaystyle{ d=NWD\left( m,n\right)}\). Mamy:
\(\displaystyle{ d|4\left( 5a+3b\right) -5\left(4a+7b \right) \Rightarrow d|-23b \Rightarrow d|23b}\)
\(\displaystyle{ d|7\left( 5a+3b\right)-3\left( 4a+7b\right) \Rightarrow d|23a}\)
Stąd skoro \(\displaystyle{ NWD\left( a,b\right)=1}\) to \(\displaystyle{ d=23}\).

[Szymon1993]

Jeśli chodzi o trzecie to czy mógłbyś mi wyjaśnić skąd się wzięły współczynniki \(\displaystyle{ 4}\), \(\displaystyle{ 5}\), \(\displaystyle{ 7}\) i \(\displaystyle{ 3}\) przed sumami \(\displaystyle{ 5a + 3b}\) oraz \(\displaystyle{ 4a + 7b}\)?

[bakala12]

Tak dobrałem żeby raz pozbyć się \(\displaystyle{ a}\) a drugi raz \(\displaystyle{ b}\)

[Szymon1993]

Aha, dziękuję.