NWD

[cherryvis3]

Jeśli NWD(j,m)=1 i NWD(k,m)=1 to NWD(kj,m)=1 dlaczego;>?

[radagast]

\(NWD(j,m)=1\) to \(j, m\) nie mają wspólnych dzielników poza 1

\(NWD(k,m)=1\) to \(k, m\) nie mają wspólnych dzielników poza 1

No to skąd miałby się wziąć wspólny dzielnik \(kj\) i \(m\) ?
Zbiór dzielników \(kj\) to suma zbioru dzielników \(k\) i zbioru dzielników \(j\)

[irena]

Liczba m jest względnie pierwsza z liczbą k. Jest też względnie pierwsza z liczbą j. Z żadną z tych liczb nie ma wspólnego dzielnika. Nie istnieje więc liczba całkowitą, która byłaby wspólnym dzielnikiem liczby m i iloczynu kj.

Można to pokazać tak:
Liczby a i b są względnie pierwsze, czyli NWD(a, b)=1 wtedy i tylko wtedy, gdy istnieją takie całkowite liczby x, y, że ax+by=1.

Wiemy, że istnieją takie liczby całkowite a, b, c, d, że
\(\{ak+bm=1\\cj+dm=1\)

\(\{ak=1-bm\\cj=1-dm\)

Po pomnożeniu stronami mamy:
\(ackj=1-(b+d)m+bdm^2\\ackj+(b+d-bdm)\cdot m=1\\ac=x\in C\ \wedge\ (b+d-bdm)=y\in C\)

Oznacza to, że istnieją całkowite liczby x , y takie, że \(xkj+ym=1\), czyli \(NWD(kj,\ m)=1\)