nwd, dowod

[wiedzma]

Wykaz, ze jesli nwd(a,c)=1 to nwd(a,bc)=nwd(a,b)

[BettyBoo]

Niech \(\displaystyle{ NWD(a,bc)=d,\ NWD(a,b)=s}\). Chcemy udowodnić, że d=s. Ponieważ obie liczby są dodatnie, to wystarczy pokazać dwie podzielności.

Jedna jest oczywista i zachodzi niezależnie od dodatkowego założenia.
\(\displaystyle{ s|a\ \wedge\ s|b\ \Rightarrow \ s|a\ \wedge\ s|bc\ \Rightarrow\ s|d}\)

Dla drugiej skorzystamy z założenia. Oznacza ono, że istnieją x,y całkowite takie, że ax+cy=1.
Wtedy z własności NWD mamy:

\(\displaystyle{ d|a\ \wedge\ d|bc\ \Rightarrow \ d|a\ \wedge\ d|a(bx)+bc(y)\ \Rightarrow\ d|a\ \wedge\ d|b\ \Rightarrow \ d|s}\)

Pozdrawiam.