Równość NWD-ów

Podzielność. Reszty z dzielenia. Kongruencje. Systemy pozycyjne. Równania diofantyczne. Liczby pierwsze i względnie pierwsze. NWW i NWD.
jenek
Użytkownik
Użytkownik
Posty: 26
Rejestracja: 16 paź 2013, o 11:09
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 6 razy
Pomógł: 1 raz

Równość NWD-ów

Post autor: jenek »

Dobry wieczór, mam pytanie odnośnie rozwiązania zamieszczonego poniżej:

Treść:
Udowodnij, że \(\displaystyle{ \gcd(a,b) = \gcd(a,b-a)}\).
Rozwiązanie:
Przyjmuję, że \(\displaystyle{ d = \gcd(a,b)}\). Wtedy \(\displaystyle{ d \vert a}\) i \(\displaystyle{ d \vert b}\), czyli \(\displaystyle{ d \vert b-a}\). Stąd \(\displaystyle{ d}\) jest wspólnym dzielnikiem \(\displaystyle{ a}\) i \(\displaystyle{ b-a}\), co daje \(\displaystyle{ d \le \gcd(a,b-a)}\).

Podobnie przyjmuję, że \(\displaystyle{ c = \gcd(a,b-a)}\). Wtedy \(\displaystyle{ c \vert a}\) i \(\displaystyle{ c \vert b-a}\), czyli \(\displaystyle{ c \vert b}\). Stąd \(\displaystyle{ c}\) jest wspólnym dzielnikiem \(\displaystyle{ a}\) i \(\displaystyle{ b}\), co daje \(\displaystyle{ \gcd(a,b-a) \le d}\).

Ostatecznie \(\displaystyle{ d = \gcd(a,b) = \gcd(a,b-a) = c}\)
Czy jest ono poprawne?

Pozdrawiam.
Zahion
Moderator
Moderator
Posty: 2095
Rejestracja: 9 gru 2012, o 19:46
Płeć: Mężczyzna
Lokalizacja: Warszawa, mazowieckie
Podziękował: 139 razy
Pomógł: 504 razy

Równość NWD-ów

Post autor: Zahion »

Si.
ODPOWIEDZ