Implikacja z NWD

[Hatcher]

Zad.
Czy prawdziwa jest implikacja:
\(\displaystyle{ [ NWD(a,b)=d \wedge ar+bs=d ] \Rightarrow NWD(r,s)=1}\) ?

Bardzo proszę o pomoc.

[BettyBoo]

Jeśli \(\displaystyle{ a,b,r,s\in \mathbb{Z}}\), to

\(\displaystyle{ NWD(a,b)=d \wedge ar+bs=d \Rightarrow \frac{a}{d}r+\frac{b}{d}s=1\ \wedge\ \frac{a}{d},\ \frac{b}{d}\in\mathbb{Z}\ \Rightarrow \ NWD(r,s)|1\ \Rightarrow \ NWD(r,s)=1}\)

Pozdrawiam.

[Hatcher]

\(\displaystyle{ ... \frac{a}{d}r+\frac{b}{d}s=1\ \wedge\ \frac{a}{d},\ \frac{b}{d}\in\mathbb{Z}\ \Rightarrow \ NWD(r,s)|1\ \Rightarrow \ NWD(r,s)=1}\)

czyli \(\displaystyle{ \exists k \in \mathbb{Z} : a=d \cdot k}\), \(\displaystyle{ \exists l \in \mathbb{Z} : b=d \cdot l}\)

\(\displaystyle{ ar+bs=d \iff d \cdot k \cdot r + d \cdot l \cdot s=d \iff k \cdot r+ l \cdot s=1}\)
czyli to oznacza, że \(\displaystyle{ NWD(r,s)=1}\), \(\displaystyle{ NWD(k,l)=1}\)
Dobrze rozumiem?

[BettyBoo]

Dobrze, chociaż tak dokładniej, to z tw o kombinacji liniowej wynika, że równość kr+ls=1 oznacza to, że NWD(r,s) dzieli 1, a z definicji NWD wynika wobec tego, że NWD(r,s)=1.

Pozdrawiam.