Treść:
Rozwiązanie:Udowodnij, że \(\displaystyle{ \gcd(a,b) = \gcd(a,b-a)}\).
Czy jest ono poprawne?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}\)
Pozdrawiam.