/Konkursy

Zadanie nr 1122197

Dodaj do ulubionych
Dodaj do rozwiązanych

Uzasadnij, że dla dowolnych liczb naturalnych b > a zachodzi równość N W D (a,b) = N W D (a,b− a) .

Rozwiązanie

Wystarczy pokazać, że liczba p dzieli lewą stronę wtedy i tylko wtedy, gdy dzieli prawą stronę.

Jeżeli p|N W D (a,b) to p dzieli i a i b i mamy

p|a∧ p |b − a ⇒ p |N W D (a,b− a).

Na odwrót, jeżeli p dzieli a i b − a to mamy

p|a ∧ p|(a+ (b− a)) ⇒ p|a∧ p |b ⇒ p|N W D (a,b).
Wersja PDF